CLAW-DECOMPOSITION OF KNESER GRAPHS

被引：1
|
作者：
Sankari, C. [1 ]
Sangeetha, R. [1 ]
Arthi, K. [1 ]
机构：
[1] Bharathidasan Univ, AVVM Sri Pushpam Coll, Dept Math, Thanjavur, Tamil Nadu, India
来源：
TRANSACTIONS ON COMBINATORICS | 2022年 / 11卷 / 01期
关键词：
Decomposition; Tensor Product; Kneser Graph; Crown Graph; Star;
D O I：
10.22108/TOC.2021.126283.1792
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A claw is a star with three edges. The Kneser graph KG(n,2 )is the graph whose vertices are the 2-subsets of an n-set, in which two vertices are adjacent if and only if their intersection is empty. In this paper, we prove that KG(n,2) is claw-decomposable, for all n >= 6.
引用
收藏
页码：53 / 61
页数：9
相关论文
共 50 条
  • [1] The toughness of Kneser graphs
    Park, Davin
    Ostuni, Anthony
    Hayes, Nathan
    Banerjee, Amartya
    Wakhare, Tanay
    Wong, Wiseley
    Cioaba, Sebastian
    DISCRETE MATHEMATICS, 2021, 344 (09)
  • [2] Path Decompositions of Kneser and Generalized Kneser Graphs
    Rodger, C. A.
    Whitt, Thomas Richard, III
    CANADIAN MATHEMATICAL BULLETIN-BULLETIN CANADIEN DE MATHEMATIQUES, 2015, 58 (03): : 610 - 619
  • [3] Saturation in Kneser Graphs
    Vakhrushev, S. V.
    Zhukovskii, M. E.
    Skorkin, A. Yu.
    MATHEMATICAL NOTES, 2024, 116 (1-2) : 200 - 208
  • [4] Kneser graphs are Hamiltonian
    Merino, Arturo
    Muetze, Torsten
    Namrata
    ADVANCES IN MATHEMATICS, 2025, 468
  • [5] 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
  • [6] The energy of q-Kneser graphs and attenuated q-Kneser graphs
    Lv, Benjian
    Wang, Kaishun
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (13-14) : 2079 - 2083
  • [7] 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
  • [8] The equitable colorings of Kneser graphs
    Chen, Bor-Liang
    Huang, Kuo-Ching
    TAIWANESE JOURNAL OF MATHEMATICS, 2008, 12 (04): : 887 - 900
  • [9] 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
  • [10] The determining number of Kneser graphs
    Caceres, Jose
    Garijo, Delia
    Gonzalez, Antonio
    Marquez, Alberto
    Luiz Puertas, Maria
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2013, 15 (01): : 1 - 14
12345