Isomorphic factorisations III: Complete multipartite graphs

Frank Harary; Robert W Robinson; Nicholas C Wormald

doi:10.1007/BFb0062515

Isomorphic factorisations III: Complete multipartite graphs

Frank Harary, Robert W Robinson, Nicholas C Wormald

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

Abstract

In the first paper of this series we showed that a factorisation of the complete graph Kp into t isomorphic subgraphs exists whenever the Divisibility Condition holds, that is, the number of lines is divisible by t. Our present objective is to investigate for complete multipartite graphs the extent to which the Divisibility Condition implies the existence of an isomorphic factorisation. We find that this is indeed the situation for all complete bipartite graphs but not for all k-partite graphs when k ≥ 3.

Original language	English
Title of host publication	Combinatorial Mathematics
Subtitle of host publication	Proceedings of the International Conference on Combinatorial Theory Canberra, August 16-27, 1977
Editors	D A Holton, Jennifer Seberry
Place of Publication	Berlin Germany
Pages	47-54
Number of pages	8
Volume	686
DOIs	https://doi.org/10.1007/BFb0062515
Publication status	Published - 1978
Externally published	Yes

Publication series

Name	Lecture Notes in Mathematics
Publisher	Springer
Volume	686

Access to Document

10.1007/BFb0062515

Cite this

Harary, F., Robinson, R. W., & Wormald, N. C. (1978). Isomorphic factorisations III: Complete multipartite graphs. In D. A. Holton, & J. Seberry (Eds.), Combinatorial Mathematics: Proceedings of the International Conference on Combinatorial Theory Canberra, August 16-27, 1977 (Vol. 686, pp. 47-54). (Lecture Notes in Mathematics; Vol. 686).. https://doi.org/10.1007/BFb0062515

@inproceedings{58205827a8474c0bbe27010075606e30,

title = "Isomorphic factorisations III: Complete multipartite graphs",

abstract = "In the first paper of this series we showed that a factorisation of the complete graph Kp into t isomorphic subgraphs exists whenever the Divisibility Condition holds, that is, the number of lines is divisible by t. Our present objective is to investigate for complete multipartite graphs the extent to which the Divisibility Condition implies the existence of an isomorphic factorisation. We find that this is indeed the situation for all complete bipartite graphs but not for all k-partite graphs when k ≥ 3.",

author = "Frank Harary and Robinson, {Robert W} and Wormald, {Nicholas C}",

year = "1978",

doi = "10.1007/BFb0062515",

language = "English",

isbn = "0858470497",

volume = "686",

series = "Lecture Notes in Mathematics",

publisher = "Springer",

pages = "47--54",

editor = "Holton, {D A} and Seberry, {Jennifer }",

booktitle = "Combinatorial Mathematics",

}

Harary, F, Robinson, RW & Wormald, NC 1978, Isomorphic factorisations III: Complete multipartite graphs. in DA Holton & J Seberry (eds), Combinatorial Mathematics: Proceedings of the International Conference on Combinatorial Theory Canberra, August 16-27, 1977. vol. 686, Lecture Notes in Mathematics, vol. 686, Berlin Germany, pp. 47-54. https://doi.org/10.1007/BFb0062515

Isomorphic factorisations III : Complete multipartite graphs. / Harary, Frank; Robinson, Robert W; Wormald, Nicholas C.

Combinatorial Mathematics: Proceedings of the International Conference on Combinatorial Theory Canberra, August 16-27, 1977. ed. / D A Holton; Jennifer Seberry. Vol. 686 Berlin Germany, 1978. p. 47-54 (Lecture Notes in Mathematics; Vol. 686).

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

TY - GEN

T1 - Isomorphic factorisations III

T2 - Complete multipartite graphs

AU - Harary, Frank

AU - Robinson, Robert W

AU - Wormald, Nicholas C

PY - 1978

Y1 - 1978

N2 - In the first paper of this series we showed that a factorisation of the complete graph Kp into t isomorphic subgraphs exists whenever the Divisibility Condition holds, that is, the number of lines is divisible by t. Our present objective is to investigate for complete multipartite graphs the extent to which the Divisibility Condition implies the existence of an isomorphic factorisation. We find that this is indeed the situation for all complete bipartite graphs but not for all k-partite graphs when k ≥ 3.

AB - In the first paper of this series we showed that a factorisation of the complete graph Kp into t isomorphic subgraphs exists whenever the Divisibility Condition holds, that is, the number of lines is divisible by t. Our present objective is to investigate for complete multipartite graphs the extent to which the Divisibility Condition implies the existence of an isomorphic factorisation. We find that this is indeed the situation for all complete bipartite graphs but not for all k-partite graphs when k ≥ 3.

U2 - 10.1007/BFb0062515

DO - 10.1007/BFb0062515

M3 - Conference Paper

SN - 0858470497

SN - 3540089535

SN - 0387089535

VL - 686

T3 - Lecture Notes in Mathematics

SP - 47

EP - 54

BT - Combinatorial Mathematics

A2 - Holton, D A

A2 - Seberry, Jennifer

CY - Berlin Germany

ER -