TY - JOUR
T1 - Orthogonal double covers of complete graphs by caterpillars of diameter 5
AU - Froncek, Dalibor
PY - 2007/4/1
Y1 - 2007/4/1
N2 - An orthogonal double cover (ODC) of the complete graph K n by a graph G is a collection [InlineMediaObject not available: see fulltext.] = {G i |i = 1,2, . . . ,n} of spanning subgraphs of K n , all isomorphic to G, with the property that every edge of K n belongs to exactly two members of [InlineMediaObject not available: see fulltext.] and any two distinct members of [InlineMediaObject not available: see fulltext.] share exactly one edge. A caterpillar of diameter five is a tree arising from a path with six vertices by attaching pendant vertices to some or each of its vertices of degree two. We show that for any caterpillar of diameter five there exists an ODC of the complete graph K n .
AB - An orthogonal double cover (ODC) of the complete graph K n by a graph G is a collection [InlineMediaObject not available: see fulltext.] = {G i |i = 1,2, . . . ,n} of spanning subgraphs of K n , all isomorphic to G, with the property that every edge of K n belongs to exactly two members of [InlineMediaObject not available: see fulltext.] and any two distinct members of [InlineMediaObject not available: see fulltext.] share exactly one edge. A caterpillar of diameter five is a tree arising from a path with six vertices by attaching pendant vertices to some or each of its vertices of degree two. We show that for any caterpillar of diameter five there exists an ODC of the complete graph K n .
KW - Orthogonal double cover
KW - Orthogonal labeling
UR - http://www.scopus.com/inward/record.url?scp=34247250335&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34247250335&partnerID=8YFLogxK
U2 - 10.1007/s00373-007-0693-4
DO - 10.1007/s00373-007-0693-4
M3 - Article
AN - SCOPUS:34247250335
SN - 0911-0119
VL - 23
SP - 145
EP - 163
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
IS - 2
ER -