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 8008
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.
12
votes
Is there a 7-regular graph on 50 vertices with girth 5? What about 57-regular on 3250 vertices?
Additional random facts.
The Peterson Graph can be obtained by identifying the antipodal points of a dodecahedron and it has $S_5$ as its automorphism group (order 120 of course).
There are a numbe …
- 30.1k
11
votes
Accepted
Are "almost all" strongly regular graphs rigid?
The article Random strongly regular graphs? by Peter Cameron http://www.maths.qmul.ac.uk/~pjc/preprints/randsrg.pdf provides some information about what is known and why someone might make that claim …
- 30.1k
10
votes
A labelling of the vertices of the Petersen graph with integers
With some computer searching I can get a sum of $37358$ and another of $37360.$ I list them below. I'm not saying they are optimal, though they seem pretty good.
The ten vertex labels should multiply …
- 30.1k
10
votes
Why are the numbers counting "ever-closer" lattice paths so round?
In fact the numbers $a_k$ in the various factors $1+a_k$ are multiples of $4$ and typically small ones.
$a_k=0$ unless every prime of the form $4m-1$ dividing $k$ occurs to an even power. If so, $$a_k …
- 30.1k
10
votes
Number of spanning forests in a graph
I started this, went to dinner, and came back to see that David Speyer anticipated me, but I'll put it in anyway. Here is a theorem, a story and a result somewhat along the lines you want.
Theorem: …
- 30.1k
8
votes
Moore graphs and finite projective geometry
Adding to the allure of this deadly siren song is the fact that there are constructions of this sort for the Moore graph of degree $3$ (the Petersen Graph with 10 vertices and independence number $4$) …
- 30.1k
8
votes
Accepted
What makes Graph invariants so useful/important?
We probably wouldn’t ask what makes graph properties useful. In many ways we consider isomorphic graphs as “the same.” Invariants are just properties that respect this sameness. The specific vertex …
- 30.1k
7
votes
Cubic almost-vertex-transitive graphs with given spanning tree
The two you give are the only cubic examples. There are various ways to weaken your requirements which give very small families.
One is Moore Graphs which take a $k$-ary tree of diameter $L$ and conn …
- 30.1k
6
votes
Algorithm to find all (up to isomorphism) perfect matchings of quartic plane graphs
The answer which is useful to you may depend on the details, so it would be good to have more. You mention isomorphism, quartic (regular of degree 4) and planar. Each of these could be important or ig …
- 30.1k
6
votes
Connectivity of the Erdős–Rényi random graph
I think perhaps the problem with the variance is not the overlap of the different trees but the fact that the number of spanning trees can be much much larger than 1 but not much less.
With $p=\frac …
- 30.1k
5
votes
The minimum of alpha times omega for vertex-transitive graphs
One very promising place to look is at Paley Graphs which are self dual (so $\alpha=\omega$.) This answer to a question suggests that, based on prime $n \lt 10000,$ it might be that $\alpha \omega =O( …
- 30.1k
5
votes
Accepted
Is the following graph well known?
They might have a name, I don't know. For the next few lines let us call each a Partial Permutation graph $PP(n,k)$ (assume $k<n$). They may not get as much respect because they are not distance trans …
5
votes
Accepted
Classes of graphs for which isospectrum implies isomorphism?
Maximum degree 2 would be such a class (which includes regular of degree $2$ as a subclass). Transitive graphs (by which I mean that the relation of being connected by an edge is transitive) are anoth …
- 30.1k
5
votes
Game on undirected graphs
On any graph it is a combinatorial game which can be analyzed by the usual techniques. I can think of a few named cases.
If the graph is a path, it is called Kayles. Having it be a single cycle is …
- 30.1k
5
votes
Accepted
Clique and chromatic number of cycle graph of permutations
It turns out that for the $S_5$ graph the clique number is $7$ but the chromatic number is $30.$ Details at the end.
The number of cycles is $c_n=\sum_{k=2}^{n}\binom{n}{k}(k-1)!$ The first few terms …
- 30.1k