Triangulations of 3-way regular tripartite graphs of degree 4, with applications to orthogonal latin squares
✍ Scribed by L.D. Andersen; A.J.W. Hilton
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 831 KB
- Volume
- 167-168
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
If G is a regular tripartite graph of degree d(G) with tripartition (A,B,C) of V(G) such that the bipartite subgraphs induced by each ofA UB, BU C, CUA are all regular of degree ½d(G), then we call G 3-way regular. We give necessary and sufficient conditions for a 3-way regular tripartite graph of degree 4 to have a decomposition into edge-disjoint triangles. These yield necessary and sufficient conditions for the completion of a partial latin square of order n in which each row and column is missing exactly two symbols, and in which each symbol occurs exactly n -2 times.
We also give necessary and sufficient conditions for a 3-way regular tripartite graph of degree 4 to have a decomposition into two edge-disjoint parallel classes, each parallel class consisting of disjoint triangles. This in turn yields necessary and sufficient conditions for the completion of a pair of (n -2) × n partial orthogonal latin squares.
Generalizations of some of the various conditions are shown to be necessary in some more general contexts.