PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 1 | 173-184
Tytuł artykułu

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

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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)\} \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.
Słowa kluczowe
Wydawca
Rocznik
Tom
36
Numer
1
Strony
173-184
Opis fizyczny
Daty
wydano
2016-02-01
otrzymano
2014-12-10
poprawiono
2015-05-28
zaakceptowano
2015-05-28
online
2016-01-19
Twórcy
  • AGH University of Science and Technology Faculty of Applied Mathematics Department of Discrete Mathematics al. A. Mickiewicza 30, 30-059 Kraków, Poland, widel@agh.edu.pl
Bibliografia
  • [1] P. Bedrossian, Forbidden subgraph and Minimum Degree Conditions for Hamiltonicity, PhD Thesis (Memphis State University, USA, 1991).
  • [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]
  • [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]
  • [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]
  • [5] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan London and Elsevier, 1976).
  • [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] 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]
  • [8] B. Ning, Pairs of Fan-type heavy subgraphs for pancyclicity of 2-connected graphs, Australas. J. Combin. 58 (2014) 127–136.
  • [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] 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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1840
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.