On the extremal number of edges in 2-factor Hamiltonian graphs

被引:4
作者
Faudree, Ralph J. [1 ]
Gould, Ronald J. [2 ]
Jacobson, Michael S. [3 ]
机构
[1] Univ Memphis, Off Provost, Memphis, TN 38152 USA
[2] Emory Univ, Dept Math & Comp Sci, Atlanta, GA 30322 USA
[3] Univ Colorado, Dept Math, Denver, CO 80217 USA
来源
GRAPH THEORY IN PARIS: PROCEEDINGS OF A CONFERENCE IN MEMORY OF CALUDE BERGE | 2007年
关键词
2-factor; Hamiltonian; size;
D O I
10.1007/978-3-7643-7400-6_11
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In this paper we consider the question of determining the maximum number of edges in a Hamiltonian graph of order n that contains no 2-factor with more than one cycle, that is, 2-factor Hamiltonian graphs. We obtain exact results for both bipartite graphs, and general graphs, and construct extremal graphs in each case.
引用
收藏
页码:139 / +
页数:2
相关论文
共 50 条
  • [21] On the 2-factor index of a graph
    Xiong, Liming
    Li, MingChu
    [J]. DISCRETE MATHEMATICS, 2007, 307 (21) : 2478 - 2483
  • [22] Cycle-Saturated Graphs with Minimum Number of Edges
    Fueredi, Zoltan
    Kim, Younjin
    [J]. JOURNAL OF GRAPH THEORY, 2013, 73 (02) : 203 - 215
  • [23] Binding number and Hamiltonian (g, f)-factors in graphs
    Cai J.
    Liu G.
    [J]. Journal of Applied Mathematics and Computing, 2007, 25 (1-2) : 383 - 388
  • [24] Forbidden Subgraphs and the Existence of a 2-Factor
    Aldred, R. E. L.
    Fujisawa, Jun
    Saito, Akira
    [J]. JOURNAL OF GRAPH THEORY, 2010, 64 (03) : 250 - 266
  • [25] A note on the 2-factor Hamiltonicity Conjecture
    Gorsky, Maximilian
    Johanni, Theresa
    Wiederrecht, Sebastian
    [J]. DISCRETE MATHEMATICS, 2025, 348 (06)
  • [26] The signless Laplacian spectral radius of graphs with a prescribed number of edges
    Zhai, Mingqing
    Xue, Jie
    Lou, Zhenzhen
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2020, 603 (603) : 154 - 165
  • [27] The structure of the 2-factor transfer digraph common for thin cylinder, torus and Klein bottle grid graphs
    Dokic, Jelena
    Doroslovacki, Ksenija
    Bodroza-Pantic, Olga
    [J]. FILOMAT, 2024, 38 (01) : 57 - 65
  • [28] THE STRUCTURE OF THE 2-FACTOR TRANSFER DIGRAPH COMMON FOR RECTANGULAR, THICK CYLINDER AND MOEBIUS STRIP GRID GRAPHS
    Dokic, Jelena
    Doroslovacki, Ksenija
    Bodroza-Pantic, Olga
    [J]. APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2023, 17 (01) : 120 - 137
  • [29] Binding number and Hamiltonian (g, f)-factors in graphs II
    Cai, Jiansheng
    Liu, Guizhen
    Hou, Jianfeng
    [J]. INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2008, 85 (09) : 1325 - 1331
  • [30] Local Dirac's condition on the existence of 2-factor
    Chen, Xiaodong
    Chen, Guantao
    [J]. DISCRETE MATHEMATICS, 2023, 346 (07)