×

Symmetric latin square and complete graph analogues of the Evans conjecture. (English) Zbl 0821.05005

T. Evans conjectured that a partial latin square of order \(n\) with at most \(n- 1\) cells occupied can always be completed to a latin square of order \(n\), see [Am. Math. Mon. 67, 958-961 (1961; Zbl 0100.256)]. The Evans conjecture turned out to be true and the history of the solution can be found in C. C. Lindner [Embedding theorems for partial latin squares, Ann. Discrete Math. 46, 217-265 (1991; Zbl 0741.05013)]. The present authors prove an analogous result for symmetric latin squares. They also characterize those partial symmetric squares of order \(n\) with exactly \(n\) or \(n+ 1\) nonempty cells which cannot be completed.

MSC:

05B15 Orthogonal arrays, Latin squares, Room squares
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andersen, Ann. Discrete Math. 15 pp 9– (1982)
[2] Andersen, Mat.-Fys. Medd. Danske Vid. Selsk. 41 pp 23– (1985)
[3] Math. Scand. 64 pp 5– (1989) · Zbl 0665.05028 · doi:10.7146/math.scand.a-12245
[4] Andersen, European J. Combin. 1 pp 5– (1980) · Zbl 0442.05009 · doi:10.1016/S0195-6698(80)80014-X
[5] Andersen, Proc. London Math. Soc. (3) 47 pp 507– (1983)
[6] Andersen, Ann. Discrete Math. 34 pp 1– (1987)
[7] ”Extending edge-colorings of complete graphs and independent edges,” in Graph Theory and its applications: East and west, proceedings of the first China–USA international graph theory conference (1989), 30–41.
[8] Andersen, J. London Math. Soc. (2) 26 pp 21– (1982)
[9] Andersen, Ann. Discrete Math. 17 pp 19– (1983)
[10] Cruse, J. Combin. Theory Ser. A 16 pp 18– (1974)
[11] Damerell, Proc. London Math. Soc. (3) 47 pp 523– (1983)
[12] Evans, Amer. Math. Monthly 67 pp 958– (1960)
[13] Hall, J. London Math. Soc. 10 pp 26– (1935)
[14] Hilton, J. Combin. Theory Ser. A 15 pp 121– (1973)
[15] Hilton, Discrete Math. 12 pp 257– (1975)
[16] Hilton, Canad. J. Math. pp 1251– (1982) · Zbl 0468.05015 · doi:10.4153/CJM-1982-087-7
[17] Hoffmann, European J. Combin. 4 pp 33– (1983) · Zbl 0513.05016 · doi:10.1016/S0195-6698(83)80006-7
[18] Linder, J. Combin. Theory Ser. A 10 pp 240– (1971)
[19] ”Embedding incomplete idempotent latin squares”, Combinatorial mathematics X, L. R. A. Casse (Editor), Proceedings of the conference held in Adelaide, Australia, August 23-27, 1982; Lecture notes in Mathematics 1036, Springer, Berlin, 1983, pp. 355–366.
[20] Rodger, Discrete Math. 51 pp 73– (1984)
[21] Smetaniuk, Ars Combin. pp 155– (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.