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 条
  • [1] 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
  • [2] Minimal graphs for 2-factor extension
    Costa, M-C
    de Werra, D.
    Picouleau, C.
    DISCRETE APPLIED MATHEMATICS, 2020, 282 : 65 - 79
  • [3] Forbidden pairs of disconnected graphs for 2-factor of connected graphs
    Holub, Premysl
    Ryjacek, Zdenek
    Vrana, Petr
    Wang, Shipeng
    Xiong, Liming
    JOURNAL OF GRAPH THEORY, 2022, 100 (02) : 209 - 231
  • [4] Characterizing P≥2-factor and P≥2-factor covered graphs with respect to the size or the spectral radius
    Li, Shuchao
    Miao, Shujing
    DISCRETE MATHEMATICS, 2021, 344 (11)
  • [5] Pseudo 2-factor isomorphic regular bipartite graphs
    Abreu, M.
    Diwan, A. A.
    Jackson, Bill
    Labbate, D.
    Sheehan, J.
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (02) : 432 - 442
  • [6] Closure, stability and iterated line graphs with a 2-factor
    Saito, Akira
    Xiong, Liming
    DISCRETE MATHEMATICS, 2009, 309 (16) : 5000 - 5010
  • [7] Best Monotone Degree Condition for the Hamiltonicity of Graphs with a 2-Factor
    D. Bauer
    A. Nevo
    E. Schmeichel
    Graphs and Combinatorics, 2017, 33 : 1231 - 1248
  • [8] On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance
    Chen, Shih-Yan
    Kao, Shin-Shin
    Su, Hsun
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2016, 17 (03) : 307 - 314
  • [9] On a simple randomized algorithm for finding a 2-factor in sparse graphs
    Pandurangan, G
    INFORMATION PROCESSING LETTERS, 2005, 95 (01) : 321 - 327
  • [10] On the number of edges in some graphs
    Lai, Chunhui
    DISCRETE APPLIED MATHEMATICS, 2020, 283 : 751 - 755
12345