2-halvable complete 4-partite graphs

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

top

Abstract

top
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.

How to cite

top

Dalibor 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. [1] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs (Prindle, Weber & Schmidt, Boston, 1979). Zbl0403.05027
2. [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. [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. [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. [5] D. Fronček, Decompositions of complete multipartite graphs into disconnected selfcomplementary factors, Utilitas Mathematica 53 (1998) 201-216. Zbl0909.05038
6. [6] D. Fronček and J. Širáň, Halving complete 4-partite graphs, Ars Combinatoria (to appear). Zbl0994.05117
7. [7] T. Gangopadhyay, Range of diameters in a graph and its r-partite complement, Ars Combinatoria 18 (1983) 61-80. Zbl0558.05035
8. [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. [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. [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. [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. [12] E. Tomová, Decomposition of complete bipartite graphs into factors with given diameters, Math. Slovaca 27 (1977) 113-128. Zbl0357.05066

NotesEmbed?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.