The toughness of split graphs

被引：21
|
作者：
Woeginger, GJ [1 ]
机构：
[1] Graz Tech Univ, Inst Math B, A-8010 Graz, Austria
来源：
DISCRETE MATHEMATICS | 1998年 / 190卷 / 1-3期
关键词：
graph algorithm; split graph; toughness; Hamiltonian cycle;
D O I：
10.1016/S0012-365X(98)00156-3
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In this short note we argue that the toughness of split graphs can be computed in polynomial time. This solves an open problem from a recent paper by Kratsch et al. (Discrete Math. 150 (1996) 231-245). (C) 1998 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：295 / 297
页数：3
相关论文
共 50 条
  • [1] Polynomial algorithms for computing the isolated toughness of interval and split graphs
    Li, Fengwei
    Ye, Qingfang
    Broersma, Hajo
    Zhang, Xiaoyan
    CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, 2023, 35 (17)
  • [2] Vulnerability issues of star graphs, alternating group graphs and split-stars: strength and toughness
    Cheng, E
    Lipman, MJ
    DISCRETE APPLIED MATHEMATICS, 2002, 118 (03) : 163 - 179
  • [3] Toughness, hamiltonicity and spectral radius in graphs
    Fan, Dandan
    Lin, Huiqiu
    Lu, Hongliang
    EUROPEAN JOURNAL OF COMBINATORICS, 2023, 110
  • [4] Retractions of split graphs and End-orthodox split graphs
    Fan, SH
    DISCRETE MATHEMATICS, 2002, 257 (01) : 161 - 164
  • [5] Toughness in Graphs – A Survey
    Douglas Bauer
    Hajo Broersma
    Edward Schmeichel
    Graphs and Combinatorics, 2006, 22 : 1 - 35
  • [6] The toughness of Kneser graphs
    Park, Davin
    Ostuni, Anthony
    Hayes, Nathan
    Banerjee, Amartya
    Wakhare, Tanay
    Wong, Wiseley
    Cioaba, Sebastian
    DISCRETE MATHEMATICS, 2021, 344 (09)
  • [7] Toughness in graphs - A survey
    Bauer, D
    Broersma, H
    Schmeichel, E
    GRAPHS AND COMBINATORICS, 2006, 22 (01) : 1 - 35
  • [8] TOUGHNESS, ISOLATED TOUGHNESS AND PATH FACTORS IN GRAPHS
    Zhou, Sizhong
    Wu, Jiancheng
    Xu, Yang
    BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2022, 106 (02) : 195 - 202
  • [9] A note on the approximability of the toughness of graphs
    Bazgan, C
    DISCRETE MATHEMATICS, 2004, 280 (1-3) : 215 - 218
  • [10] Toughness of Kronecker product of graphs
    Guji, Raxida
    Ali, Tursun
    ARS COMBINATORIA, 2016, 127 : 149 - 156
12345