# Questions tagged [graph-theory]

Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

1,321 questions
Filter by
Sorted by
Tagged with
1k views

### Generating a tower defense maze, aka Finding the K most vital nodes (“nodewise interdiction”) in an unweighted grid-graph

In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls. Enemies take the shortest path from start to finish without passing through any walls (they aren't usually ...
2k views

### Number of distinct nodes in a random walk

Commute time in a connected graph $G=(V,E)$ is defined as the expected number of steps in a random walk starting at $i$, before node $j$ is visited and then node $i$ is reached again. It is basically ...
3k views

### Reasons for which a graph may be not $k$ colorable?

While reasoning a bit on this question, I've tried to identify all the different reasons for which a graph $G = (V_G,E_G)$ may fail to be $k$ colorable. These are the only 2 reasons that I was able to ...
3k views

1- Is there any specific properties for adjacency matrix when a graph is planar? 2- Is there any thing special for computing the permanent of adjacency matrix when a graph is planar?
1k views

### Coloring Planar Graphs

Consider the set of planar graphs where all the internal faces are triangles. If there is an interior point of odd degree the graph cannot be three colored. If every interior point has even degree can ...
2k views

### Graphs in which every minimal separator is an independent set

Background: Let $u, v$ be two vertices of an undirected graph $G=(V,E)$. A vertex set $S\subseteq V$ is a $u,v$-separator if $u$ and $v$ belong to different connected components of $G-S$. If no proper ...
1k views

### Finding a 5-cycle in a sparse graph efficiently.

(crossposted from MathOverflow) Hi, I was reading this thread: https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length I want to find a 5-cycle in a graph. Actually, what I really ...
3k views

### What are infinite graphs good for?

I have just read on the German Wikipedia that an infinite graph is a graph with an infinite number of nodes or an infinite number of edges. I only know applications and algorithms for finite graphs. ...
864 views

### $\Delta = 57, d=2$ Moore Graph

I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years. You may recall that Hoffman and ...
499 views

### Is it necessary to call matrix multiplication $n$ times to find a claw

A claw is a $K_{1,3}$. A trivial algorithm will detect a claw in $O(n^4)$ time. It can be done in $O(n^{\omega+1})$, where $\omega$ is the exponent of fast matrix multiplication, as follows: take the ...
1k views

### Succinct circuit representation of graphs

The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE: END OF THE LINE: Given circuits S and P ...
1k views

### Is feedback vertex set problem is solvable in polynomial time for 3-degree bounded graphs?

Feedback Vertex Set is NP-complete for general graphs. It is known to be NP-complete for degree-8 bounded graphs due to a reduction from vertex cover. The Wikipedia article says that it is poly-time ...
3k views

### Network / Social network analysis visualization tools?

I was using Jung ( http://jung.sourceforge.net/ ) to visualize page rank and found it a little slow and difficult to scale it beyond 100 nodes. I was wondering what other tools people use for network /...
604 views

### Minimum chordless odd-cycle graph completion: is it NP-hard?

The following interesting problem came up in my research recently: INSTANCE: Graph $G(V, E)$. SOLUTION: A chordless odd-cycle completion, defined as a superset $E'$ of the edge set $E$ so that ...
785 views

### maintaining a balanced spanning tree of a growing undirected graph

I am looking for ways to maintain a relatively balanced spanning tree of a graph, as I add new nodes/edges to the graph. I have an undirected graph that starts as a single node, the "root". At each ...
1k views

### Models of random graphs, for real computer networks

I am interested in models of random graphs which are similar to the graphs of real computer networks. I am not sure if the common well-studied $G(n,p)$ model ($n$ vertices, each possible edge is ...
1k views

### graphs where vertex coloring is in P but independent set is NP complete

Is there an example of a class of graphs for which the vertex coloring problem is in P but the independent set is problem is NP complete?
9k views

### Counting the Number of Simple Paths in Undirected Graph

How can I go about determining the number of unique simple paths within an undirected graph? Either for a certain length, or a range of acceptable lengths. Recall that a simple path is a path with no ...
570 views

### What separates easy global problems from hard global problems on graphs of bounded treewidth?

Plenty of hard graph problems are solvable in polynomial time on graphs of bounded treewidth. Indeed, textbooks typically use e.g. independet set as an example, which is a local problem. Roughly, a ...
2k views

### Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3? I know it is NP-complete for the ...
980 views

### Construction of graphs where every pair of vertices have an unique common neighbor

Let $G$ be a simple graph on $n$ vertices $(n > 3)$ with no vertex of degree $n − 1$. Suppose that for any two vertices of $G$, there is a unique vertex adjacent to both of them. It is an exercise ...
436 views

### Finding good induced subgraph

You are given a graph $G = (V,E)$ with $n$ vertices. It might be bipartite if you want. There are $m$ sets of edges $E_1,\ldots, E_m \subseteq E$ (say disjoint). I am interested in the problem of ...
830 views