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.