Note on decomposition of kn,n into (0, j)-prisms

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

doi:10.1007/978-3-642-10217-2_15

Note on decomposition of k_n,n into (0, j)-prisms

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

Mathematics & Statistics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 [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 3-regular graphs some more. We will show that certain families of 3-regular graphs of order 2n decompose the complete bipartite graph K_3n/2,3n/2 .

Original language	English (US)
Title of host publication	Combinatorial Algorithms - 20th International Workshop, IWOCA 2009, Revised Selected Papers
Pages	125-133
Number of pages	9
DOIs	https://doi.org/10.1007/978-3-642-10217-2_15
State	Published - Dec 1 2009
Event	20th International Workshop on Combinatorial Algorithms, IWOCA 2009 - Hradec nad Moravici, Czech Republic Duration: Jun 28 2009 → Jul 2 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5874 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	20th International Workshop on Combinatorial Algorithms, IWOCA 2009
Country/Territory	Czech Republic
City	Hradec nad Moravici
Period	6/28/09 → 7/2/09

Publisher link

10.1007/978-3-642-10217-2_15

Find It

Find It at U of M Libraries

Cite this

Cichacz, S., Fronček, D., & Kovář, P. (2009). Note on decomposition of k_n,n into (0, j)-prisms. In Combinatorial Algorithms - 20th International Workshop, IWOCA 2009, Revised Selected Papers (pp. 125-133). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5874 LNCS). https://doi.org/10.1007/978-3-642-10217-2_15

Note on decomposition of k_n,n into (0, j)-prisms. / Cichacz, Sylwia; Fronček, Dalibor; Kovář, Petr.
Combinatorial Algorithms - 20th International Workshop, IWOCA 2009, Revised Selected Papers. 2009. p. 125-133 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5874 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Cichacz, S, Fronček, D & Kovář, P 2009, Note on decomposition of k_n,n into (0, j)-prisms. in Combinatorial Algorithms - 20th International Workshop, IWOCA 2009, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5874 LNCS, pp. 125-133, 20th International Workshop on Combinatorial Algorithms, IWOCA 2009, Hradec nad Moravici, Czech Republic, 6/28/09. https://doi.org/10.1007/978-3-642-10217-2_15

@inproceedings{63daf58914274bda9173f8aec6fe5ca0,

title = "Note on decomposition of kn,n into (0, j)-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 K6n,6n. In [2] the first two authors established a necessary and sufficient condition for the existence of a factorization of the complete bipartite graph Kn,n into certain families of 3-regular graphs of order 2n. In this paper we tackle the problem of decompositions of Kn,n into 3-regular graphs some more. We will show that certain families of 3-regular graphs of order 2n decompose the complete bipartite graph K3n/2,3n/2 .",

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

year = "2009",

month = dec,

day = "1",

doi = "10.1007/978-3-642-10217-2_15",

language = "English (US)",

isbn = "3642102166",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "125--133",

booktitle = "Combinatorial Algorithms - 20th International Workshop, IWOCA 2009, Revised Selected Papers",

note = "20th International Workshop on Combinatorial Algorithms, IWOCA 2009 ; Conference date: 28-06-2009 Through 02-07-2009",

}

TY - GEN

T1 - Note on decomposition of kn,n into (0, j)-prisms

AU - Cichacz, Sylwia

AU - Fronček, Dalibor

AU - Kovář, Petr

PY - 2009/12/1

Y1 - 2009/12/1

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 K6n,6n. In [2] the first two authors established a necessary and sufficient condition for the existence of a factorization of the complete bipartite graph Kn,n into certain families of 3-regular graphs of order 2n. In this paper we tackle the problem of decompositions of Kn,n into 3-regular graphs some more. We will show that certain families of 3-regular graphs of order 2n decompose the complete bipartite graph K3n/2,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 K6n,6n. In [2] the first two authors established a necessary and sufficient condition for the existence of a factorization of the complete bipartite graph Kn,n into certain families of 3-regular graphs of order 2n. In this paper we tackle the problem of decompositions of Kn,n into 3-regular graphs some more. We will show that certain families of 3-regular graphs of order 2n decompose the complete bipartite graph K3n/2,3n/2 .

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

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

U2 - 10.1007/978-3-642-10217-2_15

DO - 10.1007/978-3-642-10217-2_15

M3 - Conference contribution

AN - SCOPUS:78650621195

SN - 3642102166

SN - 9783642102165

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 125

EP - 133

BT - Combinatorial Algorithms - 20th International Workshop, IWOCA 2009, Revised Selected Papers

T2 - 20th International Workshop on Combinatorial Algorithms, IWOCA 2009

Y2 - 28 June 2009 through 2 July 2009

ER -