The isomorphic factorization of complete tripartite graphs K (m, n, s) - a proof of F. Harary, R.W. Robinson and N.C. Wormald's conjecture
✍ Scribed by Shihui Yang
- Book ID
- 103059808
- Publisher
- Elsevier Science
- Year
- 1995
- Tongue
- English
- Weight
- 623 KB
- Volume
- 145
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
Harary, Robinson and Wormald (1978) proved that for a complete tripartite graph G = K(m,n,s) if t = 2 or 4 and tl(mn + ms + ns), then G has an isomorphic factorization into t isomorphic subgraphs, written as t[ G. They also proved that the analogous statement is false for all odd t > 1. They conjecture that when t > 1 is even, and tl(mn + ms + ns), G = K(m, n,s), then t lG. In this paper we shall show that the conjecture is true.
An isomorphic factorization of a graph G = (V, E) is a partition { El, E2 ..... /~t } of the edge set E, such that the spanning subgraphs (V, E1),(V, E2) ..... (V, Et) are all isomorphic to each other. If G has an isomorphic factorization into exactly t isomorphic subgraphs we say that G is divisible by t or t divides G and write t l G. For a given integer t and a given graph G with exactly q edges, an obvious necessary condition for riG is that t divides q which is denoted by t lq. The condition t lq is called the divisibility condition for riG.
Harary et al. [2] proved that a complete tripartite graph G = K(m, n, s), when t = 2 or 4 the divisibility condition tl (ran + ms + ns) is a sufficient condition for tl G. They also proved that for all odd t > 1, the divisibility condition is false to be a sufficient condition for tlK (1,1,m). They conjecture that when t is even, G = K(m,n,s) is a complete tripartite graph, and tl(mn + ms + ns), then riG. The case that t = 6 was proved by Quinn [3,4]. The case that t = 2 k, k = 1, 2, 3 ..... was proved in [5]. In this paper we shall prove that the conjecture is true by verifying it for t ~> 8 (Theorem 1). We also independently derive a proof for t = 6 (Theorem 2).
Remark. Assume t is even and tl(mn + ms + ns). Then there are at least two even numbers among m, n and s.