Stability Results on the Circumference of a Graph

被引:15
作者
Ma, Jie [1 ]
Ning, Bo [2 ]
机构
[1] Univ Sci & Technol China, Sch Math Sci, Hefei 230026, Anhui, Peoples R China
[2] Tianjin Univ, Ctr Appl Math, Tianjin 300072, Peoples R China
基金
中国国家自然科学基金;
关键词
MAXIMAL CIRCUITS; CYCLES; ERDOS; THEOREM; PATHS;
D O I
10.1007/s00493-019-3843-4
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In this paper, we extend and refine previous Turan-type results on graphs with a given circumference. Let W-n,W- k,W- c be the graph obtained from a clique Kc - k + 1 by adding n - (c - k +1) isolated vertices each joined to the same k vertices of the clique, and let f(n, k, c) = e(W-n,W- k,W- c). Improving a celebrated theorem of Erdos and Gallai [8], Kopylov [18] proved that for c < n, any 2-connected graph G on n vertices with circumference c has at most max{f(n,2,c),f(n,Lc2<SIC> RIGHT FLOOR,c)} edges, with equality if and only if G is isomorphic to W-n,W-2,W-c or Wn,Lc2<SIC> RIGHT FLOOR,c. Recently, Furedi et al. [15,14] proved a stability version of Kopylov's theorem. Their main result states that if G is a 2-connected graph on n vertices with circumference c such that 10 <= c < n and e(G)>max{f(n,3,c),f(n,Lc2<SIC> RIGHT FLOOR-1,c)}, or c is odd and G is a subgraph of a member of two well-characterized families which we define as chi(n,c) and gamma(n,c). We prove that if G is a 2-connected graph on n vertices with minimum degree at least k and circumference c such that 10 <= c < n and Wn,Lc2<SIC> RIGHT FLOOR,c = 2, is odd, and is a subgraph of a member of ?gamma, or >= 3 and is a subgraph of the union of a clique +1 and some cliques +1's, where any two cliques share the same two vertices. This provides a unified generalization of the above result of Furedi et al. [15,14] as well as a recent result of Li et al. [20] and independently, of Furedi et al. [12] on non-Hamiltonian graphs. A refinement and some variants of this result are also obtained. Moreover, we prove a stability result on a classical theorem of Bondy [2] on the circumference. We use a novel approach, which combines several proof ideas including a closure operation and an edge-switching technique. We will also discuss some potential applications of this approach for future research.
引用
收藏
页码:105 / 147
页数:43
相关论文
共 50 条
  • [31] Some further results on the stability of Ky Fan's points
    Xiang, Shuwen
    He, Jihao
    Liu, Chengwei
    Jia, Wensheng
    Yang, Yanlong
    JOURNAL OF INEQUALITIES AND APPLICATIONS, 2017,
  • [32] Stability in the Erdos-Gallai Theorem on cycles and paths, II
    Furedi, Zoltan
    Kostochka, Alexandr
    Luo, Ruth
    Verstraete, Jacques
    DISCRETE MATHEMATICS, 2018, 341 (05) : 1253 - 1263
  • [33] Coverings of the vertices of a graph by small cycles
    Forge, David
    Kouider, Mekkia
    GRAPHS AND COMBINATORICS, 2007, 23 (02) : 135 - 143
  • [34] Automata Resulting From Graph Operations
    Julie, J.
    Babujee, J. Baskar
    2012 FOURTH INTERNATIONAL CONFERENCE ON ADVANCED COMPUTING (ICOAC), 2012,
  • [35] Graph partition problems into cycles and paths
    Enomoto, H
    DISCRETE MATHEMATICS, 2001, 233 (1-3) : 93 - 101
  • [36] b-Chromatic sum of a graph
    Lisna, P. C.
    Sunitha, M. S.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2015, 7 (04)
  • [37] Coverings of the Vertices of a Graph by Small Cycles
    David Forge
    Mekkia Kouider
    Graphs and Combinatorics, 2007, 23 : 135 - 143
  • [38] Covering mappings and Ulam-Hyers stability results for coincidence problems
    Mlesnite, Oana
    CARPATHIAN JOURNAL OF MATHEMATICS, 2015, 31 (01) : 97 - 104
  • [39] Global Stability Results for Switched Systems Based on Weak Lyapunov Functions
    Mancilla-Aguilar, Jose L.
    Haimovich, Hernan
    Garcia, Rafael A.
    IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2017, 62 (06) : 2764 - 2777
  • [40] ALTERNATING AND SYMMETRIC GROUPS WITH EULERIAN GENERATING GRAPH
    Lucchini, Andrea
    Marion, Claude
    FORUM OF MATHEMATICS SIGMA, 2017, 5