Premium
Symmetric latin square and complete graph analogues of the evans conjecture
Author(s) -
Andersen Lars Døvling,
Hilton A. J. W.
Publication year - 1994
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.3180020404
Subject(s) - latin square , combinatorics , conjecture , mathematics , diagonal , square (algebra) , graph , geometry , chemistry , rumen , food science , fermentation
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 K 2m and K 2m − 1 with 2 m − 1 colors, with m + 1 or fewer edges getting prescribed colors. © 1994 John Wiley & Sons, Inc.