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 条
  • [21] On the classification problem for split graphs
    Morais de Almeida, Sheila
    Picinin de Mello, Célia
    Morgana, Aurora
    Journal of the Brazilian Computer Society, 2012, 18 (02) : 95 - 101
  • [22] On local colorings of split graphs
    Shitov, Yaroslav
    ARKIV FOR MATEMATIK, 2023, 61 (01): : 203 - 210
  • [23] Token Sliding on Split Graphs
    Belmonte, Remy
    Kim, Eun Jung
    Lampis, Michael
    Mitsou, Valia
    Otachi, Yota
    Sikora, Florian
    36TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2019), 2019,
  • [24] Rainbow colouring of split graphs
    Chandran, L. Sunil
    Rajendraprasad, Deepak
    Tesar, Marek
    DISCRETE APPLIED MATHEMATICS, 2017, 216 : 98 - 113
  • [25] Hamiltonicity in Split Graphs - A Dichotomy
    Renjith, P.
    Sadagopan, N.
    ALGORITHMS AND DISCRETE APPLIED MATHEMATICS, 2017, 10156 : 320 - 331
  • [26] Token Sliding on Split Graphs
    Rémy Belmonte
    Eun Jung Kim
    Michael Lampis
    Valia Mitsou
    Yota Otachi
    Florian Sikora
    Theory of Computing Systems, 2021, 65 : 662 - 686
  • [27] On the shelling antimatroids of split graphs
    Cardinal, Jean
    Doignon, Jean-Paul
    Merckx, Keno
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2017, 19 (01)
  • [28] Vulnerability parameters of split graphs
    Li, Yinkui
    Zhang, Shenggui
    Zhang, Qilong
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2008, 85 (01) : 19 - 23
  • [29] Further split graphs known to be Class 1 and a characterization of subgraph-overfull split graphs
    Cararo, Cintia Izabel
    de Almeida, Sheila Morais
    da Silva, Candida Nunes
    DISCRETE APPLIED MATHEMATICS, 2024, 345 : 114 - 124
  • [30] Toughness and Hamiltonicity of a class of planar graphs
    Gerlach, T
    DISCRETE MATHEMATICS, 2004, 286 (1-2) : 61 - 65
12345