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 条
  • [41] On fractional (g, f, n)-critical graphs
    Liu, Shuli
    2011 INTERNATIONAL CONFERENCE ON COMPUTERS, COMMUNICATIONS, CONTROL AND AUTOMATION (CCCA 2011), VOL II, 2010, : 242 - 245
  • [42] ORTHOGONAL (g,f)-FACTORIZAFIONS OF BIPARTITE GRAPHS
    刘桂真
    董鹤年
    ActaMathematicaScientia, 2001, (03) : 316 - 322
  • [43] Some results on (g, f)-uniform graphs
    Cai, Jiansheng
    Ge, Liansheng
    UTILITAS MATHEMATICA, 2012, 89 : 203 - 210
  • [44] Some Sufficient Conditions for Graphs to Be (g, f, n)-Critical Graphs
    Zhou, Sizhong
    Liu, Hongxia
    Duan, Ziming
    IAENG TRANSACTIONS ON ENGINEERING TECHNOLOGIES VOL 1, 2009, 1089 : 178 - +
  • [45] Toughness and the existence of Hamiltonian [a, b]-factors of graphs
    Zhou, Sizhong
    UTILITAS MATHEMATICA, 2013, 90 : 187 - 197
  • [46] Binding Number and Wheel Related Graphs
    Aytac, Vecdi
    Berberler, Zeynep Nihan
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2017, 28 (01) : 29 - 38
  • [47] Connected (g, f)-factors
    Ellingham, MN
    Nam, Y
    Voss, HJ
    JOURNAL OF GRAPH THEORY, 2002, 39 (01) : 62 - 75
  • [48] A THEOREM ON FRACTIONAL ID-(g, f)-FACTOR-CRITICAL GRAPHS
    Zhou, Sizhong
    Sun, Zhiren
    Xu, Yang
    CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2015, 10 (02) : 31 - 38
  • [49] On the extremal number of edges in 2-factor Hamiltonian graphs
    Faudree, Ralph J.
    Gould, Ronald J.
    Jacobson, Michael S.
    GRAPH THEORY IN PARIS: PROCEEDINGS OF A CONFERENCE IN MEMORY OF CALUDE BERGE, 2007, : 139 - +
  • [50] Complete-factors and (g, f)-factors
    Li, JX
    Ma, YH
    DISCRETE MATHEMATICS, 2003, 265 (1-3) : 385 - 391