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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.