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 440
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.
35
votes
Accepted
Graph containing all trees?
See Chung and Graham, On Universal Graphs for Spanning Trees. They prove that the number of edges is $\Theta(n\log n)$.
- 18.6k
21
votes
Accepted
Combinatorial proof that large-girth graphs are sparse?
It's known more specifically that any graph with girth ≥ 5 has $O(n^{3/2})$ edges — see e.g. Wikipedia on the Zarankiewicz problem.
Here's a combinatorial proof. Suppose that graph $G$ has $\ge kn^{3 …
- 18.6k
17
votes
Efficient way of determining isomorphism
A meta-answer: knowing that the answer is yes, for any NP search problem (regardless of completeness), does not help much in finding the answer. The reason is that, if you had an algorithm A that foun …
- 18.6k
16
votes
Is this a well known NP-complete problem?
The shortest (in terms of weight) path, constrained to have exactly n (or at most n) edges, can be found in polynomial time. For instance, given your graph $G=(V,E)$ make an expanded graph $H$ that ha …
- 18.6k
15
votes
Generalizations of Planar Graphs
There are many generalizations, but one of my favorites is "neighborhood systems": intersection graphs of systems of balls in a Euclidean space of bounded dimension, with the property that any point o …
- 18.6k
15
votes
Looking for cubic, bipartite graphs with girth at least six and no cycles of length 8.
Sure, form a torus graph by cutting a big parallelogram out of the tiling of the plane by regular hexagons and gluing opposite sides together. Any short cycle has length 6 (one hex) or length ≥ 10 (tw …
- 18.6k
13
votes
Reasons for the importance of planarity and colorability?
A few reasons for the importance of planarity having little to do with the need for maps:
A matroid is both graphic and co-graphic if and only if it is the graphic matroid of a planar graph
Planar g …
13
votes
Accepted
Graphs of Tangent Spheres
The number of edges in such a graph is linear in the number of vertices, and they can be split into two equal-sized subgraphs by the removal of $O(n^{\frac{d-1}{d}})$ vertices. See e.g.
A determinist …
- 18.6k
13
votes
Accepted
What (fun) results in graph theory should undergraduates learn?
Planar graph duality and its consequences, e.g. that a connected planar graph is Eulerian iff its dual is bipartite, or Hamiltonian iff its dual can be partitioned into two induced trees.
The emergen …
12
votes
Accepted
Proof of Bondy and Chvátal Theorem
Let $G=G_0, G_1, G_2$, etc. be a sequence of graphs where each $G_i$ is formed by performing a single closure step to $G_{i-1}$ — that is, add an edge $uv$ to $G_i$ when $u$ and $v$ together have at …
- 18.6k
11
votes
A question on representation of graphs
It's important to clarify what definition of "cycle" you have in mind. In algebraic-graph-theory contexts like this one, the natural definition is that it's a set of edges with even degree at each ver …
- 18.6k
11
votes
Accepted
Graphs in which every spanning tree is an independency tree
A graph G has all spanning trees independency if and only if G does not contain two adjacent vertices v and w, neither of degree one, such that the graph G' formed by removing v and w and all their in …
- 18.6k
11
votes
Accepted
Algorithms on graphs of bounded degeneracy/arboricity
Bounded degeneracy or arboricity just means that the graph is sparse (number of edges is proportional to number of vertices in all subgraphs).
Some ideas that have been used for fast algorithms on th …
- 18.6k
11
votes
Accepted
Finding a cycle of fixed length in a bipartite graph
Finding a cycle of length 2k in an arbitrary graph is the same thing as finding a cycle of length 4k in the bipartite graph formed by subdividing every edge. So in general even cycles of fixed length …
- 18.6k
11
votes
Accepted
Graphs with many triangles but few complete graphs on 4 vertices
Your statement may be true for large enough values of $c$, but it is not true for all constants $c>0$.
Specifically, for small enough values of $c$, form a counterexample $G$ consisting of the disjoi …
- 18.6k