×

Orthogonal double covers of general graphs. (English) Zbl 1034.05040

Summary: Let \(H\) be a graph on \(n\) vertices and \(\mathcal G\) a collection of \(n\) subgraphs of \(H\), one for each vertex. Then \(\mathcal G\) is an orthogonal double cover (ODC) of \(H\) if every edge of \(H\) occurs in exactly two members of \(\mathcal G\) and any two members share an edge whenever the corresponding vertices are adjacent in \(H\). ODCs of complete graphs have been widely studied in the literature. In this paper we are concerned with ODCs of arbitrary graphs. In particular, we investigate the existence of ODCs whose members are isomorphic sets of independent edges.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. Alspach, K. Heinrich, G. Liu, Orthogonal Factorizations of Graphs, in: J.H. Dinitz, D.R. Stinson (Eds.), Contemporary Design Theory, Wiley, New York, 1992 (Chapter 2).; B. Alspach, K. Heinrich, G. Liu, Orthogonal Factorizations of Graphs, in: J.H. Dinitz, D.R. Stinson (Eds.), Contemporary Design Theory, Wiley, New York, 1992 (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] Bryant, D. E.; Khodkar, A., On orthogonal double covers of graphs, Des. Codes Cryptography, 13, 103-105 (1998) · Zbl 0887.05040
[4] Cameron, P. J., SGDs without doubly transitive automorphism group, J. Graph Theory, 32, 229-233 (1999) · Zbl 0936.05052
[5] Chung, M. S.; West, D. B., The \(p\)-intersection number of a complete bipartite graph and orthogonal double coverings of a clique, Combinatorica, 14, 453-461 (1994) · Zbl 0813.05055
[6] 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
[7] J. Demetrovics, G.O.H. Katona, Extremal combinatorial problems in relational database, in: Fundamentals of Computation Theory, Lecture Notes in Computer Science, Vol. 117, Springer, Berlin, 1981, pp. 110-119.; J. Demetrovics, G.O.H. Katona, Extremal combinatorial problems in relational database, in: Fundamentals of Computation Theory, Lecture Notes in Computer Science, Vol. 117, Springer, Berlin, 1981, pp. 110-119.
[8] R. El-Shanawany, H.-D.O.F. Gronau, M. Grüttmüller, Orthogonal double covers of \(K_{nn}\); R. El-Shanawany, H.-D.O.F. Gronau, M. Grüttmüller, Orthogonal double covers of \(K_{nn}\)
[9] Fronček, D.; Rosa, A., Symmetric graph designs on friendship graphs, J. Combin. Des., 8, 201-206 (1999) · Zbl 0993.05041
[10] 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
[11] 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
[12] Granville, A.; Gronau, H.-D. O.F.; Mullin, R. C., On a problem of Hering concerning orthogonal double covers of \(K_n\), J. Combin. Theory A, 72, 345-350 (1995) · Zbl 0839.05025
[13] 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
[14] Gronau, H.-D. O.F.; Mullin, R. C.; Rosa, A.; Schellenberg, P. J., Symmetric graph designs, Graphs Combin., 16, 93-102 (2000) · Zbl 0952.05005
[15] Gronau, H.-D. O.F.; Mullin, R. C.; Schellenberg, P. J., On orthogonal double covers and a conjecture of Chung and West, J. Combin. Des., 3, 213-231 (1995) · Zbl 0886.05094
[16] Hartmann, S., Asymptotic results on suborthogonal \(G\)-decompositions of complete digraphs, Discrete Appl. Math., 95, 311-320 (1999) · Zbl 0933.05123
[17] Hartmann, S., Orthogonal decompositions of complete digraphs, Graphs Combin., 18, 285-302 (2002) · Zbl 0998.05052
[18] Hartmann, S.; Leck, U.; Leck, V., A conjecture on orthogonal double covers by paths, Congr. Numer., 140, 187-194 (2000) · Zbl 0960.05080
[19] Heinrich, K.; Nonay, G., Path and cycle decompositions of complete multigraphs, Ann. Discrete Math., 27, 275-286 (1985) · Zbl 0588.05022
[20] F. Hering, M. Rosenfeld, Problem number 38, in: K. Heinrich (Ed.). Unsolved Problems: Summer Research Workshop in Algebraic Combinatorics, Simon Fraser University, Canada, 1979.; F. Hering, M. Rosenfeld, Problem number 38, in: K. Heinrich (Ed.). Unsolved Problems: Summer Research Workshop in Algebraic Combinatorics, Simon Fraser University, Canada, 1979.
[21] Horton, J. D.; Nonay, G., Self-orthogonal Hamilton path decompositions, Discrete Math., 97, 251-264 (1991) · Zbl 0780.05035
[22] 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
[23] Leck, U.; Leck, V., On orthogonal double covers by trees, J. Combin. Des., 5, 433-441 (1997) · Zbl 0914.05014
[24] 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
[25] Leck, V., On orthogonal double covers by Hamiltonian paths, Congr. Numer., 135, 153-157 (1998) · Zbl 0952.05058
[26] Petersen, J., Die Theorie des regulären Graphs, Acta Math., 15, 193-220 (1891) · JFM 23.0115.03
[27] Robinson, R. W.; Wormald, N. C., Almost all cubic graphs are Hamiltonian, Random Struct. Algorithms, 3, 117-125 (1992) · Zbl 0755.05075
[28] Robinson, R. W.; Wormald, N. C., Almost all regular graphs are Hamiltonian, Random Struct. Algorithms, 5, 363-374 (1994) · Zbl 0795.05088
[29] Sauer, N.; Spencer, J., Edge disjoint placement of graphs, J. Combin. Theory B, 25, 295-302 (1978) · Zbl 0417.05037
[30] Schumacher, U., Suborthogonal double covers of complete graphs by stars, Discrete Appl. Math., 95, 439-444 (1999) · Zbl 0932.05078
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.