The Chvátal-Erdős condition for prism-Hamiltonicity

DOI10.1016/J.DISC.2019.111709MaRDI QIDQ2182179zbMATH OpenOpenAlexFDO

Authors Pouria Salehi Nowbandegani, M. N. Ellingham

Publication date 21 May 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.02894

zbMATH Keywords

Chvátal-Erdős conditionconnectivityindependence numberprism-Hamiltonian

Mathematics Subject Classification ID

Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Abstract: The prism over a graph $G$ is the cartesian product $GBox{K}_2$. It is known that the property of having a Hamiltonian prism (prism-Hamiltonicity) is stronger than that of having a $2$-walk (spanning closed walk using every vertex at most twice) and weaker than that of having a Hamilton path. For a graph $G$, it is known that $alpha(G)leq2kappa(G)$, where $alpha(G)$ is the independence number and $kappa(G)$ is the connectivity, imples existence of a $2$-walk in $G$, and the bound is sharp. West asked for a bound on $alpha(G)$ in terms of $kappa(G)$ guaranteeing prism-Hamiltonicity. In this paper we answer this question and prove that $alpha(G)leq2kappa(G)$ implies the stronger condition, prism-Hamiltonicity of $G$.

Recommendations

• Hamilton cycles in prisms
• A degree sum condition for graphs to be prism Hamiltonian
• Prism‐hamiltonicity of triangulations
• Toughness and prism-Hamiltonicity of \(P_4\)-free graphs
• A characterization of Hamiltonian prisms

Cites work

• A note on Hamiltonian circuits
• Cycles through specified vertices of a graph
• Hamilton cycles in prisms
• Hamiltonian cycles in the cartesian product of a tree and a cycle
• Hamiltonian decompositions of prisms over cubic graphs
• scientific article; zbMATH DE number 68918 (Why is no real title available?)
• On a connection between the existence of k-trees and the toughness of a graph
• Spanning trees and spanning Eulerian subgraphs with small degrees
• Tough graphs and Hamiltonian circuits.
• Toughness, trees, and walks

Cited in

(7)

• A degree sum condition for graphs to be prism Hamiltonian
• On the Hamiltonian property hierarchy of 3-connected planar graphs
• Closure for the property of having a hamiltonian prism
• Hamiltonicity and pancyclicity of generalized prisms
• scientific article; zbMATH DE number 1109394 (Why is no real title available?)
• Hamilton cycles in prisms
• Toughness and prism-Hamiltonicity of \(P_4\)-free graphs

This page was built for publication: The Chvátal-Erdős condition for prism-Hamiltonicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2182179)