Back to Search
Start Over
Solution to a problem on hamiltonicity of graphs under Ore- and Fan-type heavy subgraph conditions
- Source :
- Graphs Combin. 32 (2016), no. 3, 1125--1135
- Publication Year :
- 2014
-
Abstract
- A graph $G$ is called \emph{claw-o-heavy} if every induced claw ($K_{1,3}$) of $G$ has two end-vertices with degree sum at least $|V(G)|$ in $G$. For a given graph $R$, $G$ is called \emph{$R$-f-heavy} if for every induced subgraph $H$ of $G$ isomorphic to $R$ and every pair of vertices $u,v\in V(H)$ with $d_H(u,v)=2$, there holds $\max\{d(u),d(v)\}\geq |V(G)|/2$. In this paper, we prove that every 2-connected claw-\emph{o}-heavy and $Z_3$-\emph{f}-heavy graph is hamiltonian (with two exceptional graphs), where $Z_3$ is the graph obtained from identifying one end-vertex of $P_4$ (a path with 4 vertices) with one vertex of a triangle. This result gives a positive answer to a problem proposed in [B. Ning, S. Zhang, Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs, Discrete Math. 313 (2013) 1715--1725], and also implies two previous theorems of Faudree et al. and Chen et al., respectively.<br />Comment: 12 pages, Accepted version for publication in Graphs and Combinatorics. arXiv admin note: text overlap with arXiv:1506.02795
- Subjects :
- Mathematics - Combinatorics
05C38, 05C45
Subjects
Details
- Database :
- arXiv
- Journal :
- Graphs Combin. 32 (2016), no. 3, 1125--1135
- Publication Type :
- Report
- Accession number :
- edsarx.1409.3325
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1007/s00373-015-1619-1