Path Decompositions of Kneser and Generalized Kneser Graphs

被引：3
|
作者：
Rodger, C. A. [1 ]
Whitt, Thomas Richard, III [1 ]
机构：
[1] Auburn Univ, Dept Math, Auburn, AL 36849 USA
来源：
CANADIAN MATHEMATICAL BULLETIN-BULLETIN CANADIEN DE MATHEMATIQUES | 2015年 / 58卷 / 03期
关键词：
Kneser graph; generalized Kneser graph; path decomposition; graph decomposition; GROUP-DIVISIBLE DESIGNS; SHORT PROOF; CONJECTURE;
D O I：
10.4153/CMB-2014-068-5
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Necessary and sufficient conditions are given for the existence of a graph decomposition of the Kneser Graph KG(n,2) and of the Generalized Kneser Graph GKG(n,3,1) into paths of length three.
引用
收藏
页码：610 / 619
页数：10
相关论文
共 50 条
  • [1] ON THE CHROMATIC NUMBER OF GENERALIZED KNESER GRAPHS
    Jafari, Amir
    Alipour, Sharareh
    CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2017, 12 (02) : 69 - 76
  • [2] The toughness of Kneser graphs
    Park, Davin
    Ostuni, Anthony
    Hayes, Nathan
    Banerjee, Amartya
    Wakhare, Tanay
    Wong, Wiseley
    Cioaba, Sebastian
    DISCRETE MATHEMATICS, 2021, 344 (09)
  • [3] Sparse Kneser Graphs Are Hamiltonian
    Muetze, Torsten
    Nummenpalo, Jerri
    Walczak, Bartosz
    STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 912 - 919
  • [4] Saturation in Kneser Graphs
    Vakhrushev, S. V.
    Zhukovskii, M. E.
    Skorkin, A. Yu.
    MATHEMATICAL NOTES, 2024, 116 (1-2) : 200 - 208
  • [5] Kneser graphs are Hamiltonian
    Merino, Arturo
    Muetze, Torsten
    Namrata
    ADVANCES IN MATHEMATICS, 2025, 468
  • [6] Kneser Graphs Are Hamiltonian
    Merino, Arturo
    Mutze, Torsten
    Namrata
    PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023, 2023, : 963 - 970
  • [7] Decomposition of the Kneser Graph into paths of length four
    Whitt, T. R., III
    Rodger, C. A.
    DISCRETE MATHEMATICS, 2015, 338 (08) : 1284 - 1288
  • [8] The energy of q-Kneser graphs and attenuated q-Kneser graphs
    Lv, Benjian
    Wang, Kaishun
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (13-14) : 2079 - 2083
  • [9] On random subgraphs of Kneser and Schrijver graphs
    Kupavskii, Andrey
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2016, 141 : 8 - 15
  • [10] L(2,1)-Labeling of Kneser graphs and coloring squares of Kneser graphs
    Shao, Zhendong
    Averbakh, Igor
    Solis-Oba, Roberto
    DISCRETE APPLIED MATHEMATICS, 2017, 221 : 106 - 114
12345