Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
1answer
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
5
votes
5answers
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 ...
8
votes
3answers
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 ...
5
votes
2answers
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 ...
4
votes
3answers
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 ...
0
votes
4answers
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 ...
1
vote
1answer
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 ...
5
votes
1answer
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 ...
6
votes
2answers
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 ...
6
votes
3answers
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 ...
8
votes
10answers
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 (...
0
votes
2answers
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 ...
7
votes
2answers
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 <...
7
votes
2answers
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 ...
7
votes
3answers
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 ...
2
votes
5answers
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 ...
12
votes
3answers
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 ...
5
votes
2answers
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-...
3
votes
3answers
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 ...
6
votes
3answers
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 ...
11
votes
9answers
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 ...
13
votes
5answers
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 ...
5
votes
3answers
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 ...
20
votes
3answers
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 ...