Displaying similar documents to “Some remarks on Jaeger's dual-hamiltonian conjecture”

A Note on Barnette’s Conjecture

Jochen Harant (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.

Minimum degree, leaf number and traceability

Simon Mukwembi (2013)

Czechoslovak Mathematical Journal

Similarity:

Let G be a finite connected graph with minimum degree δ . The leaf number L ( G ) of G is defined as the maximum number of leaf vertices contained in a spanning tree of G . We prove that if δ ≥ 1 2 ( L ( G ) + 1 ) , then G is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if δ ≥ 1 2 ( L ( G ) + 1 ) , then G contains a spanning path. This provides a partial solution to a conjecture of the computer program Graffiti.pc [DeLaVi na and Waller, Spanning trees with many leaves and average distance, Electron. J. Combin....