Skip to main content

All Questions

Filter by
Sorted by
Tagged with
5 votes
1 answer
119 views

Sufficient condition for a Hamilton cycle C in a planar triangulation G s.t. every triangle in G has an edge in C

Let G be a k-connected planar triangulation (k4) and let C be a Hamilton cycle of G. Then: Which conditions would be sufficient to assure that every triangle of G has at least one ...
Jose Antonio Martin H's user avatar
4 votes
3 answers
506 views

Does every finite bridgeless cubic planar simple undirected graph admit a 2-factorization with at most two components each of which has even order?

Consider simple bridgeless cubic planar graphs. Does each such graph admit a 2-factorization with 2 components each of which has even order? If not, does anyone know of an counterexample? ...
Jimmy Dillies's user avatar
4 votes
0 answers
69 views

is a 4-connected planar graph still Hamiltonian after removing an edge?

We know that 4-connected planar graphs are Hamiltonian(by the known Tutte Theorem). Additionally, Thomas and Yu [1] proved that removing two vertices from a 4-connected planar graph still preserves ...
Licheng Zhang's user avatar
3 votes
2 answers
727 views

The perfect matching problem of planar graph

We know that connectivity is closely related to the Hamiltonian of planar graphs. The most famous result is the Tutte theorem. Theorem (Tutte, 1956). A 4-connected planar graph has a Hamiltonian ...
Licheng Zhang's user avatar
2 votes
1 answer
138 views

Two ears polygon in a maximal planar hamiltonian graph

Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. Is it always possible to ...
P.Labarque's user avatar
0 votes
0 answers
52 views

Are there 4-connected planar non-hamilton multi-graphs?

Tutte proved the famous result: Every planar 4-connected graph has a hamiltonian cycle. But I read in Section 111.6.5 on book Eulerian Graphs and Related Topics that the author Herbert Fleischner ...
Licheng Zhang's user avatar