Discussiones Mathematicae Graph Theory 33(1) (2013) 57-69
doi: 10.7151/dmgt.1648

Dedicated to Mieczysław Borowiecki on his 70th birthday

[BIBTex] [PDF] [PS]

When Is an Incomplete 3× n Latin Rectangle Completable?

Reinhardt Euler

Université Européenne de Bretagne and Lab-STICC, CNRS, UMR 6285,
Université de Brest, B.P.809,
20 Avenue Le Gorgeu, 29285 Brest Cedex, France

Paweł Oleksik

AGH University of Science and Technology,
Faculty of Geology, Geophysics and Environment Protection,
Department of Geoinformatics and Applied Computer Science,
30-059 Cracow, Poland

Abstract

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

Keywords: incomplete latin rectangle, completability, solution space enumeration, branch-and-bound

2010 Mathematics Subject Classification: 05B15, 05C65.

References

[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.
[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.
[3]L. Brankovic, P. Horák, M. Miller and A. Rosa, Premature partial latin squares, Ars Combin. 63 (2002), 175--184.
[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.
[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.
[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.
[8]T. Evans, Embedding incomplete latin squares, Amer. Math. Monthly 67 (1960) 958--961, doi: 10.2307/2309221.
[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.
[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 .
[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.
[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.
[13]B. Smetaniuk, A new construction on latin squares - I:A proof of the Evans Conjecture, Ars Combin. 11 (1981) 155--172.
[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.

Received 24 March 2012
Revised 26 July 2012
Accepted 27 July 2012