Decomposition of Complete Graphs into Cycles and Stars

Tay Woei Shyu

doi:10.1007/s00373-011-1105-3

Decomposition of Complete Graphs into Cycles and Stars

Tay Woei Shyu^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

38 Citations (Scopus)

Abstract

Let C_k denote a cycle of length k and let S_k denote a star with k edges. As usual K_n denotes the complete graph on n vertices. In this paper we investigate decomposition of K_n into C_l's and S_k's, and give some necessary or sufficient conditions for such a decomposition to exist. In particular, we give a complete solution to the problem in the case l = k = 4 as follows: For any nonnegative integers p and q and any positive integer n, there exists a decomposition of K_n into p copies of C₄ and q copies of S₄ if and only if 4(p + q) = q ≠ 1 if n is odd, and q ≥{3, n/2}if n is even.

Original language	English
Pages (from-to)	301-313
Number of pages	13
Journal	Graphs and Combinatorics
Volume	29
Issue number	2
DOIs	https://doi.org/10.1007/s00373-011-1105-3
Publication status	Published - 2013 Mar

Keywords

Complete graph
Cycle
Graph decomposition
Star

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-011-1105-3

Cite this

@article{65fbb86ad7d2415eb92d1c1d6e8060f5,

title = "Decomposition of Complete Graphs into Cycles and Stars",

abstract = "Let Ck denote a cycle of length k and let Sk denote a star with k edges. As usual Kn denotes the complete graph on n vertices. In this paper we investigate decomposition of Kn into Cl's and Sk's, and give some necessary or sufficient conditions for such a decomposition to exist. In particular, we give a complete solution to the problem in the case l = k = 4 as follows: For any nonnegative integers p and q and any positive integer n, there exists a decomposition of Kn into p copies of C4 and q copies of S4 if and only if 4(p + q) = q ≠ 1 if n is odd, and q ≥\{3, n/2\}if n is even.",

keywords = "Complete graph, Cycle, Graph decomposition, Star",

author = "Shyu, \{Tay Woei\}",

note = "Funding Information: This work was supported by the National Science Council of Taiwan (NSC 97-2115-M-003-006).",

year = "2013",

month = mar,

doi = "10.1007/s00373-011-1105-3",

language = "English",

volume = "29",

pages = "301--313",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "2",

}

TY - JOUR

T1 - Decomposition of Complete Graphs into Cycles and Stars

AU - Shyu, Tay Woei

N1 - Funding Information: This work was supported by the National Science Council of Taiwan (NSC 97-2115-M-003-006).

PY - 2013/3

Y1 - 2013/3

N2 - Let Ck denote a cycle of length k and let Sk denote a star with k edges. As usual Kn denotes the complete graph on n vertices. In this paper we investigate decomposition of Kn into Cl's and Sk's, and give some necessary or sufficient conditions for such a decomposition to exist. In particular, we give a complete solution to the problem in the case l = k = 4 as follows: For any nonnegative integers p and q and any positive integer n, there exists a decomposition of Kn into p copies of C4 and q copies of S4 if and only if 4(p + q) = q ≠ 1 if n is odd, and q ≥{3, n/2}if n is even.

AB - Let Ck denote a cycle of length k and let Sk denote a star with k edges. As usual Kn denotes the complete graph on n vertices. In this paper we investigate decomposition of Kn into Cl's and Sk's, and give some necessary or sufficient conditions for such a decomposition to exist. In particular, we give a complete solution to the problem in the case l = k = 4 as follows: For any nonnegative integers p and q and any positive integer n, there exists a decomposition of Kn into p copies of C4 and q copies of S4 if and only if 4(p + q) = q ≠ 1 if n is odd, and q ≥{3, n/2}if n is even.

KW - Complete graph

KW - Cycle

KW - Graph decomposition

KW - Star

UR - https://www.scopus.com/pages/publications/84874646637

UR - https://www.scopus.com/pages/publications/84874646637#tab=citedBy

U2 - 10.1007/s00373-011-1105-3

DO - 10.1007/s00373-011-1105-3

M3 - Article

AN - SCOPUS:84874646637

SN - 0911-0119

VL - 29

SP - 301

EP - 313

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 2

ER -

Decomposition of Complete Graphs into Cycles and Stars

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this