# Questions tagged [graph-theory]

Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.

3,524 questions
7k views

### Number of Shortest paths problem

Hey, Is countinng the number of shortest paths in a weighted directed acyclic graph with nonnegative weights #P-complete? If so, is there a proof I can read somewhere? Thanks
948 views

### A walk on a compact 2D surface embedded in 3-space that never returns home

At the risk of asking an uninformed question... Imagine an ant on a compact two-dimensional surface embedded in 3-space. The ant is placed at a point on the surface with random orientation. Once ...
989 views

### Singularity of sparse random matrices

The following topic came up in conversation with my office-mate Lionel: Let $p$ be a fixed prime, $c$ a fixed positive real parameter and $n$ a large number. Consider a random $(0,1)$ matrix with ...
467 views

### Complexity of determining if two graphs have same cycle matroid?

Consider the following question: Input: Two graphs G1 and G2 Question: Is the cycle matroid M(G1) isomorphic to the cycle matroid M(G2) What is the complexity of this question? It is well known ...
375 views

### A name for a claw-graph with paths attached to it

I wanted to know if the following family of graphs has a name in graph theory: A claw with paths of any length attached to the three free vertices of the claw. More formally, a connected acyclic ...
4k views

### How do I iterate over binary trees?

Suppose I have $n-1$ distinguishable labels for internal nodes $A=\{a_1, a_2,\dots, a_{n-1}\}$ and $n$ distinguishable labels for leaves $B=\{b_1,b_2,\dots, b_n\}$ with $A$ and $B$ disjoint. What is ...
716 views

### Edge-disjoint shortest paths

Let G be a simple connected graph. Let a, b, c, d be four distinct vertices of G. Is there a way to partition the above four vertices to two pairs, so that the two shortest paths between the ...
409 views

### Non trivial colouring of the edges of an infinite complete graph

Can you build a probabilistic scheme for colouring each edge (independently of all other edges) of the complete graph G on the positive integers such that the probability that G contains an infinite ...
931 views

### Infinite Ramsey theorem with infinitely many colours

Clearly, it is possible to colour the edges of an infinite complete graph so that it does not contain any infinite monochromatic complete subgraph. Now what about the following? Let $G$ be the ...
687 views

### 'Focusing' the mass of the Probability Density Function for a Random Walk

Consider a random walk on a two-dimensional surface with circular reflecting boundary conditions (say, of radius 'R'). Here, for a fixed-size area, one finds a larger fraction of the probability ...
2k views

### Interesting families of sparse graphs?

I'm interested in graph families which are sparse, and by sparse I mean the number of edges is linear in the number of vertices. |E| = O(|V|). Besides non-trivial minor-closed families of graphs (...
536 views

### Given a Spanning Tree and an Edge Not on the Spanning Tree, How to Form a Cycle Base?

I have a graph with Edge E and Vertex V, I can find the spanning tree using Kruskal algorithm, now I want to find all the cycle ...
719 views

### How can I prove that a sequence of squares of graph norms is never cyclotomic?

The norm of a graph is the largest eigenvalue of the adjacency matrix. I'll write ||G|| for the norm of G. Now, fix some graph <...
723 views

### Is there a free digraph associated to a graph?

A little bit of background: A graph G is, of course, a set of vertices V(G) and a multiset of edges, which are unordered pairs of (not necessarily distinct) vertices. We say that two vertices v_1, v_2 ...
2k views

### Special cases for efficient enumeration of Hamiltonian paths on grid graphs?

While the general problem of detecting a Hamiltonian path or cycle on an undirected grid graph is known to be NP-complete, are there interesting special cases where efficient polynomial time ...
3k views

### Algorithm to Find all the Cycle Bases in a Graph

I am given a graph defined by vertexes and edges. I have to obtain all the cycle bases in a network. No coordinates will be given for the nodes. Here's a sketch that illustrates my point. Note that ...
818 views

### Is there a matrix whose permanent counts 3-colorings?

Actually, I suppose that the answer is technically "yes," since computing the permanent is #P-complete, but that's not very satisfying. So here's what I mean: Kirchhoff's theorem says that if you ...
287 views

### Smooth immersion(?) of graphs into the plane

Sorry if the terminology's wrong, I don't know differential topology. Also, this is more of a brain-teaser than a bona fide research question, but it's hopefully a "real mathematician"-level brain-...
924 views

### Boolean network as a gauge field

Consider a set of N binary-state nodes at "time" t, each of which is a (boolean) transition function of two nodes in the set, evaluated at time t-1. Thus there are N of these boolean functions of two ...
894 views

### Looking for cubic, bipartite graphs with girth at least six and no cycles of length 8.

Aside from the Desargues graph, are there nice (at least vertex-transitive), small (say, less than 60 vertices), cubic, bipartite graphs with girth at least 6 and no 8-cycles? (or, even better, no ...
2k views

### What is the Tutte polynomial encoding?

Pretty much exactly what it says on the tin. Let G be a connected graph; then the Tutte polynomial T_G(x,y) carries a lot of information about G. However, it obviously doesn't encode everything about ...
2k views

### Can one make Erdős's Ramsey lower bound explicit?

Erdős's 1947 probabilistic trick provided a lower exponential bound for the Ramsey number $R(k)$. Is it possible to explicitly construct 2-colourings on exponentially sized graphs without large ...
941 views

### What is the expected number of maximal bicliques in a random bipartite graph?

Maximal Biclique: A complete bipartite subgraph, that isn't a subgraph of another complete bipartite subgraph. Given a bipartite graph $G=(V_{1}\cup V_{2}, E)$ where $|V_{1}|=|V_{2}|$ with ...
909 views

### Why are Dynkin diagrams characterized by their eigenvalues?

The Dynkin diagrams An, Dn, E6, E7, E8 can be characterized among finite simple connected graphs by the property that their eigenvalues (that is, the eigenvalues of their adjacency matrices) all have ...