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.
2
votes
A plane graph problem
This is Cauchy's Combinatorial Lemma, which is Lemma 26.8 in Pak's book.
- 96.4k
1
vote
Lower bound on diameter of trivalent graphs
To amplify on Fedor's answer, random graphs come close to this bound, for a lot more color see the ancient (but still useful) 1987 paper by Fan Chung.
- 96.4k
1
vote
Accepted
Generalizing Steinitz's theorem
Well, no direct generalization is known. One related result (which seems to have come out of an attempt to generalize Steinitz) is this paper by D. Eppstein and E. Mumford. However, since Steinitz' th …
- 96.4k
3
votes
Is the following graph well known?
It is the "generalized Kneser graph". See the Wikipedia article on "Kneser graph" and references therein. See also a paper by B. Mohar and I. Rivin on related geometric questions...
- 96.4k
0
votes
Bounds on spanning tree for sparse graphs
Yes. See this paper:
www.intlpress.com/JOC/p/2010/JOC-1-2-a1-Thomassen.pdf
(Carsten Thomassen, spanning trees and orientations in graphs; google shows you the full text...), and references therein ( …
- 96.4k
1
vote
Spanning trees of $H \cup e$ in terms of $H$
This seems to be exactly the subject of:
http://gradworks.umi.com/31/89/3189623.html
In particular, the "Feussman formula" cited in the abstract would seem to be useful (this is used to prove the ma …
- 96.4k
3
votes
Proving that every graph is an induced subgraph of an r-regular graph
In that case, the answer is given by
Classification of degree (bi-)sequences of bipartite graphs?
You call the vertices of your graph red, and you want to have a collection of blue vertices, so that t …
- 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
1
vote
Construct a Random graph from the degree distribution,
See
http://www.stat.berkeley.edu/~sourav/beam-yale-trans.pdf
- 96.4k
3
votes
positive weighted directed graphs
The set of weightings whose sum vanishes along each cycle corresponds exactly to gradients of functions on vertices (in other words, the weight of an edge is $f(h) - f(t),$ where $h, t$ are head and t …
- 96.4k
3
votes
Faithfully embeddable graphs
To see whether a complete graph (also known as a finite metric space) is isometrically embeddable in $\mathbb{E}^n,$ one needs to check the signs of various minors of the Cayley-Menger matrix, describ …
- 96.4k
5
votes
Accepted
Number of spanning subgraphs of the complete bipartite graph $K(m,n)$
This is only known explicitly for $m=4$. A decent survey is here:
http://www.math.ru.nl/~bosma/Students/JannekevandenBoomen/JannekevdBoomenMScthesis.pdf
- 96.4k
3
votes
How many triangles can a connected graph with $n$ vertices and $m$ edges have?
This question (together with massive generalizations) is answered in I. Rivin's 2001 paper.
- 96.4k
6
votes
Distance-regular graphs
See http://www.win.tue.nl/~aeb/ (the web page of A. Brouwer) -- he has data, and I am guessing that he would be receptive to questions, as well.
- 96.4k
5
votes
Accepted
An upper bound for number of triangles in a graph
The property is that the graph be sparse, since it is easy to show that the number of triangles is $O(|E|^{3/2}),$ so as long as $E = O(V),$ your result holds. For the (simple) proof and sharp extensi …
- 96.4k