Information Technology Reference
In-Depth Information
maximal
if all its faces have degree three. Let
G
=(
V,E
) be a maximal outerpillar and
let
G
∗
be its weak dual. Let
E
1
ↆ
E
be the set of edges of
G
whose dual edges are in
the spine of
G
∗
.Theedges in
E
1
induce a subgraph
C
of
G
that is a caterpillar.
C
is
called the
backbonecaterpillar
of
G
. The vertices not in
C
are called
tip vertices
of
G
.
Theorem 7.
Everymaximalouterpillarisan EAQPgraph.
Proof.
Let
G
be a maximal outerpillar. We define a
y
-leveling
of
G
as follows. Let
C
be the backbone caterpillar of
G
,andlet
v
1
,v
2
,...,v
h
be the vertices of the spine
of
C
in the order they appear along the spine (for a chosen walking direction). Let
n
i
(with
n
i
≥
Y
0)bethenumber of degree-one vertices of
C
adjacent to
v
i
(for
i
=
1
,
2
,...,h
). We set
Y
(
v
1
)=0and for each vertex
v
i
(1
<i
≤
h
)of
G
we set
(
v
i
)=
i−
1
Y
j
=1
2(
n
j
+1).Let
w
i,
1
,w
i,
2
,...,w
i,n
i
be the degree one nodes of
C
that
are adjacent to
v
i
(for
i
=1
,
2
,...,h
); we set
j
. Finally, let
u
be a tip vertex of
G
;
u
is adjacent to two vertices
u
1
and
u
2
of
C
.Suppose that
Y
Y
(
w
i,j
)=
Y
(
v
i
)+2
·
(
u
1
)
<
1.
Since the vertices of
G
have been assigned a different value,
Y
(
u
2
),thenweset
Y
(
u
)=
Y
(
u
2
)
−
Y
is a valid
y
-leveling.
Consider now an arbitrary
x
-leveling
X
. We show that
ihs
(
ʓ
(
X
,
Y
))
≤
2.Let
be the
stabber at
l
, with
l
2 (where
n
C
is the number of vertices of
C
)then
does not intersect any edge. If
l
=2
i
for some 0
∈
R
.If
l<
0 or
l>
2
n
c
−
≤
i
≤
n
c
−
1,then
passes
throughavertex
w
of
C
.If
w
is a vertex of the spine of
C
,say
v
j
(for 1
h
), then
intersects all edges incident to
v
j
andatmosttwoedges both incident to
v
j−
1
.Thus
intersects at most two independent edges. If
w
is a degree-one vertex of
C
,say
w
i,j
,
then
intersects all edges incident to
w
i,j
and some of the edges incident to
v
i
.Also,
in this case it intersects at most two independent edges. Consider now the case when
2
i<l<
2
i
+2,andlet
w
1
and
w
2
be the two vertices of
C
such that
≤
j
≤
Y
(
w
1
)=2
i
and
Y
h
);
in this case
w
2
is either the next vertex of the spine of
C
,i.e.
v
j
+1
,oradegree-one
vertex adjacent to
v
j
,i.e.
w
i,
1
. In both cases
intersects some edges incident to
v
j
,
edge (
v
j−
1
,w
2
), and, if a tip vertex
u
adjacent to
v
j−
1
and
w
2
exists, at most two edges
(
v
j−
1
,u
) and (
w
2
,u
); in any case
intersects at most two independent edges. Suppose
then that
w
1
is a degree-one vertex of
C
,say
w
j,k
(1
(
w
2
)=2
i
+2.Suppose first that
w
1
is a vertex of the spine of
C
,say
v
j
(1
≤
j
≤
n
j
); in
this case
w
2
is either another degree-one vertex adjacent to
v
j
,i.e.
w
j,k
+1
, or the next
vertex on the spine of
C
,i.e.
v
j
+1
. In both cases
intersects some edges incident to
v
j
,
the edge (
w
1
,w
2
), and, if a tip vertex
u
adjacent to
w
1
and
w
2
exists, at most the two
edges (
w
1
,u
) and (
w
2
,u
);again,
intersects at most two independent edges. Hence
ihs
≤
j
≤
h
, 1
≤
k
≤
(
ʓ
(
X
,
Y
))
≤
2, which implies that
ihs
(
G
)
≤
2 and that
G
is an EAQPgraph.
Theorems 4, 5, and 7 imply the following.
Corollary 3.
Any tree and any cycle have aSGQPE. Any tree and any maximalouter-
pillar have aSGQPE.
