DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 26(2) (2006) 343-349
DOI: 10.7151/dmgt.1325

ORTHOGONAL DOUBLE COVERS OF COMPLETE GRAPHS BY FAT CATERPILLARS

Dalibor Froncek

Department of Mathematics and Statistics
University of Minnesota Duluth
1117 University Dr, Duluth, MN 55812, USA
e-mail: dfroncek@d.umn.edu

Uwe Leck

Institut für Mathematik, Universität Rostock
18051 Rostock, Germany
e-mail: uwe.leck@uni-rostock.de

Abstract

An orthogonal double cover (ODC) of the complete graph Kn by some graph G is a collection of n spanning subgraphs of Kn, all isomorphic to G, such that any two of the subgraphs share exactly one edge and every edge of Kn is contained in exactly two of the subgraphs. A necessary condition for such an ODC to exist is that G has exactly n−1 edges. We show that for any given positive integer d, almost all caterpillars of diameter d admit an ODC of the corresponding complete graph.

Keywords: ODC, orthogonal double cover, graph decomposition, self-orthogonal factorization.

2000 Mathematics Subject Classification: 05B40, 05C70.

References

[1] H.-D.O.F. Gronau, M. Grüttmüller, S. Hartmann, U. Leck and V. Leck, On orthogonal double covers of graphs, Des. Codes Cryptogr. 27 (2002) 49-91, doi: 10.1023/A:1016546402248.
[2] H.-D.O.F. Gronau, R.C. Mullin and A. Rosa, Orthogonal double covers of complete graphs by trees, Graphs Combin. 13 (1997) 251-262.
[3] U. Leck, A class of 2-colorable orthogonal double covers of complete graphs by hamiltonian paths, Graphs Combin. 18 (2002) 155-167, doi: 10.1007/s003730200010.
[4] U. Leck and V. Leck, On orthogonal double covers by trees, J. Combin. Des. 5 (1997) 433-441, doi: 10.1002/(SICI)1520-6610(1997)5:6<433::AID-JCD4>3.0.CO;2-G.
[5] U. Leck and V. Leck, Orthogonal double covers of complete graphs by trees of small diameter, Discrete Appl. Math. 95 (1999) 377-388, doi: 10.1016/S0166-218X(99)00087-6.
Received 8 February 2005
Revised 14 August 2005