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 2384
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.
9
votes
Girth 5 graphs with diameter 2
No infinite family exists. In fact all graphs with diameter $d$ and girth $2d+1$ have to be regular, and thus are Moore graphs. This was proved in
R. Singleton, "There is no irregular Moore graph", A …
- 85.6k
10
votes
Accepted
Probability of Generating a Connected Graph
Just a few more comments to the answers and references already posted. I will denote your graph by $G(n,d(n))$. I'm not sure if this is satisfactory enough, but with fairly standard methods one can pr …
- 2,821
3
votes
Hoffman singleton conjecture
The suggestion from the other answer is great. I wanted to add that it is not even known whether the Moore graph of degree 57 must contain a single copy of a Petersen graph, let alone a decomposition …
- 85.6k
11
votes
Proofs of parity results via the Handshaking lemma
Another very famous example is Sperner's lemma. Other examples are Chevalley's theorem for $p=2$, Tucker's lemma, the fact that the number of decompositions into Hamiltonian cycles is even etc. (See …
- 4,713
2
votes
Accepted
Is there a planar network whose path give a TNN matrix whose entries are Eulerian numbers?
There is a Bratelli diagram which satisfies this. Consider $\mathbb N^2$ as a graph where the edges are given by k parallel directed edges from $(n,k)$ to $(n+1,k)$, and $n-k+1$ parallel directed edge …
- 2,821
10
votes
Wanted: a graph $G$ without bridges, whose square is not hamiltonian
You can find an example of a bridgeless graph with cut points, whose square is not hamiltonian in this paper of Fleischner and Kronk. (I know the paper is in German, but the figure of the graph is on …
- 1,446
9
votes
Accepted
Round-Robin Tournaments and Forests
The bijection between score vectors and forests on labeled nodes is due to Kleitman and Winston. (This paper)
A small clarification, your question about the cardinalities being equal was answered by S …
- 1,446
19
votes
What are the applications of hypergraphs?
Hypergraphs and various properties that we can prove about them are the basis of many techniques that are used in modern mathematics. I will mention Deducing the Density Hales–Jewett Theorem from an i …
- 12.9k
8
votes
The chromatic number of the union of two graphs
In a similar vein to $\chi^{\ast}(G_n)$, we can define a quantity $\chi^{\ast \ast}(G_n)$ as follows: Suppose you have an abelian group $M$ and a set $S=\{x_1, x_2, \dots, x_n\}\subset M$, such that f …
- 85.6k
2
votes
Integral positive definite quadratic forms and graphs
In Cluster algebras of finite type and positive symmetrizable matrices by Barot, Geiss and Zelevinsky (J. London Math. Soc. (2) 73 (2006), no. 3, 545--564, doi:10.1112/S0024610706022769, arXiv:math/04 …
- 35.5k
19
votes
Accepted
Reference request: Moore graphs
Moore posed this problem to Hoffman at a conference, so it is not in print. Hoffman makes the following remark (from "Selected Papers of Alan Hoffman with Commentary", pp. 367):
After I discussed the …
- 85.6k
2
votes
Anchor sets for lattice polygons: Part I
Consider the set $S_0$ consisting of all points $(x,y)$ such that $(x,y)\in \mathcal D$ but $(x-1,y)$ and $(x,y-1)$ are not in $\mathcal D$. It is clear that $S_0$ satisfies the conditions in the prob …
- 24.2k
8
votes
Number of spanning trees of a quotient graph
Let us group the vertices as $U=\{u_1,u_2,\dots,u_n\}$ and $V=\{v_1,v_2,\dots, v_n\}$ where $f(u_i)=v_i$. Let $L_0$ be the laplacian of the graph with vertex set $U$ and edges as restricted from $G$, …
6
votes
Accepted
$1$-factorizability for "complete" finite hypergraphs
This is Baranyai's theorem. Other than in Baranyai's original paper you can also find a cool proof in the article "Uniform hypergraphs" by Brouwer and Schrijver which uses max-flow min-cut.
- 85.6k
8
votes
Accepted
Embedding any graph in a regular graph with the same chromatic number
Yes, you can find such a $G_R$ of any degree greater than or equal to the maximum degree of $G$. This is the main theorem of the paper "On regular bipartite-preserving supergraphs" by G. Chartrand and …
- 85.6k