On the length of longest chordless cycles

被引：0
作者：
Van Nuffelen C. [1 ]
Van Rompay K. [1 ]
机构：
[1] University of Antwerp, 2000 Antwerp
来源：
4OR | 2005年 / 3卷 / 2期
关键词：
Adjacency matrix; Cycle; Eigenvalues; Rank;
D O I：
10.1007/s10288-005-0062-1
中图分类号：
学科分类号：
摘要：
Upper bounds for the length of a longest (circuit) cycle without chords in a (directed) graph are given in terms of the rank of the adjacency matrix and in terms of its eigenvalues. © Springer-Verlag 2005.
引用
收藏
页码：133 / 138
页数：5
相关论文
共 50 条
[31]   Vertex-disjoint cycles of length at most four each of which contains a specified vertex [J].
Ishigami, Y .
JOURNAL OF GRAPH THEORY, 2001, 37 (01) :37-47
[32]   On acyclic 4-choosability of planar graphs without cycles of length 4, 7 and 9 [J].
He, Yanfang ;
Chen, Min ;
Sun, Yingcai .
DISCRETE MATHEMATICS, 2021, 344 (08)
[33]   GENERALIZED INVERSES OF CYCLES [J].
Pavlikova, Sona ;
Krivonakova, Nada .
MATHEMATICS, INFORMATION TECHNOLOGIES AND APPLIED SCIENCES 2018, 2018, :110-117
[34]   Loopless algorithms to generate maximum length gray cycles wrt. k-character substitutions [J].
Neraud, Jean .
THEORETICAL COMPUTER SCIENCE, 2023, 977
[35]   (1,0,0)-colorability of planar graphs without cycles of length 4, 5 or 9 [J].
Wang, Yingqian ;
Yang, Yaochou .
DISCRETE MATHEMATICS, 2014, 326 :44-49
[36]   Planar graphs with cycles of length neither 4 nor 7 are (3,0,0)-colorable [J].
Li, Huihui ;
Xu, Jinghan ;
Wang, Yingqian .
DISCRETE MATHEMATICS, 2014, 327 :29-35
[37]   Planar graphs with cycles of length neither 4 nor 6 are (2,0,0)-colorable [J].
Wang, Yingqian ;
Xu, Jinghan .
INFORMATION PROCESSING LETTERS, 2013, 113 (18) :659-663
[38]   A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs [J].
Zhang, Zhiyuan ;
Zhao, Yanhua .
DISCRETE MATHEMATICS, 2023, 346 (06)
[39]   On the (3,1)-choosability of planar graphs without adjacent cycles of length 5, 6, 7 [J].
Wang, Yue ;
Wu, Jianliang ;
Yang, Donglei .
DISCRETE MATHEMATICS, 2019, 342 (06) :1782-1791
[40]   Approximating the longest paths in grid graphs [J].
Zhang, Wen-Qi ;
Liu, Yong-Jin .
THEORETICAL COMPUTER SCIENCE, 2011, 412 (39) :5340-5350
12345