Symmetric latin square and complete graph analogues of the evans conjecture |
| |
Authors: | Lars Dvling Andersen A J W Hilton |
| |
Institution: | Lars Døvling Andersen,A. J. W. Hilton |
| |
Abstract: | With the proof of the Evans conjecture, it was established that any partial latin square of side n with a most n ? 1 nonempty cells can be completed to a latin square of side n. In this article we prove an analogous result for symmetric latin squares: a partial symmetric latin square of side n with an admissible diagonal and at most n ? 1 nonempty cells can be completed to a symmetric latin square of side n. We also characterize those partial symmetric latin squares of side n with exactly n or n + 1 nonempty cells which cannot be completed. From these results we deduce theorems about completing edge-colorings of complete graphs K2m and K2m ? 1 with 2m ? 1 colors, with m + 1 or fewer edges getting prescribed colors. © 1994 John Wiley & Sons, Inc. |
| |
Keywords: | |
|
|