# 2-halvable complete 4-partite graphs

Discussiones Mathematicae Graph Theory (1998)

- Volume: 18, Issue: 2, page 233-242
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topDalibor Fronček. "2-halvable complete 4-partite graphs." Discussiones Mathematicae Graph Theory 18.2 (1998): 233-242. <http://eudml.org/doc/270258>.

@article{DaliborFronček1998,

abstract = {A complete 4-partite graph $K_\{m₁,m₂,m₃,m₄\}$ is called d-halvable if it can be decomposed into two isomorphic factors of diameter d. In the class of graphs $K_\{m₁,m₂,m₃,m₄\}$ with at most one odd part all d-halvable graphs are known. In the class of biregular graphs $K_\{m₁,m₂,m₃,m₄\}$ with four odd parts (i.e., the graphs $K_\{m,m,m,n\}$ and $K_\{m,m,n,n\}$) all d-halvable graphs are known as well, except for the graphs $K_\{m,m,n,n\}$ when d = 2 and n ≠ m. We prove that such graphs are 2-halvable iff n,m ≥ 3. We also determine a new class of non-halvable graphs $K_\{m₁,m₂,m₃,m₄\}$ with three or four different odd parts.},

author = {Dalibor Fronček},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {Graph decompositions; isomorphic factors; selfcomplementary graphs; 2-halvable graphs; complete 4-partite graphs},

language = {eng},

number = {2},

pages = {233-242},

title = {2-halvable complete 4-partite graphs},

url = {http://eudml.org/doc/270258},

volume = {18},

year = {1998},

}

TY - JOUR

AU - Dalibor Fronček

TI - 2-halvable complete 4-partite graphs

JO - Discussiones Mathematicae Graph Theory

PY - 1998

VL - 18

IS - 2

SP - 233

EP - 242

AB - A complete 4-partite graph $K_{m₁,m₂,m₃,m₄}$ is called d-halvable if it can be decomposed into two isomorphic factors of diameter d. In the class of graphs $K_{m₁,m₂,m₃,m₄}$ with at most one odd part all d-halvable graphs are known. In the class of biregular graphs $K_{m₁,m₂,m₃,m₄}$ with four odd parts (i.e., the graphs $K_{m,m,m,n}$ and $K_{m,m,n,n}$) all d-halvable graphs are known as well, except for the graphs $K_{m,m,n,n}$ when d = 2 and n ≠ m. We prove that such graphs are 2-halvable iff n,m ≥ 3. We also determine a new class of non-halvable graphs $K_{m₁,m₂,m₃,m₄}$ with three or four different odd parts.

LA - eng

KW - Graph decompositions; isomorphic factors; selfcomplementary graphs; 2-halvable graphs; complete 4-partite graphs

UR - http://eudml.org/doc/270258

ER -

## References

top- [1] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs (Prindle, Weber & Schmidt, Boston, 1979). Zbl0403.05027
- [2] J. Bosák, A. Rosa and Š. Znám, On decompositions of complete graphs into factors with given diameters, in: Theory of Graphs, Proc. Coll. Tihany 1966 (Akadémiai Kiadó, Budapest, 1968) 37-56.
- [3] D. Fronček, Decompositions of complete bipartite and tripartite graphs into selfcomplementary factors with finite diameters, Graphs. Combin. 12 (1996) 305-320, doi: 10.1007/BF01858463. Zbl0866.05050
- [4] D. Fronček, Decompositions of complete multipartite graphs into selfcomplementary factors with finite diameters, Australas. J. Combin. 13 (1996) 61-74. Zbl0844.05075
- [5] D. Fronček, Decompositions of complete multipartite graphs into disconnected selfcomplementary factors, Utilitas Mathematica 53 (1998) 201-216. Zbl0909.05038
- [6] D. Fronček and J. Širáň, Halving complete 4-partite graphs, Ars Combinatoria (to appear). Zbl0994.05117
- [7] T. Gangopadhyay, Range of diameters in a graph and its r-partite complement, Ars Combinatoria 18 (1983) 61-80. Zbl0558.05035
- [8] P. Híc and D. Palumbíny, Isomorphic factorizations of complete graphs into factors with a given diameter, Math. Slovaca 37 (1987) 247-254. Zbl0675.05051
- [9] A. Kotzig and A. Rosa, Decomposition of complete graphs into isomorphic factors with a given diameter, Bull. London Math. Soc. 7 (1975) 51-57, doi: 10.1112/blms/7.1.51. Zbl0308.05128
- [10] D. Palumbíny, Factorizations of complete graphs into isomorphic factors with a given diameter, Zborník Pedagogickej Fakulty v Nitre, Matematika 2 (1982) 21-32.
- [11] P. Tomasta, Decompositions of graphs and hypergraphs into isomorphic factors with a given diameter, Czechoslovak Math. J. 27 (1977) 598-608. Zbl0384.05048
- [12] E. Tomová, Decomposition of complete bipartite graphs into factors with given diameters, Math. Slovaca 27 (1977) 113-128. Zbl0357.05066

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.