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 条
  • [31] Toughness and Hamiltonicity of strictly chordal graphs
    Markenzon, Lilian
    Waga, Christina F. E. M.
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2019, 26 (02) : 725 - 731
  • [32] Toughness and normalized Laplacian eigenvalues of graphs
    Huang, Xueyi
    Das, Kinkar Chandra
    Zhu, Shunlai
    APPLIED MATHEMATICS AND COMPUTATION, 2022, 425
  • [33] Toughness and (a, b, k)-critical graphs
    Zhou, Sizhong
    Jiang, Jiashang
    INFORMATION PROCESSING LETTERS, 2011, 111 (09) : 403 - 407
  • [34] Radio labeling of biconvex split graphs
    Sethuraman, G.
    Nithya, M.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2025, 22 (01) : 36 - 42
  • [35] POTENTIALLY GRAPHIC SEQUENCES OF SPLIT GRAPHS
    Pirzada, S.
    Chat, Bilal A.
    KRAGUJEVAC JOURNAL OF MATHEMATICS, 2014, 38 (01): : 73 - 81
  • [36] Edge-Coloring of Split Graphs
    de Almeida, Sheila Morais
    de Mello, Celia Picinin
    Morgana, Aurora
    ARS COMBINATORIA, 2015, 119 : 363 - 375
  • [37] On-line Ranking of Split Graphs
    Borowiecki, Piotr
    Dereniowski, Dariusz
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2013, 15 (02) : 195 - 214
  • [38] Spectral Characterization of Families of Split Graphs
    Milica Anđelić
    Domingos M. Cardoso
    Graphs and Combinatorics, 2015, 31 : 59 - 72
  • [39] Word-representability of split graphs
    Kitaev, Sergey
    Long, Yangjing
    Ma, Jun
    Wu, Hehui
    JOURNAL OF COMBINATORICS, 2021, 12 (04) : 725 - 746
  • [40] Quasi-kernels in split graphs
    Langlois, Helene
    Meunier, Frederic
    Rizzi, Romeo
    Vialette, Stephane
    Zhou, Yacong
    DISCRETE APPLIED MATHEMATICS, 2025, 361 : 236 - 243
12345