Information Technology Reference
In-Depth Information
AEQP
EAQP
AEP = ULP
EAP
fat caterpillars
Fig. 4.
Proper inclusions among the different classes of graphs studied in this paper
Radius-2 Star.
(see Fig.5(a)).Let
G
be a radius-2 star and let
v
be the uniquevertexof
G
with degree larger than two. Denote by
u
1
,u
2
,...,u
k
the neighbors of
v
and denote
by
w
i
the neighbor of
u
i
different from
v
(if it exists). We define a
y
-leveling
Y
of
G
as
follows. We set
(
w
i
)=2
i
.
Extended Degree-3 Spider.
Let
G
be an extended degree-3 spider. Suppose first that
G
is a 1-connected extended degree-3 spider (see Fig. 5(b)). We can assume that
G
is
full
,
i.e., it has the two optional edges (if
G
is not full we can temporarily add the additional
edges to
G
). Since
G
is full it consists of a cycle
C
,plusavertex
v
connected to two
consecutive vertices of
C
,plusapath
P
attached to
v
. Denote by
u
1
,u
2
,...u
k
the
vertices of
C
(in the order they appear on
C
), where
u
1
and
u
2
are the vertices adjacent
to
v
. Denote by
w
1
,w
2
,...,w
h
the vertices of
P
(in the order they appear on
P
),
where
w
1
is the vertex adjacent to
v
.Wedefinea
y
-leveling
Y
(
v
)=0,
Y
(
u
i
)=2
i
−
1,and
Y
Y
of
G
as follows. We set
Y
i
.Suppose now that
G
is a 2-connected extended
degree-3 spider (see Fig.5(c)).If
G
is a cycle where one edge has been replaced by
a
K
3
gadget, then it is a subgraph of a full 1-connected extended degree-3 spider and
therefore a
y
-leveling for
G
can be defined as in the previous case. If
G
is a cycle where
one edge has been replaced by a
C
4
gadget, then
G
is the subgraph of a 2-connected
extended degree-3 spider consisting of a cycle where one edge has been replaced by a
kite gadget, and a
y
-leveling for
G
can be defined as in the next case. Thus, suppose
that
G
is a cycle where one edge has been replaced by a kite gadget. In this case
G
consists of a cycle
C
plusavertex
v
adjacent to three consecutive vertices of
C
. Denote
by
u
1
,u
2
,...u
k
the vertices of
C
(in the order they appear on
C
), where
u
1
,
u
2
,and
u
3
are the vertices adjacent to
v
.Wedefinea
y
-leveling
(
v
)=0,
Y
(
u
i
)=
i
,and
Y
(
w
i
)=
−
(
u
i
)=
i
.
Generalized Caterpillar.
(see Fig.5(d)).Let
G
be a generalized caterpillar.
G
consists
of a caterpillar
C
where some edges of the spine and (possibly) two non spine edges
have been replaced by a gadget. We first describe a
y
-leveling
Y
Y
(
v
)=0and
Y
setting
for
C
andthenextend
it to the vertices of
G
that are not in
C
.Let
u
1
,u
2
,...,u
k
be the vertices of the spine of
C
.Ifanedge connecting
u
1
to a leaf is replaced by a gadget in
G
, then let this leaf be
denoted by
u
0
;analogously, if an edge connecting
u
k
to a leaf is replaced by a gadget
in
G
, then let this leaf be denoted by
u
k
+1
.Weset
Y
(
u
i
)=2
i
(
i
=0
,
1
,...,k
+1).
Denote by
w
i,
1
,w
i,
2
,...w
i,h
the leaves adjacent to
u
i
.Weset
Y
(
u
i
)+
j
h
+1
.
Suppose that edge (
u
i
,u
i
+1
) (
i
=0
,
1
,...,k
) is replaced by a gadget
ʳ
in
G
.Let
v
i,
1
,v
i,
2
,...v
i,h
(
h
Y
(
w
i,j
)=
Y
≥
1) be the vertices of
ʳ
other than
u
i
and
u
i
+1
.Weset
Y
(
v
i,j
)=
2
i
+1+
j−
1
h
(for
j
=1
,
2
,...,h
).
