Stack Exchange Network

Stack Exchange network consists of 174 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.

6
votes
4answers
2k views

Number of spanning trees in a grid

Given a $\sqrt{n}\times\sqrt{n}$ piece of the integer $\mathbb{Z}^2$ grid, define a graph by joining any two of these points at unit distance apart. How many spanning trees does this graph have (...
0
votes
3answers
2k views

min cut and max cut

If you want to maximize a function f(x), you can do this by minimizing -f(x). Naively it seems like an analogous trick could convert a max cut problem into a min cut problem, however this is ...
15
votes
11answers
2k views

Chromatic number of graphs of tangent closed balls

The Koebe–Andreev–Thurston theorem gives a characterization of planar graphs in terms of disjoint circles being tangent. For every planar graph $G$ there is a disk packing whose graph is $G$. What ...
7
votes
1answer
637 views

Graphs of Tangent Spheres

The Koebe–Andreev–Thurston theorem gives a characterization of planar graphs in terms of disjoint circles being tangent. For every planar graph $G$ there is a circle packing whose graph is G. What ...
34
votes
21answers
4k views

Generalizations of Planar Graphs

This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; ...
4
votes
2answers
329 views

A graph connectivity problem (restated)

Given an undirected connected graph, our goal is to remove some edges to make the graph disconnected. The constraint is that each node of the graph can not lose more than $m$ edges incident to it. I ...
43
votes
4answers
7k views

Why are planar graphs so exceptional?

As compared to classes of graphs embeddable in other surfaces. Some ways in which they're exceptional: Mac Lane's and Whitney's criteria are algebraic characterizations of planar graphs. (Well, ...
0
votes
1answer
369 views

Szemeredi's Regularity Lemma

Theorem: (SRL) For every $\epsilon>0$ and integer $m\geq 1$ there is an $M$ such that every graph $G$, with $|G|\geq m$ has an $\epsilon$-regular partition $V(G)=V_0\cup\ldots\cup V_k$ for some $m\...
5
votes
2answers
380 views

How are graph automorphisms are affected by transformations?

I have a heavily symmetric regular graph whose automorphisms I know. I remove one subgraph and insert another one in a consistent manner; for example, this could be a Delta-Y transformation (...
5
votes
5answers
3k views

A random walk matrix has eigenvalue 1 with multiplicty 1 - why?

A random walk matrix has largest eigenvalue 1 with multiplicty 1 - why? Let $G$ be a non-directed, regular connected graph with degree $d$. Let $A$ be its random walk matrix, i.e. it's adjacency ...
6
votes
2answers
36k views

Difference between connected vs strongly connected vs complete graphs [closed]

What is the difference between connected strongly-connected and complete? My understanding is: connected: you can get to every vertex from every other vertex. strongly connected: every vertex ...
9
votes
5answers
1k views

Triangle-free Lemma

Theorem (Triangle-free Lemma). For all $\eta>0$ there exists $c > 0$ and $n_0$ so that every graph $G$ on $n>n_0$ vertices, which contains at most $cn^3$ triangles can be made triangle free ...
10
votes
2answers
1k views

Ramsey Theory, monochromatic subgraphs

If we have the complete countably infinite bipartite graph $K_{\omega,\omega}$ and we colour the edges with just two colours. Should we expect to get a monochromatic copy of $K_{\omega,\omega}$. ...
8
votes
4answers
1k views

Prime numbers $p$ not of the form $ab + bc + ac$ $(0 < a < b < c )$ (and related questions)

If we ask which natural numbers n are not expressible as $n = ab + bc + ca$ ($0 < a < b < c$) then this is a well known open problem. Numbers not expressible in such form are called Euler'...
20
votes
6answers
2k views

“The” random tree

One time I heard a talk about "the" random tree. This tree has one vertex for each natural number, and the edges are constructed probabilistically. Connect vertex $2$ to vertex $1$. Connect vertex $3$ ...
16
votes
3answers
2k views

Number theoretic spectral properties of random graphs

If G is a graph then its adjacency matrix has a distinguished Peron-Frobenius eigenvalue x. Consider the field Q(x). I'd like a result that says that if G is a "random graph" then the Galois group ...
11
votes
12answers
6k views

Graphs with fractal properties?

For the purposes of a research project, I am wondering if there are any resources on graphs with fractal properties, by which I mean self-similarity in particular. For instance, imagine a graph where ...
15
votes
5answers
6k views

Which graphs have incidence matrices of full rank?

This is a follow-up to a previous question. What graphs have incidence matrices of full rank? Obvious members of the class: complete graphs. Obvious counterexamples: Graph with more than two ...
0
votes
2answers
257 views

What is the name for this type of graph? [closed]

(old image at bayimg.com/image/iaeidaacn.jpg just there for the post to still make sense) Both graphs have a braching factor of 3. Graph A is a "tree". Is there a name for the type of graphs as B? (...
10
votes
1answer
827 views

Is every matching of the hypercube graph extensible to a Hamiltonian cycle

Given that $Q_d$ is the hypercube graph of dimension $d$ then it is a known fact (not so trivial to prove though) that given a perfect matching $M$ of $Q_d$ ($d\geq 2$) it is possible to find another ...
6
votes
2answers
578 views

Algorithms for laying out directed graphs?

I have an acyclic digraph that I would like to draw in a pleasing way, but I am having trouble finding a suitable algorithm that fits my special case. My problem is that I want to fix the x-...
0
votes
3answers
222 views

Where to find nice diagrams of trees and other graphs? [closed]

Are there some publicly available, vector format diagrams of trees and other graphs? They aren't hard to make, but they sure do take a lot of time (for me).
12
votes
3answers
416 views

Groupoid of moves on trivalent fatgraph

Let $T$ be a finite trivalent fatgraph - i.e. a graph with a cyclic order of the edges at each vertex. Then there are certain basic "moves" we can perform on $T$: an embedded edge can be collapsed and ...
7
votes
1answer
1k views

Graphs with incidence matrices whose pseudoinverses are proportional to their transposes

When I was working on my PhD dissertation, I came across a physical situation involving nodes and flows between them. It turned out that I was working with a complete oriented graph $K_n$ (all nodes ...
10
votes
14answers
19k views

What introductory book on Graph Theory would you recommend?

I'm looking for a book with the description of basic types of graphs, terminology used in this field of Mathematics and main theorems. All in all, a good book to start with to be able to understand ...
5
votes
3answers
1k views

Erdős–Stone theorem type edge density estimates for bipartite graphs?

The Erdős–Stone theorem theory says that the densest graph not containing a graph H (which has chromatic number r) has number of edges equal to $(r-2)/(r-1) {n \choose 2}$ asymptotically. However, ...
3
votes
3answers
916 views

Number of paths equal less than equal to a certain length

Hey, I need to count the number of paths from node $s$ to $t$ in a weighted directed acyclic graph s.t. the total weight of each path is less than or equal to a certain weight $W$. I have an ...
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
947 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
974 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
465 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
371 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
707 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
406 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
902 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
684 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
528 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
714 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
695 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
810 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
284 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
920 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
884 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 ...
12
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
931 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 ...