CLAW-DECOMPOSITION OF KNESER GRAPHS

被引：3
作者：
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 条
[41]   Circular chromatic numbers of some reduced Kneser graphs [J].
Lih, KW ;
Liu, DDF .
JOURNAL OF GRAPH THEORY, 2002, 41 (01) :62-68
[42]   Improved bounds on the chromatic numbers of the square of Kneser graphs [J].
Kim, Seog-Jin ;
Park, Boram .
DISCRETE MATHEMATICS, 2014, 315 :69-74
[43]   Mutual-visibility problems in Kneser and Johnson graphs [J].
Ekinci, Gulnaz Boruzanli ;
Bujtas, Csilla .
ARS MATHEMATICA CONTEMPORANEA, 2025, 25 (03)
[44]   On semi-transitive orientability of Kneser graphs and their complements [J].
Kitaev, Sergey ;
Saito, Akira .
DISCRETE MATHEMATICS, 2020, 343 (08)
[45]   Characterization of balanced graphs within claw-free graphs [J].
Busolini, Lucia ;
Duran, Guillermo ;
Safe, Martin D. .
XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023, 2023, 224 :258-266
[46]   Existence of a P2k+1-decomposition in the Kneser graph KGt,2 [J].
Ganesamurthy, S. ;
Paulraja, P. .
DISCRETE MATHEMATICS, 2018, 341 (07) :2113-2116
[47]   Non-cover generalized Mycielski, Kneser, and Schrijver graphs [J].
Lih, Ko-Wei ;
Lin, Chen-Ying ;
Tong, Li-Da .
DISCRETE MATHEMATICS, 2008, 308 (20) :4653-4659
[48]   First-Order Complexity of Subgraph Isomorphism via Kneser Graphs [J].
V. A. Voronov ;
E. A. Dergachev ;
M. E. Zhukovskii ;
A. M. Neopryatnaya .
Mathematical Notes, 2021, 109 :29-37
[49]   Short proof that Kneser graphs are Hamiltonian for n ≥ 4k [J].
Bellmann, Johann ;
Schulke, Bjarne .
DISCRETE MATHEMATICS, 2021, 344 (07)
[50]   Decomposition of complete graphs into paths and stars [J].
Shyu, Tay-Woei .
DISCRETE MATHEMATICS, 2010, 310 (15-16) :2164-2169
12345