pith. machine review for the scientific record. sign in

arxiv: 1306.5316 · v2 · submitted 2013-06-22 · 🧮 math.CO

Recognition: unknown

Hamilton cycles in almost distance-hereditary graphs

Authors on Pith no claims yet
classification 🧮 math.CO
keywords graphalmostdistance-hereditaryheavyverticesclaw-heavyconnectedevery
0
0 comments X
read the original abstract

Let $G$ be a graph on $n\geq 3$ vertices. A graph $G$ is almost distance-hereditary if each connected induced subgraph $H$ of $G$ has the property $d_{H}(x,y)\leq d_{G}(x,y)+1$ for any pair of vertices $x,y\in V(H)$. A graph $G$ is called 1-heavy (2-heavy) if at least one (two) of the end vertices of each induced subgraph of $G$ isomorphic to $K_{1,3}$ (a claw) has (have) degree at least $n/2$, and called claw-heavy if each claw of $G$ has a pair of end vertices with degree sum at least $n$. Thus every 2-heavy graph is claw-heavy. In this paper we prove the following two results: (1) Every 2-connected, claw-heavy and almost distance-hereditary graph is Hamiltonian. (2) Every 3-connected, 1-heavy and almost distance-hereditary graph is Hamiltonian. In particular, the first result improves a previous theorem of Feng and Guo. Both results are sharp in some sense.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.