Orthogonal double covers of complete graphs by fat caterpillars
Discussiones Mathematicae Graph Theory (2006)
- Volume: 26, Issue: 2, page 343-349
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topDalibor Froncek, and Uwe Leck. "Orthogonal double covers of complete graphs by fat caterpillars." Discussiones Mathematicae Graph Theory 26.2 (2006): 343-349. <http://eudml.org/doc/270256>.
@article{DaliborFroncek2006,
abstract = {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.},
author = {Dalibor Froncek, Uwe Leck},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {ODC; orthogonal double cover; graph decomposition; self-orthogonal factorization},
language = {eng},
number = {2},
pages = {343-349},
title = {Orthogonal double covers of complete graphs by fat caterpillars},
url = {http://eudml.org/doc/270256},
volume = {26},
year = {2006},
}
TY - JOUR
AU - Dalibor Froncek
AU - Uwe Leck
TI - Orthogonal double covers of complete graphs by fat caterpillars
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 2
SP - 343
EP - 349
AB - 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.
LA - eng
KW - ODC; orthogonal double cover; graph decomposition; self-orthogonal factorization
UR - http://eudml.org/doc/270256
ER -
References
top- [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. Zbl1001.05091
- [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. Zbl0885.05093
- [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. Zbl0988.05074
- [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 Zbl0914.05014
- [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. Zbl0932.05075
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.