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 条
  • [41] Spectral Characterization of Families of Split Graphs
    Andelic, Milica
    Cardoso, Domingos M.
    GRAPHS AND COMBINATORICS, 2015, 31 (01) : 59 - 72
  • [42] On split graphs with four distinct eigenvalues
    Goldberg, Felix
    Kirkland, Steve
    Varghese, Anu
    Vijayakumar, Ambat
    DISCRETE APPLIED MATHEMATICS, 2020, 277 : 163 - 171
  • [43] Edge vulnerability parameters of split graphs
    Zhang, Qilong
    Zhang, Shenggui
    APPLIED MATHEMATICS LETTERS, 2006, 19 (09) : 916 - 920
  • [44] Note on enumeration of labeled split graphs
    Bina, Vladislav
    Pribil, Jiri
    COMMENTATIONES MATHEMATICAE UNIVERSITATIS CAROLINAE, 2015, 56 (02): : 133 - 137
  • [45] Toughness and isolated toughness conditions for P≥3-factor uniform graphs
    Hua, Hongbo
    JOURNAL OF APPLIED MATHEMATICS AND COMPUTING, 2021, 66 (1-2) : 809 - 821
  • [46] Algorithms for unipolar and generalized split graphs
    Eschen, Elaine M.
    Wang, Xiaoqiang
    DISCRETE APPLIED MATHEMATICS, 2014, 162 : 195 - 201
  • [47] Toughness and isolated toughness conditions for path-factor critical covered graphs
    Dai, Guowei
    RAIRO-OPERATIONS RESEARCH, 2023, 57 (02) : 847 - 856
  • [48] Some sufficient conditions on hamilton graphs with toughness
    Cai, Gaixiang
    Yu, Tao
    Xu, Huan
    Yu, Guidong
    FRONTIERS IN COMPUTATIONAL NEUROSCIENCE, 2022, 16
  • [49] The Overfull Conjecture on split-comparability and split-interval graphs
    da Soledade Gonzaga, Luis Gustavo
    de Sousa Cruz, Jadder Bismarck
    de Almeida, Sheila Morais
    da Silva, Candida Nunes
    DISCRETE APPLIED MATHEMATICS, 2023, 340 : 228 - 238
  • [50] STRENGTHENING SOME COMPLEXITY RESULTS ON TOUGHNESS OF GRAPHS
    Katona, Gyula Y.
    Varga, Kitti
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2023, 43 (02) : 401 - 419
12345