×

Orthogonal double covers of \(K_{n,n}\) by small graphs. (English) Zbl 1034.05039

Summary: An orthogonal double cover (ODC) of \(K_n\) is a collection of graphs such that each edge of \(K_n\) occurs in exactly two of the graphs and two graphs have precisely one edge in common. ODCs of \(K_n\) and their generalizations have been extensively studied by several authors (e.g. in J. H. Dinitz and D. R. Stinson (eds.) [Contemporary design theory (Wiley, New York) (1992; Zbl 0746.00028), pp. 13–40 (Chapter 2)]; H.-J. O. F. Gronau et al. [Des. Codes Cryptography 27, 49–91 (2002; Zbl 1001.05091)]; H.-J. O. F. Gronau et al. [Graphs Comb. 13, 251–262 (1997; Zbl 0885.05093)]; V. Leck [Orthogonal double covers of \(K_m\), Ph.D. Thesis, Universität Rostock (2000)]). In this paper, we investigate ODCs where the graph to be covered twice is \(K_{n,n}\) and all graphs in the collection are isomorphic to a given small graph \(G\). We prove that there exists an ODC of \(K_{n,n}\) by all proper subgraphs \(G\) of \(K_{n,n}\) for \(1 \leqslant n \leqslant 9\), with two genuine exceptions.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Software:

nauty
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alspach, B.; Heinrich, K.; Liu, G., Orthogonal factorizations of graphs, (Dinitz, J. H.; Stinson, D. R., Contemporary Design Theory (1992), Wiley: Wiley New York), 13-40, (Chapter 2) · Zbl 0779.05032
[2] Bennett, F. E.; Wu, L., On minimum matrix representation of closure operations, Discrete Appl. Math., 26, 25-40 (1990) · Zbl 0724.05011
[3] C.J. Colbourn, J.H. Dinitz (Eds.), CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton, FL, 1996.; C.J. Colbourn, J.H. Dinitz (Eds.), CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton, FL, 1996. · Zbl 0836.00010
[4] Demetrovics, J.; Füredi, Z.; Katona, G. O.H., Minimum matrix representations of closure operations, Discrete Appl. Math., 11, 115-128 (1985) · Zbl 0577.68084
[5] Ganter, B.; Gronau, H.-D. O.F., On two conjectures of Demetrovics, Füredi and Katona on partitions, Discrete Math., 88, 149-155 (1991) · Zbl 0739.05004
[6] Ganter, B.; Gronau, H.-D. O.F.; Mullin, R. C., On orthogonal double covers of \(K_n\), Ars Combin., 37, 209-221 (1994) · Zbl 0807.05059
[7] Gronau, H.-D. O.F.; Hartmann, S.; Grüttmüller, M.; Leck, U.; Leck, V., On orthogonal double covers of graphs, Design Codes Cryptography, 27, 49-91 (2002) · Zbl 1001.05091
[8] Gronau, H.-D. O.F.; Mullin, R. C.; Rosa, A., Orthogonal double covers of complete graphs by trees, Graphs Combin., 13, 251-262 (1997) · Zbl 0885.05093
[9] Gronau, H.-D. O.F.; Mullin, R. C.; Schellenberg, P. J., On Orthogonal double covers and a conjecture of Chung and West, J. Combin. Designs, 3, 213-231 (1995) · Zbl 0886.05094
[10] Hartmann, S.; Leck, U.; Leck, V., A conjecture on orthogonal double covers by paths, Congr. Numer., 140, 187-193 (1999) · Zbl 0960.05080
[11] S. Hartmann, U. Schumacher, Orthogonal double covers of general graphs, Discrete Appl. Math. x-ref: Doi:10.1016/S0166-218X(03)00269-5; S. Hartmann, U. Schumacher, Orthogonal double covers of general graphs, Discrete Appl. Math. x-ref: Doi:10.1016/S0166-218X(03)00269-5 · Zbl 1034.05040
[12] Heinrich, K.; Nonay, G., Path and cycle decompositions of complete multigraphs, Ann. Discrete Math., 27, 275-286 (1985) · Zbl 0588.05022
[13] F. Hering, M. Rosenfeld, Problem number 38, in: K. Heinrich (Ed.), Unsolved Problems: Summer Research Workshop in Algebraic Combinatorics, Simon Fraser University, 1979.; F. Hering, M. Rosenfeld, Problem number 38, in: K. Heinrich (Ed.), Unsolved Problems: Summer Research Workshop in Algebraic Combinatorics, Simon Fraser University, 1979.
[14] Horton, J. D.; Nonay, G., Self-orthogonal Hamilton path decompositions, Discrete Math., 97, 251-264 (1991) · Zbl 0780.05035
[15] Leck, U., A class of 2-colorable orthogonal double covers of complete graphs by Hamiltonian paths, Graphs Combin., 18, 155-167 (2002) · Zbl 0988.05074
[16] Leck, U.; Leck, V., There is no ODC with all pages isomorphic to \(C_4\)∪ \(C_3\)∪ \(C_3\)∪ \(v\), Utilitas Math., 49, 185-189 (1996) · Zbl 0854.05087
[17] Leck, U.; Leck, V., On orthogonal double covers by trees, J. Combin. Designs, 5, 433-441 (1997) · Zbl 0914.05014
[18] Leck, U.; Leck, V., Orthogonal double covers of complete graphs by trees of small diameter, Discrete Appl. Math., 95, 377-388 (1999) · Zbl 0932.05075
[19] V. Leck, Orthogonal double covers of \(K_n\); V. Leck, Orthogonal double covers of \(K_n\)
[20] B.D. McKay, Nauty User’s Guide, Computer Science Technical Report TR-CS-84-05, Australian National University, 1984.; B.D. McKay, Nauty User’s Guide, Computer Science Technical Report TR-CS-84-05, Australian National University, 1984.
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.