Decomposition of complete bipartite graphs into generalized prisms

Sylwia Cichacz; Dalibor Fronček; Petr Kovář

doi:10.1016/j.ejc.2012.07.018

Decomposition of complete bipartite graphs into generalized prisms

Sylwia Cichacz
, Dalibor Fronček
, Petr Kovář

Mathematics & Statistics

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

4 Scopus citations

Abstract

R. Häggkvist proved that every 3-regular bipartite graph of order 2n with no component isomorphic to the Heawood graph decomposes the complete bipartite graph K _6n,6n. In (Cichacz and Fronček, 2009) [2] the first two authors established a necessary and sufficient condition for the existence of a factorization of the complete bipartite graph K _n,n into certain families of 3-regular graphs of order 2n. In this paper we tackle the problem of decompositions of K _n,n into certain 3-regular graphs called generalized prisms. We will show that certain families of 3-regular graphs of order 2n decompose the complete bipartite graph K _3n/12,3n/2.

Original language	English (US)
Pages (from-to)	104-110
Number of pages	7
Journal	European Journal of Combinatorics
Volume	34
Issue number	1
DOIs	https://doi.org/10.1016/j.ejc.2012.07.018
State	Published - 2013

Bibliographical note

Funding Information:
The research for this article was partially supported by the institutional project MSM6198910027 and by the Polish Ministry of Science and Higher Education .

Publisher link

10.1016/j.ejc.2012.07.018

Find It

Find It at U of M Libraries

Cite this

@article{53e5b7f14a4342889c0e09241816c8fe,

title = "Decomposition of complete bipartite graphs into generalized prisms",

abstract = "R. H{\"a}ggkvist proved that every 3-regular bipartite graph of order 2n with no component isomorphic to the Heawood graph decomposes the complete bipartite graph K 6n,6n. In (Cichacz and Fron{\v c}ek, 2009) [2] the first two authors established a necessary and sufficient condition for the existence of a factorization of the complete bipartite graph K n,n into certain families of 3-regular graphs of order 2n. In this paper we tackle the problem of decompositions of K n,n into certain 3-regular graphs called generalized prisms. We will show that certain families of 3-regular graphs of order 2n decompose the complete bipartite graph K 3n/12,3n/2.",

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

note = "Funding Information: The research for this article was partially supported by the institutional project MSM6198910027 and by the Polish Ministry of Science and Higher Education .",

year = "2013",

doi = "10.1016/j.ejc.2012.07.018",

language = "English (US)",

volume = "34",

pages = "104--110",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

number = "1",

}

TY - JOUR

T1 - Decomposition of complete bipartite graphs into generalized prisms

AU - Cichacz, Sylwia

AU - Fronček, Dalibor

AU - Kovář, Petr

N1 - Funding Information: The research for this article was partially supported by the institutional project MSM6198910027 and by the Polish Ministry of Science and Higher Education .

PY - 2013

Y1 - 2013

N2 - R. Häggkvist proved that every 3-regular bipartite graph of order 2n with no component isomorphic to the Heawood graph decomposes the complete bipartite graph K 6n,6n. In (Cichacz and Fronček, 2009) [2] the first two authors established a necessary and sufficient condition for the existence of a factorization of the complete bipartite graph K n,n into certain families of 3-regular graphs of order 2n. In this paper we tackle the problem of decompositions of K n,n into certain 3-regular graphs called generalized prisms. We will show that certain families of 3-regular graphs of order 2n decompose the complete bipartite graph K 3n/12,3n/2.

AB - R. Häggkvist proved that every 3-regular bipartite graph of order 2n with no component isomorphic to the Heawood graph decomposes the complete bipartite graph K 6n,6n. In (Cichacz and Fronček, 2009) [2] the first two authors established a necessary and sufficient condition for the existence of a factorization of the complete bipartite graph K n,n into certain families of 3-regular graphs of order 2n. In this paper we tackle the problem of decompositions of K n,n into certain 3-regular graphs called generalized prisms. We will show that certain families of 3-regular graphs of order 2n decompose the complete bipartite graph K 3n/12,3n/2.

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

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

U2 - 10.1016/j.ejc.2012.07.018

DO - 10.1016/j.ejc.2012.07.018

M3 - Article

AN - SCOPUS:84866977027

SN - 0195-6698

VL - 34

SP - 104

EP - 110

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 1

ER -

Decomposition of complete bipartite graphs into generalized prisms

Abstract

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this