All Questions
Tagged with planar-graphs hamiltonian-path
17
questions
3
votes
1
answer
34
views
Is There any Untraceable Generalized Petersen Graph?
The Petersen graph is one of the example of graph which is not Hamiltonian.
Can we find an example among the generalized Petersen graph which doesn't have Hamiltonian path (untraceable)?
- 1,949
1
vote
1
answer
36
views
What kind of graph is this? Hamiltonian by association?
Here is an example of a connected cycle using the edges:
$ABC-BCD-BCE-CDE-BDE-ABE-ACE-ADE-ACD$
Here $ABC$ shares $BC$ with $BCD$, $BCD$ shares $BC$ with $BCE$, ... , $ACD$ shares $AC$ with $ABC$. ...
- 633
0
votes
1
answer
774
views
Graph problem about roads built between towns [closed]
There are 10 cities in a country. The Government starts to build direct roads between the cities, but with random access, it can build direct road between two cities even if there is already another ...
- 21
2
votes
1
answer
573
views
Prove Herschel graph is nonhamiltonian
Let us denote by $c(G)$ the number of components of graph $G$.
Theory: For a hamiltonain graph we have $c(G-S)\leq|S|$ for any set $S$ of vertices of $G$.
How can I show that Herschel graph is ...
0
votes
2
answers
264
views
Degree sequence in a maximal planar graph
Two isomorphic 9 vertex graphs Given the ordered degree sequence of a hamiltonian circuit in a maximal planar graph. Can we have different maximal planar graphs with the same ordered degree sequence?
...
- 13
1
vote
1
answer
224
views
Ultra-Hamiltonian cycle
Ultra-Hamiltonian cycling is defined to be a closed walk that visits every vertex exactly once, except for at most one vertex that visits more than once.
Question:- Prove that it is NP-hard to ...
1
vote
0
answers
58
views
Is there any new developments on the Barnette's conjecture?
When I searching for interesting math problems. I find there is a graph theory conjecture called the Barnette's conjecture.
The statement is: Is every bipartite simple polyhedron Hamiltonian?
A early ...
- 178
5
votes
1
answer
808
views
Definition of a separating triangle in planar graph
In Bill Tutte's famous book Graph Theory as I Have Known It he discusses Hassler Whitney's theorem on Hamiltonian cycles in planar graphs, summarising it thus:
Any strict triangulation in which there ...
- 153
7
votes
1
answer
2k
views
How does Grinberg's theorem work?
Grinberg's theorem is a condition used to prove the existence of an Hamilton cycle on a planar graph. It is formulated in this way:
Let $G$ be a finite planar graph with a Hamiltonian cycle $C$, ...
- 173
9
votes
1
answer
2k
views
All 4-connected planar graphs are Hamiltonian-connected
I started reading Thomassen's paper A Theorem on Paths in Planar Graphs, where he proves one of Plummer's conjectures: Every $4$-connected planar graph is Hamiltonian-connected.
Context. Recall that ...
- 11.3k
1
vote
1
answer
523
views
Is there a non-planar, non-hamiltonian and eulerian graph?
I'm trying to find a graph that is non-planar, non-hamiltonian and eulerian but I can't find anyone.
Is this possible?
Thanks
- 29
3
votes
1
answer
1k
views
3-connected planar bipartite graph without a Hamiltonian path
I'm stuck with exercise 18.1.5 of Bondy & Murty's Graph Theory book which asks for an example of a 3-connected planar bipartite graph on fourteen vertices that is not traceable (that is, which has ...
- 367
0
votes
0
answers
39
views
Are there any software or libraries(in some language) which draws all the planar graphs given the number of vertices?
I am working on interrelationships between planar and Hamiltonian graphs and for the purpose I need planar graphs for inspection. Since their number grows asymptotically, I cannot approach it manually....
- 159
3
votes
1
answer
570
views
Edge-disjoint Hamiltonian cycles in a planar graph.
Is it possible to have a planar graph with two edge-disjoint Hamiltonian cycles?
- 65
1
vote
2
answers
150
views
Number of Hamiltonian Cycles in planar chordal graph
I have a given planar chordal graph $G$. Due to the construction of $G$ I know that there exists at least one Hamiltonian cycle in $G$. My question is:
How many Hamiltonian cycles are in $G$? (an ...
- 328