2-halvable complete 4-partite graphs
Dalibor Fronček
Discussiones Mathematicae Graph Theory, Tome 18 (1998), p. 233-242 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

A complete 4-partite graph Km₁,m₂,m₃,m₄ is called d-halvable if it can be decomposed into two isomorphic factors of diameter d. In the class of graphs Km₁,m₂,m₃,m₄ with at most one odd part all d-halvable graphs are known. In the class of biregular graphs Km₁,m₂,m₃,m₄ with four odd parts (i.e., the graphs Km,m,m,n and Km,m,n,n) all d-halvable graphs are known as well, except for the graphs Km,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 Km₁,m₂,m₃,m₄ with three or four different odd parts.

Publié le : 1998-01-01
EUDML-ID : urn:eudml:doc:270258 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1079,
     author = {Dalibor Fron\v cek},
     title = {2-halvable complete 4-partite graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {18},
     year = {1998},
     pages = {233-242},
     zbl = {0934.05103},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1079}
}

Dalibor Fronček. 2-halvable complete 4-partite graphs. Discussiones Mathematicae Graph Theory, Tome 18 (1998) pp. 233-242. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1079/

[000] [1] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs (Prindle, Weber & Schmidt, Boston, 1979). | Zbl 0403.05027

[001] [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.

[002] [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. | Zbl 0866.05050

[003] [4] D. Fronček, Decompositions of complete multipartite graphs into selfcomplementary factors with finite diameters, Australas. J. Combin. 13 (1996) 61-74. | Zbl 0844.05075

[004] [5] D. Fronček, Decompositions of complete multipartite graphs into disconnected selfcomplementary factors, Utilitas Mathematica 53 (1998) 201-216. | Zbl 0909.05038

[005] [6] D. Fronček and J. Širáň, Halving complete 4-partite graphs, Ars Combinatoria (to appear). | Zbl 0994.05117

[006] [7] T. Gangopadhyay, Range of diameters in a graph and its r-partite complement, Ars Combinatoria 18 (1983) 61-80. | Zbl 0558.05035

[007] [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. | Zbl 0675.05051

[008] [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. | Zbl 0308.05128

[009] [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.

[010] [11] P. Tomasta, Decompositions of graphs and hypergraphs into isomorphic factors with a given diameter, Czechoslovak Math. J. 27 (1977) 598-608. | Zbl 0384.05048

[011] [12] E. Tomová, Decomposition of complete bipartite graphs into factors with given diameters, Math. Slovaca 27 (1977) 113-128. | Zbl 0357.05066