When is an Incomplete 3 × n Latin Rectangle Completable?
Reinhardt Euler ; Paweł Oleksik
Discussiones Mathematicae Graph Theory, Tome 33 (2013), p. 57-69 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

We use the concept of an availability matrix, introduced in Euler [7], to describe the family of all minimal incomplete 3 × n latin rectangles that are not completable. We also present a complete description of minimal incomplete such latin squares of order 4.

Publié le : 2013-01-01
EUDML-ID : urn:eudml:doc:267599 
@article{bwmeta1.element.doi-10_7151_dmgt_1648,
     author = {Reinhardt Euler and Pawe\l\ Oleksik},
     title = {When is an Incomplete 3 $\times$ n Latin Rectangle Completable?},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {33},
     year = {2013},
     pages = {57-69},
     zbl = {1290.05040},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1648}
}

Reinhardt Euler; Paweł Oleksik. When is an Incomplete 3 × n Latin Rectangle Completable?. Discussiones Mathematicae Graph Theory, Tome 33 (2013) pp. 57-69. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1648/

[1] P. Adams, D. Bryant and M. Buchanan, Completing partial latin squares with two filled rows and two filled columns, Electron. J. Combin. 15 (2008) #R56. | Zbl 1181.05018

[2] L.D. Andersen and A.J.W. Hilton, Thank Evans!, Proc. Lond. Math. Soc. (3) 47 (1983) 507-522. doi:10.1112/plms/s3-47.3.507[Crossref]

[3] L. Brankovic, P. Horák, M. Miller and A. Rosa, Premature partial latin squares, Ars Combin. 63 (2002), 175-184. | Zbl 1071.05016

[4] R. Burkard, M. Dell’Amico and S. Martello, Assignment Problems (SIAM, 2009).

[5] C. Colbourn, The complexity of completing partial latin squares, Discrete Appl. Math. 8 (1984) 25-30. doi:10.1016/0166-218X(84)90075-1[Crossref] | Zbl 0538.05013

[6] R. Euler, R.E. Burkard and R. Grommes, On latin squares and the facial structure of related polytopes, Discrete Math. 62 (1986) 155-181. doi:10.1016/0012-365X(86)90116-0[Crossref] | Zbl 0614.05015

[7] R. Euler, On the completability of incomplete latin squares, European J. Combin. 31 (2010) 535-552. doi:10.1016/j.ejc.2009.03.036[Crossref][WoS] | Zbl 1201.05016

[8] T. Evans, Embedding incomplete latin squares, Amer. Math. Monthly 67 (1960) 958-961. doi:10.2307/2309221[Crossref]

[9] M. Hagen, Lower bounds for three algorithms for transversal hypergraph generation, Discrete Appl. Math. 157 (2009) 1460-1469. doi:10.1016/j.dam.2008.10.004[WoS][Crossref] | Zbl 1177.05116

[10] M. Hall, An existence theorem for latin squares, Bull. Amer. Math. Soc. 51 (1945) 387-388. doi:10.1090/S0002-9904-1945-08361-X[Crossref] | Zbl 0060.02801

[11] L. Khachiyan, E. Boros, K. Elbassioni and V. Gurvich, A global parallel algorithm for the hypergraph transversal problem, Inform. Process. Lett. 101 (2007) 148-155. doi:10.1016/j.ipl.2006.09.006[WoS][Crossref] | Zbl 1185.68838

[12] H.J. Ryser, A combinatorial theorem with an application to latin rectangles, Proc. Amer. Math. Soc. 2 (1951) 550-552. doi:10.1090/S0002-9939-1951-0042361-0[Crossref] | Zbl 0043.01202

[13] B. Smetaniuk, A new construction on latin squares - I: A proof of the Evans Conjecture, Ars Combin. 11 (1981) 155-172. | Zbl 0471.05013

[14] F.C.R. Spieksma, Multi-index assignment problems: complexity, approximation, applications, in: Nonlinear Assignment Problems, Algorithms and Applications, L. Pitsoulis and P. Pardalos, (Eds.), Kluwer (2000) 1-12. | Zbl 1029.90036