An orthogonal double cover (ODC) of the complete graph Kₙ by some graph G is a collection of n spanning subgraphs of Kₙ, all isomorphic to G, such that any two of the subgraphs share exactly one edge and every edge of Kₙ 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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1325,
author = {Dalibor Froncek and Uwe Leck},
title = {Orthogonal double covers of complete graphs by fat caterpillars},
journal = {Discussiones Mathematicae Graph Theory},
volume = {26},
year = {2006},
pages = {343-349},
zbl = {1140.05319},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1325}
}
Dalibor Froncek; Uwe Leck. Orthogonal double covers of complete graphs by fat caterpillars. Discussiones Mathematicae Graph Theory, Tome 26 (2006) pp. 343-349. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1325/
[000] [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. | Zbl 1001.05091
[001] [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. | Zbl 0885.05093
[002] [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. | Zbl 0988.05074
[003] [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 | Zbl 0914.05014
[004] [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. | Zbl 0932.05075