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 1492
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.
8
votes
0
answers
214
views
Has anyone implemented a circle graph recognition algorithm?
A double occurrence word is a circular string of length $2n$ over an alphabet of size $n$ with each letter occurring exactly twice, for example:
ABACCDBD
Given a double occurrence word, we can form …
- 12.7k
5
votes
Accepted
Graph homomorphism to minor
I think a 5-cycle meets your needs.
Clique number 2, chromatic number 3. Check.
(It does have a homomorphism to itself, but I assume you meant proper minor.)
It has no homomorphism to a 4-cycle or …
- 12.7k
3
votes
A condition that might force biregularity of a bipartite graph
I tried to construct an example that is not biregular. To make it easy, I assumed that n=3 and that the vertices of V all have degree 4 except one of degree 5 (so each vertex of U is automatically adj …
- 12.7k
2
votes
Criticalness and Hamiltonicity
This is some Sage code to check the counterexample posted by user1272680. I can't put this in a comment, so I am putting it as an answer, but the credit should go to user1272680.
g=Graph(21)
g.add_ed …
- 12.7k
7
votes
Accepted
Question about 3-regular graphs with a restriction (also fullerene and four color theorem)
Use Brinkmann & McKay's program "plantri"...
You will discover that there are
3 on 16 faces (as you said), 4 on 17 faces, 12 on 18 faces, 23 on 19 faces, 73 on 20 faces
and then going to Sloane's o …
- 12.7k
2
votes
Accepted
A Theory of 3-connected graphs
It is in the volume "Selected Papers of W.T. Tutte" published by the Charles Babbage Research Centre about 20 years ago.
(Strangely the reference is slightly different, but the title and page number …
- 12.7k
6
votes
Accepted
Is there more than 1 way to make a 17-node graph such that there are no 4-cycles and each no...
Yes, here are some
Graph 1, order 17.
0 : 5 8 12 13;
1 : 6 9 13 16;
2 : 7 10 13 15;
3 : 8 9 14 15;
4 : 9 10 11 12;
5 : 0 11 15 16;
6 : 1 10 14 16;
7 : 2 11 13 14;
8 : 0 3 12 14;
9 …
- 12.7k
6
votes
Accepted
strongly regular graph as two-graph
No, there is a correspondence between certain strongly regular graphs and two-graphs but those strongly regular graphs have specific and restricted parameters.
- 12.7k
2
votes
Accepted
Invariance of Tutte polynomial under "trivalentization"
The process of replacing a vertex of degree $d > 3$ with a $d$-cycle is normally called truncating a vertex (from the idea of slicing off a corner of a geometric shape).
If the original graph is plana …
- 12.7k
10
votes
2
answers
2k
views
Graphs where every two vertices have odd number of mutual neighbours
There was a rather cute question last week about graphs where every pair of distinct vertices has an odd number of mutual neighbours.
The question was to show that such a graph must have an odd numbe …
- 12.7k
8
votes
Accepted
Critical with respect to chromatic, but not Hadwiger number
Here's one for you:
Although it is not drawn planar, it is planar, and so it has no $K_5$-minor. However it has lots of $K_4$-minors. For example, the $0,4,6,8$ induces $K_4\backslash e$ and so ad …
- 12.7k
6
votes
Accepted
How to generate computational data in graph theory?
Use Brendan McKay's program geng, which is distributed with the nauty/Traces package and is available from http://pallini.di.uniroma1.it/.
There are about 165091172592 graphs on 12 vertices, so it mi …
- 12.7k
4
votes
Application of cospectral graphs
I'll add some thoughts partially in response to Igor's answer, in that while I agree that cospectral graphs are intrinsically interesting, I think there is a bit more to it than that.
Many authors (i …
- 12.7k
6
votes
Accepted
What is the relation between Hadwiger number and Treewidth?
Planar graphs have Hadwiger number at most 4, but can have arbitrarily high tree width (as evidenced by the $n \times n$ grid).
- 12.7k
2
votes
Cordial Labeling of 4-regular graphs
Eulerian graphs with $e$ edges cannot be cordial unless $e$ is a multiple of $4$ so don't bother looking at $4$-regular graphs with an odd number of vertices. (This is in Cahit's original paper that i …
- 12.7k