Claw-decomposition of Kneser Graphs

Document Type : Research Paper

Authors

1 Department of Mathematics, A. V. V. M. Sri Pushpam College(Affiliated to Bharathidasan University), Poondi, Than- javur, Tamil Nadu, India

2 Department of Mathematics, A. V. V. M. Sri Pushpam College( Affiliated to Bharathidasan University), Poondi, Than- javur, Tamil Nadu, India

Abstract

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 \geq 6$‎.

Keywords

Main Subjects

References

[1] Y. Chen, Kneser graphs are Hamiltonian for n ≥ 3k, J. Combin. Theory Ser. B, 80 (2000) 69–79.
[2] S. Ganesamurthy and P. Paulraja, Existence of a P2k+1 -decomposition in the Kneser graph KGn,2 , Discrete Math.,
341 (2018) 2113–2116.
[3] M. Kneser, Aufgabe 360, Jahresbericht der Deutschen Mathematiker-Vereinigung, 2 58 (1955) pp. 27.
[4] C. Lin, J.-J. Lin and T.-W. Shyu, Isomorphic star decomposition of multicrowns and the power of cycles, Ars
Combin., 53 (1999) 249–256.
[5] C. A. Rodger and T. R. Whitt III, Path decompositions of Kneser and generalized Kneser graphs, Canad. Math.
Bull., 58 (2015) 610–619.
[6] I. Shields and C. D. Savage, A note on Hamilton cycles in Kneser graphs, Bull. Inst. Combin. Appl., 40 (2004)
13–22.
[7] T. R. Whitt and C. A. Rodger, Decomposition of the Kneser graph into paths of length four, Discrete Math., 338
(2015) 1284–1288.
[8] S. Yamamoto, H. Ikeda, S. Shige-eda, K. Ushio and N. Hamada, On claw-decomposition of complete graphs and
complete bigraphs, Hiroshima Math. J., 5 (1975) 33–42.
Transactions on Combinatorics
Volume 11, Issue 1
March 2022
Pages 53-61

Files

Cited by

History

  • Receive Date: 05 December 2020
  • Revise Date: 07 October 2021
  • Accept Date: 16 October 2021
  • Published Online: 01 March 2022

Share

How to cite

Statistics