# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Orthogonal double covers of general graphs. (English) Zbl 1034.05040
Summary: Let $H$ be a graph on $n$ vertices and $\cal G$ a collection of $n$ subgraphs of $H$, one for each vertex. Then $\cal G$ is an orthogonal double cover (ODC) of $H$ if every edge of $H$ occurs in exactly two members of $\cal 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 Factorization, etc.
##### Keywords:
Edge decomposition; Factorization; ODC; Regular graph; Hypercube
Full Text:
##### 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). · 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. · Zbl 0466.68086 [8] R. El-Shanawany, H.-D.O.F. Gronau, M. Grüttmüller, Orthogonal double covers of Kn,n by small graphs, preprint, Universität Rostock, 2000, [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 kn. 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 kn. 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. [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) · Zbl 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