7 papers · 1 filter
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…
Revisiting the Hamiltonian Theme in the Square of a Block: The General Case
Herbert Fleischner, Gek L. Chia
This is the second part of joint research in which we show that every -connected graph has the property. That is, given distinct , ,…
Revisiting the Hamiltonian Theme in the Square of a Block: The Case of DT-Graphs
Gek L. Chia, Jan Ekstein, Herbert Fleischner
The square of a graph G, denoted G^2, is the graph obtained from G by joining by an edge any two nonadjacent vertices which have a common neighbor. A graph G is said to have the F_…