Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with graph-theory
Search options answers only
not deleted
user 11142
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.
14
votes
A random walk on an infinite graph is recurrent iff ...?
This is a huge subject, but the best introductory reference remains:
Doyle, Peter G.; Snell, J.Laurie, Random walks and electric networks, The Carus Mathematical Monographs, 22. Washington, D. C.: Th …
- 96.4k
11
votes
Good programs for drawing (weighted directed) graphs
Mathematica is quite good these days and exports in a bazillion formats.
10
votes
Accepted
Christmas giftgiving
In the graph theoretic setting, the question is analyzed by N. Megiddo in
Optimal flows in networks with multiple sources and sinks (1973) (google will give you the pdf). Gives an algorithm, does no …
- 96.4k
10
votes
Accepted
When does a row standardized adjacency matrix have a real spectrum?
If the adjacency matrix is $A,$ the "row-standardized" matrix is $DA$, where $D$ is a diagonal matrix all of whose diagonal entries are positive, so has a positive diagonal square root $D^{1/2}$. Now, …
- 96.4k
8
votes
Accepted
Where does $2\sqrt{d-1}$ come from in Ramanujan graphs?
Yes, see this paper by Ram Murty. The basic point is that the sum of squares of the eigenvalues is the trace of the square of the adjacency matrix, which is equal to $d n.$
- 96.4k
8
votes
Accepted
In how many ways can a given planar graph be mapped into the plane?
It is a theorem of Whitney, that a $3$-connected planar graph has two planar embeddings (one being the other flipped over). If a graph is two-connected, then you can flip over some, but not all of the …
- 96.4k
7
votes
Is every metric space quasi-isometric to a graph?
If a graph is something where all edge lengths are $1,$ then your counter-example is fine. Take any (countable, for simplicity) set of points $X$, let $d_i$ be the distance from $x_i$ to its nearest n …
- 96.4k
7
votes
Accepted
Isomorphic regular graphs
The asymptotic number of $m$-regular graphs on $N$ vertices is well understood and can be found, for example, in Bollobas' Random Graphs (the argument uses Bollobas' "configuration model"). With proba …
- 96.4k
7
votes
Accepted
Length minimizing graphs between a finite set of points
This is the so-called Steiner Tree Problem.
- 96.4k
7
votes
Accepted
Proof of Fisher's inequality in combinatorial terms
A combinatorial proof of a more general inequality is given by Douglas Woodall.
One line proof Fisher's inequality is given by Renaud Palisse
Palisse, Renaud, A short proof of Fisher's inequality, …
- 96.4k
7
votes
Accepted
Generate random graphs that satisfy the triangle inequality
I am not sure I understand the issues: First you generate an ER (or your favorite model) random graph. The constraints that the edge lengths are in $[0, 1]$ and satisfy all possible triangle inequalit …
- 96.4k
6
votes
Accepted
Method to construct a bipartite graph G' with 2n vertices from a graph G
What you are looking for is the bipartite double cover.
- 96.4k
6
votes
Large power of an adjacency matrix
Vertex $1$ is connected to $2,$ $2$ to $3,$ $3$ to $1, 4, 5,$ and $4$ and $5$ have no out edges, so your graph is a directed cycle with a couple of hairs pointing out. The number of paths of length $k …
- 96.4k
6
votes
Discrete Laplace operator and its eigenvalues
The magic words are "spectral graph theory". Google it.
- 96.4k
6
votes
Drawing planar graphs with integer edge lengths
Not quite an answer, but:
The Kemnitz/Harborth conjecture was proved for cubic planar graphs in:
Straight line embeddings of cubic planar graphs with integer edge lengths
Jim Geelen1, Anjie Guo2,† …
- 96.4k