×

On vertices enforcing a Hamiltonian cycle. (English) Zbl 1293.05205

Summary: A nonempty vertex set \(X\subseteq V(G)\) of a Hamiltonian graph \(G\) is called an \(H\)-force of \(G\) if every \(X\)-cycle of \(G\) (i.e. a cycle of \(G\) containing all vertices of \(X\)) is Hamiltonian. The \(H\)-force number \(h(G)\) of a graph \(G\) is defined to be the smallest cardinality of an \(H\)-force set of \(G\). In the paper the study of this parameter is introduced and its value or a lower bound for outerplanar graphs, planar graphs, \(k\)-connected graphs and prisms over graphs is determined.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI