CLAW-DECOMPOSITION OF THE KNESER GRAPH KG_(n,3)
CLAW-DECOMPOSITION OF THE KNESER GRAPH KG_(n,3)
C. Sankari, R. Sangeetha, K. Arthi
[PDF]
Abstract
The Kneser graph KGn,3 is the graph whose vertices are the 3-element subsets of n-elements, in which two vertices are adjacent if and only if their intersection is empty. A claw is a star with three edges. In this paper, we prove that KGn,3 is claw-decomposable if and only if n ≥ 9 and n ≡ 0, 1, 2, 3, 4, 5(mod 9).
Keywords
Decomposition, Kneser Graph, Star, Complete Bipartite Graph, Induced Subgraph.