Binding number and Hamiltonian (g, f)-factors in graphs II

被引:1
|
作者
Cai, Jiansheng [2 ]
Liu, Guizhen [1 ]
Hou, Jianfeng [1 ]
机构
[1] Shandong Univ, Sch Math & Syst Sci, Jinan 250100, Peoples R China
[2] Weifang Univ, Sch Math & Informat Sci, Weifang 261061, Peoples R China
关键词
(g; f)-factor; Hamiltonian; binding number; computer science;
D O I
10.1080/00207160701524368
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A (g, f)-factor F of a graph G is called a Hamiltonian (g, f)-factor if F contains a Hamiltonian cycle. For a subset X of V(G), let N-G(X) = boolean OR(x is an element of X) N-G(x). The binding number of G is defined by bind(G) = min{vertical bar N-G(X)vertical bar/vertical bar X vertical bar vertical bar empty set not equal X subset of V(G), N-G(X) not equal V(G)}. Let G be a connected graph of order n, 3 <= a <= b be integers, and b >= 4. Let g, f be positive integer-valued functions defined on V(G), such that a <= g(x) <= f(x) <= b for every x is an element of V(G). Suppose n >= (a+b-4)(2)/(a-2) and f(V(G)) is even, we shall prove that if bind(G) > ((a+b-4)(n-1))/((a-2)n-(5/2)(a+b-4)) and for any independent set X subset of V(G), N-G(X) >= ((b-3)n + (2a+2b-9)vertical bar X vertical bar)/(a+b-5), then G has a Hamiltonian (g, f)-factor.
引用
收藏
页码:1325 / 1331
页数:7
相关论文
共 50 条
  • [21] A DEGREE CONDITION FOR GRAPHS TO HAVE CONNECTED (g, f)-FACTORS
    Zhou, S.
    Liu, H.
    Xu, Y.
    BULLETIN OF THE IRANIAN MATHEMATICAL SOCIETY, 2009, 35 (01) : 199 - 209
  • [22] Independence Number and Minimum Degree for the Existence of (g, f, n)-Critical Graphs
    Zhou, Sizhong
    Pan, Quanru
    Xu, Yang
    ANALELE STIINTIFICE ALE UNIVERSITATII OVIDIUS CONSTANTA-SERIA MATEMATICA, 2011, 19 (01): : 373 - 381
  • [23] Binding Number and Fractional k-Factors of Graphs
    Zhou, Sizhong
    Xu, Zurun
    Duan, Ziming
    ARS COMBINATORIA, 2011, 102 : 473 - 481
  • [24] ALL FRACTIONAL (g, f) -FACTORS IN GRAPHS
    Sun, Zhiren
    Zhou, Sizhong
    PROCEEDINGS OF THE ROMANIAN ACADEMY SERIES A-MATHEMATICS PHYSICS TECHNICAL SCIENCES INFORMATION SCIENCE, 2019, 20 (04): : 323 - 327
  • [25] On the Extremal Number of Edges in Hamiltonian Graphs
    Ho, Tung-Yang
    Lin, Cheng-Kuan
    Tan, Jimmy J. M.
    Hsu, D. Frank
    Hsu, Lih-Hsing
    JOURNAL OF INFORMATION SCIENCE AND ENGINEERING, 2011, 27 (05) : 1659 - 1665
  • [26] (g,f)-FACTORS WITH SPECIAL PROPERTIES IN BIPARTITE (mg,mf)-GRAPHS
    Bian Qiuju Liu GuizhenSchool of Mathematics and System Science
    AppliedMathematics:AJournalofChineseUniversities, 2004, (02) : 133 - 139
  • [27] (g,f)-Factors with special properties in bipartite (mg, mf)-graphs
    Bian Q.
    Liu G.
    Applied Mathematics-A Journal of Chinese Universities, 2004, 19 (2) : 133 - 139
  • [28] A Sufficient Condition for the Existence of Restricted Fractional (g, f)-Factors in Graphs
    Zhou, S.
    Sun, Z.
    Pan, Q.
    PROBLEMS OF INFORMATION TRANSMISSION, 2020, 56 (04) : 332 - 344
  • [29] A NEIGHBORHOOD CONDITION FOR GRAPHS TO HAVE RESTRICTED FRACTIONAL (g, f)-FACTORS
    Zhou, Sizhong
    Sun, Zhiren
    CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2021, 16 (01) : 138 - 149
  • [30] On (g, f)-Uniform Graphs
    Gui-zhen Liu~1
    Acta Mathematicae Applicatae Sinica(English Series), 2005, (01) : 67 - 76