Decompositions of complete graphs into paths and cycles

Tay Woei Shyu

Decompositions of complete graphs into paths and cycles

Tay Woei Shyu^*

^*Corresponding author for this work

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

35 Citations (Scopus)

Abstract

Abstract. Let P_k+1 denote a path of length k and let C _k denote a cycle of length k. As usual K_n denotes the complete graph on n vertices. In this paper we investigate decompositions of K_n into paths and cycles, and give some necessary and/or sufficient conditions for such a decomposition to exist. Besides, we obtain a necessary and sufficient condition for decomposing K_n into p copies of P ₅ and q copies of C₄ for all possible values of p ≥ 0 and q ≥ 0.

Original language	English
Pages (from-to)	257-270
Number of pages	14
Journal	Ars Combinatoria
Volume	97
Publication status	Published - 2010 Oct

Keywords

Complete graph
Cycle
Graph decompositions
Path

ASJC Scopus subject areas

General Mathematics

Cite this

@article{a4fda896a443442ca89d393932b98542,

title = "Decompositions of complete graphs into paths and cycles",

abstract = "Abstract. Let Pk+1 denote a path of length k and let C k denote a cycle of length k. As usual Kn denotes the complete graph on n vertices. In this paper we investigate decompositions of Kn into paths and cycles, and give some necessary and/or sufficient conditions for such a decomposition to exist. Besides, we obtain a necessary and sufficient condition for decomposing Kn into p copies of P 5 and q copies of C4 for all possible values of p ≥ 0 and q ≥ 0.",

keywords = "Complete graph, Cycle, Graph decompositions, Path",

author = "Shyu, {Tay Woei}",

year = "2010",

month = oct,

language = "English",

volume = "97",

pages = "257--270",

journal = "Ars Combinatoria",

issn = "0381-7032",

publisher = "Charles Babbage Research Centre",

}

TY - JOUR

T1 - Decompositions of complete graphs into paths and cycles

AU - Shyu, Tay Woei

PY - 2010/10

Y1 - 2010/10

N2 - Abstract. Let Pk+1 denote a path of length k and let C k denote a cycle of length k. As usual Kn denotes the complete graph on n vertices. In this paper we investigate decompositions of Kn into paths and cycles, and give some necessary and/or sufficient conditions for such a decomposition to exist. Besides, we obtain a necessary and sufficient condition for decomposing Kn into p copies of P 5 and q copies of C4 for all possible values of p ≥ 0 and q ≥ 0.

AB - Abstract. Let Pk+1 denote a path of length k and let C k denote a cycle of length k. As usual Kn denotes the complete graph on n vertices. In this paper we investigate decompositions of Kn into paths and cycles, and give some necessary and/or sufficient conditions for such a decomposition to exist. Besides, we obtain a necessary and sufficient condition for decomposing Kn into p copies of P 5 and q copies of C4 for all possible values of p ≥ 0 and q ≥ 0.

KW - Complete graph

KW - Cycle

KW - Graph decompositions

KW - Path

UR - http://www.scopus.com/inward/record.url?scp=77958493788&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77958493788&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:77958493788

SN - 0381-7032

VL - 97

SP - 257

EP - 270

JO - Ars Combinatoria

JF - Ars Combinatoria

ER -

Decompositions of complete graphs into paths and cycles

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this