A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs

Wojciech Wideł

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 1, page 173-184
  • ISSN: 2083-5892

Abstract

top
Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies [...] min⁡dG(u),dG(v)≥n+12 min { d G ( u ) , d G ( v ) } ≥ n + 1 2 . In this paper we prove that every 2-connected K1,3, P5-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying pancyclicity of 2-connected graphs.

How to cite

top

Wojciech Wideł. "A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs." Discussiones Mathematicae Graph Theory 36.1 (2016): 173-184. <http://eudml.org/doc/276967>.

@article{WojciechWideł2016,
abstract = {Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies [...] min⁡dG(u),dG(v)≥n+12 $\min \lbrace d_G (u),d_G (v)\rbrace \ge \{\{n + 1\} \over 2\}$ . In this paper we prove that every 2-connected K1,3, P5-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying pancyclicity of 2-connected graphs.},
author = {Wojciech Wideł},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {cycle; Fan-type heavy subgraph; Hamilton cycle; pancyclicity},
language = {eng},
number = {1},
pages = {173-184},
title = {A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs},
url = {http://eudml.org/doc/276967},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Wojciech Wideł
TI - A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 1
SP - 173
EP - 184
AB - Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies [...] min⁡dG(u),dG(v)≥n+12 $\min \lbrace d_G (u),d_G (v)\rbrace \ge {{n + 1} \over 2}$ . In this paper we prove that every 2-connected K1,3, P5-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying pancyclicity of 2-connected graphs.
LA - eng
KW - cycle; Fan-type heavy subgraph; Hamilton cycle; pancyclicity
UR - http://eudml.org/doc/276967
ER -

References

top
  1. [1] P. Bedrossian, Forbidden subgraph and Minimum Degree Conditions for Hamiltonicity, PhD Thesis (Memphis State University, USA, 1991). 
  2. [2] P. Bedrossian, G. Chen and R.H. Schelp, A generalization of Fan’s condition for Hamiltonicity, pancyclicity and Hamiltonian connectedness, Discrete Math. 115 (1993) 39–59. doi:10.1016/0012-365X(93)90476-A[Crossref] Zbl0773.05075
  3. [3] A. Benhocine and A.P. Wojda, The Geng-Hua Fan conditions for pancyclic or Hamilton-connected graphs, J. Combin. Theory Ser. B 58 (1987) 167–180. doi:10.1016/0095-8956(87)90038-4[Crossref] Zbl0613.05038
  4. [4] J.A. Bondy, Pancyclic graphs I, J. Combin. Theory Ser. B 11 (1971) 80–84. doi:10.1016/0095-8956(71)90016-5[Crossref] Zbl0183.52301
  5. [5] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan London and Elsevier, 1976). 
  6. [6] G. Fan, New su cient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1984) 221–227. doi:0.1016/0095-8956(84)90054-6 
  7. [7] M. Ferrara, M.S. Jacobson and A. Harris, Cycle lenghts in Hamiltonian graphs with a pair of vertices having large degree sum, Graphs Combin. 26 (2010) 215–223. doi:10.1007/s00373-010-0915-z[Crossref] Zbl1230.05179
  8. [8] B. Ning, Pairs of Fan-type heavy subgraphs for pancyclicity of 2-connected graphs, Australas. J. Combin. 58 (2014) 127–136. Zbl1296.05115
  9. [9] B. Ning and S. Zhang, Ore- and Fan-type heavy subgraphs for Hamiltonicity of 2-connected graphs, Discrete Math. 313 (2013) 1715–1725. doi:10.1016/j.disc.2013.04.023[Crossref] 
  10. [10] E.F. Schmeichel and S.L. Hakimi, A cycle structure theorem for Hamiltonian graphs, J. Combin. Theory Ser. B 45 (1988) 99–107. doi:10.1016/0095-8956(88)90058-5[Crossref] Zbl0607.05050

NotesEmbed ?

top

You must be logged in to post comments.