9 papers
On finding hamiltonian cycles in Barnette graphs
Behrooz Bagheri Gh., Tomas Feder, Herbert Fleischner +1
In this paper, we deal with hamiltonicity in planar cubic graphs G having a facial 2-factor Q via (quasi) spanning trees of faces in G/Q and study the algorithmic complexity of fin…
The most general structure of graphs with hamiltonian or hamiltonian connected square
J. Ekstein, H. Fleischner
On the basis of recent results on hamiltonicity and hamiltonian connectedness in the square of a 2-block, we determine the most general block-cutvertex structure a graph may ha…
A Best Possible Result for the Square of a 2-Block to be Hamiltonian
Jan Ekstein, Herbert Fleischner
It is shown that for any choice of four different vertices x_1,...,x_4 in a 2-block G of order p>3, there is a hamiltonian cycle in G^2 containing four different edges x_iy_i of E(…
Perfect Pseudo-Matchings in cubic graphs
Herbert Fleischner, Behrooz Bagheri Gh., Benedikt Klocker
A perfect pseudo-matching M in a cubic graph G is a spanning subgraph of G such that every component of M is isomorphic to K_2 or to K_1,3. In view of snarks G with dominating cycl…
On the algorithmic complexity of finding hamiltonian cycles in special classes of planar cubic graphs
Behrooz Bagheri Gh., Tomas Feder, Herbert Fleischner +1
It is a well-known fact that hamiltonicity in planar cubic graphs is an NP-complete problem. This implies that the existence of an A-trail in plane eulerian graphs is also an NP-co…
Hamiltonian cycles in planar cubic graphs with facial 2-factors, and a new partial solution of Barnette's Conjecture
Behrooz Bagheri Gh., Tomas Feder, Herbert Fleischner +1
We study the existence of hamiltonian cycles in plane cubic graphs G having a facial 2-factor Q. Thus hamiltonicity in G is transformed into the existence of a (quasi) spanning tre…