Decompositions of complete graphs into blown-up cycles Cm [2]

Dalibor Fronček; Petr Kovář; Michael Kubesa

doi:10.1016/j.disc.2009.10.018

Decompositions of complete graphs into blown-up cycles C_m [2]

Dalibor Fronček, Petr Kovář, Michael Kubesa

Mathematics & Statistics

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

1 Scopus citations

Abstract

Let C_m [over(K, -)₂] stand for a cycle C_m in which every vertex is replaced by two isolated vertices and every edge by K_{2, 2}. We prove that the complete graph K_{8 m k + 1} can be decomposed into graphs isomorphic to C_m [over(K, -)₂] for any m ≥ 3, k > 0. Decompositions of complete graphs into certain collections of even cycles are obtained as a corollary. Also some special cases of Alspach Conjecture are solved in this article. All proofs are constructive and use both graph theory and design theory techniques.

Original language	English (US)
Pages (from-to)	1003-1015
Number of pages	13
Journal	Discrete Mathematics
Volume	310
Issue number	5
DOIs	https://doi.org/10.1016/j.disc.2009.10.018
State	Published - Mar 6 2010

Bibliographical note

Funding Information:
Research for this article was supported by the Ministry of Education of the Czech Republic grant No. MSM6198910027. The authors wish to express their thanks to the anonymous referees, whose comments helped in improving the quality of this paper.

Keywords

Graph decompositions
Graph labeling

Publisher link

10.1016/j.disc.2009.10.018

Find It

Find It at U of M Libraries

Cite this

@article{e5c1a8f65c754215b3da6930c7346846,

title = "Decompositions of complete graphs into blown-up cycles Cm [2]",

abstract = "Let Cm [over(K, -)2] stand for a cycle Cm in which every vertex is replaced by two isolated vertices and every edge by K2, 2. We prove that the complete graph K8 m k + 1 can be decomposed into graphs isomorphic to Cm [over(K, -)2] for any m ≥ 3, k > 0. Decompositions of complete graphs into certain collections of even cycles are obtained as a corollary. Also some special cases of Alspach Conjecture are solved in this article. All proofs are constructive and use both graph theory and design theory techniques.",

keywords = "Graph decompositions, Graph labeling",

author = "Dalibor Fron{\v c}ek and Petr Kov{\'a}{\v r} and Michael Kubesa",

note = "Funding Information: Research for this article was supported by the Ministry of Education of the Czech Republic grant No. MSM6198910027. The authors wish to express their thanks to the anonymous referees, whose comments helped in improving the quality of this paper.",

year = "2010",

month = mar,

day = "6",

doi = "10.1016/j.disc.2009.10.018",

language = "English (US)",

volume = "310",

pages = "1003--1015",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Decompositions of complete graphs into blown-up cycles Cm [2]

AU - Fronček, Dalibor

AU - Kovář, Petr

AU - Kubesa, Michael

N1 - Funding Information: Research for this article was supported by the Ministry of Education of the Czech Republic grant No. MSM6198910027. The authors wish to express their thanks to the anonymous referees, whose comments helped in improving the quality of this paper.

PY - 2010/3/6

Y1 - 2010/3/6

N2 - Let Cm [over(K, -)2] stand for a cycle Cm in which every vertex is replaced by two isolated vertices and every edge by K2, 2. We prove that the complete graph K8 m k + 1 can be decomposed into graphs isomorphic to Cm [over(K, -)2] for any m ≥ 3, k > 0. Decompositions of complete graphs into certain collections of even cycles are obtained as a corollary. Also some special cases of Alspach Conjecture are solved in this article. All proofs are constructive and use both graph theory and design theory techniques.

AB - Let Cm [over(K, -)2] stand for a cycle Cm in which every vertex is replaced by two isolated vertices and every edge by K2, 2. We prove that the complete graph K8 m k + 1 can be decomposed into graphs isomorphic to Cm [over(K, -)2] for any m ≥ 3, k > 0. Decompositions of complete graphs into certain collections of even cycles are obtained as a corollary. Also some special cases of Alspach Conjecture are solved in this article. All proofs are constructive and use both graph theory and design theory techniques.

KW - Graph decompositions

KW - Graph labeling

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

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

U2 - 10.1016/j.disc.2009.10.018

DO - 10.1016/j.disc.2009.10.018

M3 - Article

AN - SCOPUS:72549084492

SN - 0012-365X

VL - 310

SP - 1003

EP - 1015

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 5

ER -