I 1, 2, - . - , N) of Spanning Subgraphs of K Pages, Satisfying The Following Two Properties

ORTHOGONAL DOUBLE COVERS OF COMPLETE
GRAPHS BY LOBSTERS OF DIAMETER 5
Dalibor Froncek
University of Minnesota Duluth
April 2005
Abstract. An orthogonal double cover (ODC) of the complete graph Kn

by a graph G is a collection G = {Gi |i = 1, 2, . . . , n} of spanning subgraphs
of Kn , all isomorphic to G, with the property that every edge of Kn belongs
to exactly two members of G and any two distinct members of G share
exactly one edge.
A lobster of diameter five is a tree arising from a double star by at-
taching any number of pendant vertices to each of its vertices of degree one.
We show that for any double star R(p, q) there exists an ODC of Kn by
all lobsters of diameter five (with finitely many possible exceptions) arising
from R(p, q).
1. Introduction
An orthogonal double cover (ODC) of the complete graph Kn is a
collection G = {Gi |i = 1, 2, . . . , n} of spanning subgraphs of Kn , called
pages, satisfying the following two properties:
(1) Double cover property: Every edge of Kn belongs to exactly two pages
of G.
(2) Orthogonality property: Any two distinct pages of G share exactly one
edge.
The definition immediately implies that every page of G must have
exactly n − 1 edges. If all pages of G are isomorphic to the same graph G,
then G is called an ODC of Kn by G.
2000 Mathematics Subject Classification. 05C70, 05B30.

Key words and phrases. Orthogonal double cover, orthogonal labeling .
Research for this article was in part supported by the University of Minnesota
Duluth Grant 177–1009
Typeset by AMS-TEX
1
ODCs have been investigated for more than 25 years, and there is
an extensive literature on the subject. For motivation and an overview of
results and problems in the area we refer to the survey paper [2].
As the condition on the number of edges of G is necessary for the
existence of an ODC by G, it is natural to ask whether there exist ODCs
for some classes of trees. It can be easily verified that there is no ODC
of K4 by P4 , the path of length three. For all other non-trivial trees on
at most 14 vertices ODCs of the corresponding complete graphs exist [2],
which supports the following conjecture by Gronau, Mullin, and Rosa [3].
Conjecture. (Gronau, Mullin, and Rosa) If T 6= P4 is a tree on n ≥ 2
vertices, then there is an ODC of Kn by T .
The conjecture trivially holds for stars, and it was shown to be true
for all trees of diameter three [3] (see also [4]). On the other hand, even for
paths a complete solution is not known. Therefore, we do not expect the
conjecture to be completely solved soon.
It was also proved for all caterpillars of diameter four [5]. A caterpillar
is a tree that is obtained by attaching pendant vertices of degree one to a
path. By R(p1 , p2 , . . . , pt ) we denote a caterpillar with t spine vertices and
pi pendant vertices attached to the i-th spine vertex (in natural order). We
of course assume that p1 , pt ≥ 1.
The only other class of trees of diameter four and five is the class of
lobsters. In general, a lobster is a tree that is obtained by attaching pendant
vertices of degree one to a caterpillar. Leck and Leck [5] proved that for a
fixed r, almost all lobsters of diameter four with the central vertex (i.e., the
only vertex of eccentricity 2) of degree r admit an ODC of the appropriate
Kn . The author strengthened their result by proving that for a fixed r, all
but possibly finitely many lobsters of diameter four with the central vertex
of degree r admit an ODC [1]. In this paper, we prove analogical result for
lobsters of diameter five. A lobster L of diameter five arises from a double
star R(p, q) by attaching pendant vertices to the leaves of the double star.
We say that R(p, q) is the base caterpillar or just base of the lobster L.
2. Another generalization of adding construction

In this section we describe a recursive method for constructing ODCs.
The method is a modification of the method originally developed by Leck
and Leck in [5], who call it the adding construction. The author generalized
the adding construction in [1]. A simple version appeared already as a part
of a construction of ODCs by double stars in [3]. To find an ODC by a
graph G, we will need two subgraphs of G, say G∗ , G0 , that both admit
certain type of orthogonal double cover and arise from G by deleting some
vertices of degree one.
2
Let G = {G1 , G2 , . . . , Gn } be an ODC of Kn by G defined by isomor-
phisms φi : G → Gi for i = 1, 2, . . . , n. A vertex v of G is surjective if
{φi (v)|i = 1, 2, . . . , n} = V (Kn ). Notice that in [5] surjective vertices are
called rotational.
The following lemma is an essential part of the adding construction.
A proof can be found in [1] or in [5] as a part of the proof of Lemma 6.
Lemma 1. Let Kr,s be a complete bipartite graph with bipartition X =

{x1 , x2 , . . . , xr }, Y = {y1 , y2 , . . . , ys }. Let G be a subgraph of Kr,s such
that degG (yj ) = 1 for every j = 1, 2, . . . , s and every yj is adjacent to
one of x1 , x2 , . . . , xm with 1 ≤ m ≤ r. Define Gi for i = 1, 2, . . . , r by
an isomorphism φi : G → Gi with the property that φi (xp ) 6= φj (xp ) for
p = 1, 2, . . . , m if i 6= j and φi (yq ) = yq for q = 1, 2, . . . , s.
Let F be the star induced by X ∪ {ys }. Let Fi for i = 1, 2, . . . , s be
defined by an isomorphism ψi : F → Fi with the property that ψi (ys ) = yi
for i = 1, 2, . . . , s and ψi (xq ) = xq for q = 1, 2, . . . , r. Then
(1) every edge of Kr,s appears in exactly one of the graphs G1 , G2 , . . . , Gr ,
(2) every edge of Kr,s appears in exactly one of the graphs F1 , F2 , . . . , Fs ,
and
(3) for any i ∈ {1, 2, . . . , r}, j ∈ {1, 2, . . . , s} the graphs Gi and Fj share
exactly one edge.
The following lemma will be also useful. The proof is an easy applica-
tion of Lemma 1 and can be found in [1].
Lemma 2. Let H = Kr + K s (i.e., H is the complete graph Kr+s with

all edges of some Ks removed). Let V (H) = X ∪ Y, X ∩ Y = ∅, where
hXi = Kr and hY i = K s . Let G 0 = {G01 , G02 , . . . , G0r } be an ODC of Kr
by G0 with V (G0 ) = X defined by G0i = φ0i (G0 ) and S ⊆ X be the set of
surjective vertices of G0 . Let G be a graph with the vertex set X ∪ Y that
arises from G0 by joining each vertex of Y to exactly one surjective vertex
of G0 . Let Gi for i = 1, 2, . . . , r be defined by φi (G), where φi (x) = φ0i (x)
for every x ∈ X and φi (y) = y for every y ∈ Y . Then every two pages
Gi , Gj share exactly one edge xp xq , every edge xp xq appears in exactly two
distinct pages, and every edge xp yt appears in exactly one page.
Next we present another generalization of the adding construction.
Lemma 3. Let G be a graph with the vertex set V, |V | = n = `k + m, 0 ≤

m ≤ min{` − 1, k − 1} and U ⊂ V be a set of vertices of degree one with
the following properties:
(1) W = V \ U , |W | = k, |U | = (` − 1)k + m, the graph G∗ = hW i allows
an ODC G ∗ of Kk and S ⊆ W is the set of surjective vertices of G∗
with respect to G ∗ ,
3
(2) in the bipartite graph with bipartition W, U there are at least b edge-
disjoint stars K1,k+1 with central vertices in S, where b = min{m, b 2` c},
and if b < b 2` c, then b 2` c − m more edge-disjoint stars K1,k .
If m ≥ 1, then let U 0 ⊂ V be a set of vertices of degree one (not necessarily
disjoint from U ) with the following properties:
(3) W 0 = V \U 0 , |W 0 | = k +1, |U 0 | = (`−1)k +m−1, the graph G0 = hW 0 i
allows an ODC G 0 of Kk+1 and S 0 ⊆ W 0 is the set of surjective vertices
of G0 with respect to G 0 ,
(4) in the bipartite graph with bipartition W 0 , U 0 there are at least b0 edge-
disjoint stars K1,k+1 with central vertices in S 0 , where b0 = min{m −
1, b 2` c}, and if b0 < b 2` c, then b 2` c − b0 more edge-disjoint stars K1,k .
Then G allows an ODC G of Kn .
Proof. We split V into ` disjoint subsets, V1 , V2 , . . . , V` , with |Vi | = k + 1
for i = 1, 2, . . . , m and |Vi | = k for i = m + 1, m + 2, . . . , ` if m < `. The
conditions (2) and (4) guarantee that whenever we place a copy of G0 into
one of V1 , V2 , . . . , Vm , or G∗ into one of Vm+1 , Vm+2 , . . . , V` , we have enough
stars K1,k+1 and/or K1,k whose vertices of degree one can be placed into at
least b 2` c other sets Vj such that each star “fills” with its leaves the whole
set Vj . More precisely, for every i = 1, 2, . . . , `, we can fill with the leaves
of a star K1,k+1 or K1,k (as needed) each of the sets Vi+1 , Vi+2 , . . . , Vi+b ` c ,
2
where the addition is taken modulo `.
Now let Gi,p and Gi,q be pages of G isomorphic to G that are placed
such that their subgraphs G0i,p and G0i,q isomorphic to G0 (or G∗i,p and G∗i,q
isomorphic to G∗ ) both belong to the set Vi . We apply Lemma 2 with
Vi = X, V \ Vi = Y and observe that Gi,p and Gi,q share exactly one edge
with both endvertices in Vi and each such an edge is contained in exactly
two pages Gi,p0 and Gi,q0 for some p0 , q 0 . It also follows that Gi,p and Gi,q
do not share any edge vi x with vi ∈ Vi , x 6∈ Vi or an edge xy with x, y 6∈ Vi .
We now denote by G̃i,p a page of G ∗ placed in Vi if m + 1 ≤ i ≤ ` or
a page of G 0 placed in Vi if 1 ≤ i ≤ m. If we then look at Gi,p with G̃i,p
placed in the set Vi and Gj,q with G̃j,q placed in the set Vj , we observe
that they can intersect only in some edge vi vj , where vi ∈ Vi , vj ∈ Vj . We
can assume WLOG that j ≤ i + b 2` c. Therefore, there is the star K1,k
(if m + 1 ≤ j ≤ `) or K1,k+1 (if 1 ≤ j ≤ m) with the central vertex vi
in Gi,p , while in Gj,q all vertices of Vi are of degree one. Thus, we can
apply Lemma 1 with Vi = Y, Vj = X and conclude that Gi,p and Gj,q share
exactly one edge. Again, if we let G̃i,p run through Vi and G̃j,q through Vj ,
from Lemma 1 we can see that each edge of the complete bipartite graph
with the partite sets Vi , Vj is contained in exactly two pages Gi,p0 and Gj,q0
for some p0 , q 0 . ¤
4
The graphs we will use in our constructions as G∗ , G0 have a cyclic
orthogonal double cover, or CODC for short. We say that Kn has a CODC
G = {G1 , G2 , . . . , Gn } by a graph G if V (Kn ) = {x1 , x2 , . . . , xn } and the
isomorphisms φ1 , φ2 , . . . , φn ; φi : G → Gi are defined as φi (xj ) = xj+i−1 for
every i, j = 1, 2, . . . , n, where the addition is taken modulo n with 0 replaced
by n. Notice that if G is cyclic, then all vertices of G are surjective.
3. The result
We noticed above that a lobster of diameter five is a tree arising from
a double star by attaching any number of pendant vertices to each of its
vertices of degree one. We will call the only two vertices of eccentricity 3
the primary vertices, and their neighbors (of eccentricity 4) the secondary
vertices. The vertices of degree one and eccentricity 5 are called leaves.
Recall that R(p1 , p2 , p3 ) is the caterpillar of diameter 5 with p1 and p3
leaves adjacent to the endvertices of the path P3 , respectively, and p2 leaves
attached to the central vertex of P3 .
We will use the following result by Leck and Leck [5].
Theorem 4. (Leck and Leck [5]) The caterpillar R(p1 , p2 , p3 ) admits a
CODC if p2 ≤ |p1 − p3 |.
Now we can prove our main result.
Theorem 5. Let L = L(p, q; 5) be a lobster of diameter 5 with the base
double star R(p, q) and n ≥ 4(p + q)(p + q + 1) vertices. Then there is an
ODC of Kn by L.
Proof. First we show that at least one secondary vertex has p + q or more
neighboring leaves. Suppose it is not the case. Then the number of leaves is
at most (p+q)(p+q −1) = (p+q)2 −(p+q) and the number of vertices of L
is at most (p+q)2 +2, which is a contradiction. Therefore, L contains either
R(p + q, p − 1, q) or R(p, q − 1, p + q). Each of them satisfies assumptions
of Theorem 4. Therefore, we can suppose WLOG it is the former. By
Theorem 4 it admits a CODC of K2(p+q)+2 , all of its vertices are surjective,
and we can choose it for G0 of Lemma 3. Similarly, R(p + q − 1, p − 1, q)
satisfies assumptions of Theorem 4. Hence it admits a CODC of K2(p+q)+1 ,
and we can choose it for G∗ of Lemma 3. Note that then k = 2(p + q) + 1.
Now we need to show that L has enough leaves to satisfy assumptions
(2) and (4) of Lemma 3. We again proceed by contradiction. The number
of secondary vertices of the base double star is p + q and the maximum
number of leaves that do not induce a star K1,k+1 is 2p + 2q + 1 at each
secondary vertex. Therefore, we have at most (p + q)(2p + 2q + 1) leaves not
included in the stars. These leaves fill at most p+q of the sets Vi . It remains
to show that the number of stars K1,k+1 and/or K1,k that fill all remaining
5
sets Vi is at least p + q. If this is so, then the number of sets Vi filled with
stars satisfies assumptions of Lemma 3. Hence, we suppose it is not the
case. Then we have at most p + q − 1 stars, and we can suppose they are
all the bigger ones, K1,2p+2q+2 . This gives at most (p + q − 1)(2p + 2q + 2)
vertices in the stars. The total number of vertices is then at most
(2p+2q+2)+(p+q)(2p+2q+1)+(p+q−1)(2p+2q+2) = (p+q)(4p+4q+3).
This contradicts our assumption that the number of vertices is at least

4(p + q)(p + q + 1). Therefore, the number of stars is sufficient. Now we
have verified all assumptions of Lemma 3 and the proof is complete. ¤
The corollary now follows immediately.
Corollary 6. Let p, q ≥ 1. Then all lobsters of diameter 5 with the base
double star R(p, q) with at most finitely many possible exceptions admit an
orthogonal double cover of the complete graph Kn .
References
1. D. Froncek, Orthogonal double covers of complete graphs by lobsters of diameter 4,
Congr. Numer. 177 (2005), 25–32.
2. H.-D.O.F. Gronau, M. Grüttmüller, S. Hartmann, U. Leck, and V. Leck, On orthog-
onal double covers of graphs, Des. Codes Cryptogr. 27 (2002), 49–91.
3. 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.
4. U. Leck and V. Leck, On orthogonal double covers by trees, J. Combin. Des. 5 (1997),
433–441.
5. U. Leck and V. Leck, Orthogonal double covers of complete graphs by trees of small
diameter, Discrete Appl. Math. 95 (1999), 377–388.
Department of Mathematics and Statistics, University of Minnesota

Duluth, 1117 University Dr., Duluth, MN 55812–3000, U.S.A.
E-mail address: dalibor@d.umn.edu

I 1, 2, - . - , N) of Spanning Subgraphs of K Pages, Satisfying The Following Two Properties

Uploaded by

Copyright:

Available Formats

I 1, 2, - . - , N) of Spanning Subgraphs of K Pages, Satisfying The Following Two Properties

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

I 1, 2, - . - , N) of Spanning Subgraphs of K Pages, Satisfying The Following Two Properties

Uploaded by

Copyright:

Available Formats

ORTHOGONAL DOUBLE COVERS OF COMPLETE

GRAPHS BY LOBSTERS OF DIAMETER 5

University of Minnesota Duluth

Abstract. An orthogonal double cover (ODC) of the complete graph Kn

2000 Mathematics Subject Classification. 05C70, 05B30.

2. Another generalization of adding construction

Lemma 1. Let Kr,s be a complete bipartite graph with bipartition X =

Lemma 2. Let H = Kr + K s (i.e., H is the complete graph Kr+s with

Next we present another generalization of the adding construction.

Lemma 3. Let G be a graph with the vertex set V, |V | = n = `k + m, 0 ≤

This contradicts our assumption that the number of vertices is at least

Department of Mathematics and Statistics, University of Minnesota

You might also like