Completing simple partial k-Latin squares
We study the completion problem for simple k-Latin rectangles, which are a special case of the generalized latin rectangles studied for which embedding theorems are given by Andersen and Hilton (1980) in “Generalized Latin rectangles II: Embedding”, Discrete Mathematics 31(3). Here an alternative p...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Accademia Peloritana dei Pericolanti
2018-11-01
|
| Series: | Atti della Accademia Peloritana dei Pericolanti : Classe di Scienze Fisiche, Matematiche e Naturali |
| Online Access: |
http://dx.doi.org/10.1478/AAPP.96S2A4
|
| _version_ | 1818937298836783104 |
|---|---|
| author | Nicholas Cavenagh Giovanni Lo Faro Antoinette Tripodi |
| author_facet | Nicholas Cavenagh Giovanni Lo Faro Antoinette Tripodi |
| author_sort | Nicholas Cavenagh |
| collection | DOAJ |
| description | We study the completion problem for simple k-Latin rectangles, which are a special case of the generalized latin rectangles studied for which embedding theorems are given by Andersen and Hilton (1980) in “Generalized Latin rectangles II: Embedding”, Discrete Mathematics 31(3). Here an alternative proof of those theorems are given for k-Latin rectangles in the “simple” case. More precisely, generalizing two classic results on the completability of partial Latin squares, we prove the necessary and suffisucient conditions for a completion of a simple m x n k-Latin rectangle to a simple k-Latin square of order n and we show that if m ≤ n/2, any simple partial k-Latin square P of order m embeds in a simple k-Latin square L of order n. |
| first_indexed | 2024-12-20T05:49:45Z |
| format | Article |
| id | doaj.art-4759cf5ae4b24c02841ca36ed4564a03 |
| institution | Directory Open Access Journal |
| issn | 0365-0359 1825-1242 |
| language | English |
| last_indexed | 2024-12-20T05:49:45Z |
| publishDate | 2018-11-01 |
| publisher | Accademia Peloritana dei Pericolanti |
| record_format | Article |
| series | Atti della Accademia Peloritana dei Pericolanti : Classe di Scienze Fisiche, Matematiche e Naturali |
| spelling | doaj.art-4759cf5ae4b24c02841ca36ed4564a032022-12-21T19:51:13ZengAccademia Peloritana dei PericolantiAtti della Accademia Peloritana dei Pericolanti : Classe di Scienze Fisiche, Matematiche e Naturali0365-03591825-12422018-11-0196S2A410.1478/AAPP.96S2A4AAPP.96S2A4Completing simple partial k-Latin squaresNicholas CavenaghGiovanni Lo FaroAntoinette TripodiWe study the completion problem for simple k-Latin rectangles, which are a special case of the generalized latin rectangles studied for which embedding theorems are given by Andersen and Hilton (1980) in “Generalized Latin rectangles II: Embedding”, Discrete Mathematics 31(3). Here an alternative proof of those theorems are given for k-Latin rectangles in the “simple” case. More precisely, generalizing two classic results on the completability of partial Latin squares, we prove the necessary and suffisucient conditions for a completion of a simple m x n k-Latin rectangle to a simple k-Latin square of order n and we show that if m ≤ n/2, any simple partial k-Latin square P of order m embeds in a simple k-Latin square L of order n. http://dx.doi.org/10.1478/AAPP.96S2A4 |
| spellingShingle | Nicholas Cavenagh Giovanni Lo Faro Antoinette Tripodi Completing simple partial k-Latin squares Atti della Accademia Peloritana dei Pericolanti : Classe di Scienze Fisiche, Matematiche e Naturali |
| title | Completing simple partial k-Latin squares |
| title_full | Completing simple partial k-Latin squares |
| title_fullStr | Completing simple partial k-Latin squares |
| title_full_unstemmed | Completing simple partial k-Latin squares |
| title_short | Completing simple partial k-Latin squares |
| title_sort | completing simple partial k latin squares |
| url |
http://dx.doi.org/10.1478/AAPP.96S2A4
|
| work_keys_str_mv | AT nicholascavenagh completingsimplepartialklatinsquares AT giovannilofaro completingsimplepartialklatinsquares AT antoinettetripodi completingsimplepartialklatinsquares |