Spectral radius, edge-disjoint cycles and cycles of the same length

被引:10
作者
Lin, Huiqiu [1 ]
Zhai, Mingqing [2 ]
Zhao, Yanhua [1 ]
机构
[1] East China Univ Sci & Technol, Sch Math, Shanghai 200237, Peoples R China
[2] Chuzhou Univ, Sch Math & Finance, Chuzhou 239012, Anhui, Peoples R China
关键词
ODD CYCLES; GRAPHS; NUMBER; CLIQUES;
D O I
10.37236/10783
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In this paper, we provide spectral conditions for the existence of two edge-disjoint cycles and two cycles of the same length in a graph, which can be viewed as the spectral analogues of Erdos and Posa's condition and Erdos' classic problem about the maximum number of edges of a graph without two edge-disjoint cycles and two cycles of the same length, respectively. Furthermore, we give a spectral condition to guarantee the existence of k edge-disjoint triangles in a graph.
引用
收藏
页数:26
相关论文
共 50 条
  • [21] Parallel algorithm for shortest pairs of edge-disjoint paths
    Banerjee, S
    Ghosh, RK
    Reddy, APK
    [J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1996, 33 (02) : 165 - 171
  • [22] Edge Irregular k-labeling for Disjoint Union of Cycles and Generalized Prisms
    Hasni, R.
    Tarawneh, I
    Siddiqui, M. K.
    Raheem, A.
    Asim, M. A.
    [J]. MALAYSIAN JOURNAL OF MATHEMATICAL SCIENCES, 2021, 15 (01): : 79 - 90
  • [23] AN APPROXIMATION ALGORITHM FOR FULLY PLANAR EDGE-DISJOINT PATHS
    Huang, Chien-Chung
    Mari, Mathieu
    Mathieu, Claire
    Schewior, Kevin
    Vygen, Jens
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (02) : 752 - 769
  • [24] DISJOINT CYCLES IN A DIGRAPH WITH PARTIAL DEGREE
    Wang, Hong
    Wang, Yun
    Yan, Jin
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (01) : 221 - 232
  • [25] On the saturation spectrum of the unions of disjoint cycles
    Ma, Yue
    [J]. DISCRETE MATHEMATICS, 2025, 348 (06)
  • [26] A Blossom Algorithm for Maximum Edge-Disjoint T-Paths
    Iwata, Satoru
    Yokoi, Yu
    [J]. PROCEEDINGS OF THE 2020 ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2020, : 1933 - 1944
  • [27] FINDING MAXIMUM EDGE-DISJOINT PATHS BETWEEN MULTIPLE TERMINALS
    Iwata, Satoru
    Yokoi, Yu
    [J]. SIAM JOURNAL ON COMPUTING, 2023, 52 (05) : 1230 - 1268
  • [28] A TIGHT LOWER BOUND FOR EDGE-DISJOINT PATHS ON PLANAR DAGS*
    Chitnis, Rajesh
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (02) : 556 - 572
  • [29] Three Edge-Disjoint Plane Spanning Paths in a Point Set
    Kindermann, P.
    Kratochvil, J.
    Liotta, G.
    Valtr, P.
    [J]. GRAPH DRAWING AND NETWORK VISUALIZATION, GD 2023, PT I, 2023, 14465 : 323 - 338
  • [30] A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
    Chuzhoy, Julia
    Li, Shi
    [J]. JOURNAL OF THE ACM, 2016, 63 (05)