pith. machine review for the scientific record. sign in

arxiv: 1506.02795 · v3 · submitted 2015-06-09 · 🧮 math.CO

Recognition: unknown

Heavy subgraphs, stability and hamiltonicity

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

Let $G$ be a graph. Adopting the terminology of Broersma et al. and \v{C}ada, respectively, we say that $G$ is 2-heavy if every induced claw ($K_{1,3}$) of $G$ contains two end-vertices each one has degree at least $|V(G)|/2$; and $G$ is o-heavy if every induced claw of $G$ contains two end-vertices with degree sum at least $|V(G)|$ in $G$. In this paper, we introduce a new concept, and say that $G$ is \emph{$S$-c-heavy} if for a given graph $S$ and every induced subgraph $G'$ of $G$ isomorphic to $S$ and every maximal clique $C$ of $G'$, every non-trivial component of $G'-C$ contains a vertex of degree at least $|V(G)|/2$ in $G$. In terms of this concept, our original motivation that a theorem of Hu in 1999 can be stated as every 2-connected 2-heavy and $N$-c-heavy graph is hamiltonian, where $N$ is the graph obtained from a triangle by adding three disjoint pendant edges. In this paper, we will characterize all connected graphs $S$ such that every 2-connected o-heavy and $S$-c-heavy graph is hamiltonian. Our work results in a different proof of a stronger version of Hu's theorem. Furthermore, our main result improves or extends several previous results.

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.