Displaying similar documents to “Hamiltonian connectedness and a matching in powers of connected graphs”

On a Hamiltonian cycle of the fourth power of a connected graph

Elena Wisztová (1991)

Mathematica Bohemica

Similarity:

In this paper the following theorem is proved: Let G be a connected graph of order p ≥ 4 and let M be a matching in G . Then there exists a hamiltonian cycle C of G 4 such that E ( C ) ⋂ M = 0 .

Decompositions into two paths

Zdzisław Skupień (2005)

Discussiones Mathematicae Graph Theory

Similarity:

It is proved that a connected multigraph G which is the union of two edge-disjoint paths has another decomposition into two paths with the same set, U, of endvertices provided that the multigraph is neither a path nor cycle. Moreover, then the number of such decompositions is proved to be even unless the number is three, which occurs exactly if G is a tree homeomorphic with graph of either symbol + or ⊥. A multigraph on n vertices with exactly two traceable pairs is constructed for each...

Bounds of lengths of open Hamiltonian walks

Pavel Vacek (1992)

Archivum Mathematicum

Similarity:

If G is a graph, an open Hamiltonian walk is any open sequence of edges of minimal length which includes every vertex of G . In this paper bounds of lengths of open Hamiltonian walks are studied.