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 not deleted
user 9025
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.
43
votes
Accepted
A conjecture on planar graphs
Let $L(G)=\sum_{xy\in E(G)} \min\lbrace\deg(x),\deg(y)\rbrace$.
THM. For a simple planar graph with $n$ vertices, $L(G)\le 18n-36$ for $n\ge 3$.
PROOF. Recall that a simple planar graph with $k\ge 3$ …
- 37.7k
43
votes
3
answers
2k
views
History of the four-colour problem
It is stated in many places that the first published reference to the four-colour problem (aka the four-color problem) was an anonymous article in The Athenæum of April 14, 1860, attributed to de Morg …
- 37.7k
37
votes
Accepted
How many $p$-regular graphs with $n$ vertices are there?
McKay and Wormald conjectured that the number of simple $d$-regular graphs of order $n$ is asymptotically
$$\sqrt 2 e^{1/4} (\lambda^\lambda(1-\lambda)^{1-\lambda})^{\binom n2}\binom{n-1}{d}^n,$$
whe …
- 37.7k
29
votes
Accepted
Is there a graph with 99 vertices in which every edge belong to a unique triangle and every ...
First we will prove the graph is regular.
Let $x,y$ be two non-adjacent vertices, and let $a,b$ be their common neighbours. Define $X$ to be the neighbourhood of $x$ other than $a,b$, and $Y$ to be …
- 37.7k
28
votes
Is it easy to produce hard-to-color graphs?
Since nobody seems to have addressed question 3, I will. The proofs of the 4-colour theorem are effective in the sense that they can be turned into polynomial-time algorithms. So there are no planar …
- 37.7k
22
votes
2
answers
2k
views
Largest graphs of girth at least 6
Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6.
Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.
…
- 37.7k
21
votes
1
answer
1k
views
A strange sum over bipartite graphs
While mucking around with some generating functions related to enumeration of regular bipartite graphs, I stumbled across the following cutie. I wonder if anyone has seen it before, and/or if anyone …
- 37.7k
19
votes
Reasons for difficulty of Graph Isomorphism and why Johnson graphs are important?
Johnson graphs do not cause difficulty to existing programs. Actually they are rather easy; nauty can handle them up to tens of millions of vertices, and so can other programs such as Traces and Bliss …
- 37.7k
18
votes
4
answers
2k
views
Complexity of equitable partitions
We are talking about undirected simple graphs and partitions of their vertex sets into disjoint non-empty cells. Such a partition is equitable if for any two vertices $v,w$ in the same cell, and any …
- 37.7k
17
votes
0
answers
505
views
Maximum automorphism group for a 3-connected cubic graph
The following arose as a side issue in a project on graph reconstruction.
Problem: Let $a(n)$ be the greatest order of the automorphism group of a 3-connected cubic graph with $n$ vertices. Find a g …
- 37.7k
16
votes
Regular graph of order 50, degree 7 and Automorphism group of order 288000. How to check if ...
There isn't any good general computational method for determining whether a permutation group has a regular subgroup. It was recently described to me by an authority on permutation group algorithms a …
- 37.7k
16
votes
Is there a Cayley graph of a non-abelian finite group that is not isomorphic to any Cayley g...
If I understand my own 1979 catalogue of small transitive graphs, this happens first at 12 vertices. The simplest example to describe (L10 in the catalogue): take the tetrahedon and cut off each of t …
- 37.7k
16
votes
What is the upper bound of $R\underbrace{(3,3,3, \ldots,3)}_\text{$k$ times}$?
All questions about Ramsey numbers for small graphs should be first checked in Staszek Radziszowki's amazing frequently updated survey. On page 40 we find the upper bound $(e-\frac16)k!+1\approx 2.55 …
- 37.7k
16
votes
Accepted
What happens to eigenvalues when edges are removed?
The smallest eigenvalue can go up or down when an edge is removed.
For "down": $G=K_n$ for $n\ge 3$.
For "up": Take $K_n$ for $n\ge 1$ and append a new vertex attached to a single vertex of the orig …
- 37.7k
15
votes
Accepted
Are all cubic graphs almost Hamiltonian?
Yes, every connected cubic graph is 3-almost-Hamiltonian.
Replace each edge by two parallel edges then follow an Eulerian circuit.
In the case of a bridgeless cubic graph, you can add a perfect match …
- 37.7k