Information Technology Reference
In-Depth Information
.
.
(b)
K
3
gadget
(d)
C
4
(a) Kite gadget
(c)
K
3
gadget
gadget
(e)
C
4
gadget
(f)
K
4
gadget
Fig. 1.
Illustration of the different gadgets. Bigger vertices are the poles of the gadget
Given an edge
e
of a graph, replacing
e
with one of the gadgets means to replace
e
with the gadget so that the end-vertices of
e
coincide with the two poles of the gadget.
The
kite gadget
is a 4-cycle plusanedge connecting the two vertices that are not poles
(Fig.1(a)).A
K
3
gadget
is a set of
k
13-cycles sharing the two poles and the edge
connecting them (Fig.1(b)).A
K
3
gadget consisting of a single cycle is called a
K
3
gadget
(Fig.1(c)).A
C
4
≥
2 paths with two edges, connecting the
two poles (Fig.1(d)).A
C
4
gadget consisting of exactly two paths is called a
C
4
gadget
(Fig.1(e)).A
K
4
gadget
is the complete graph on four vertices (Fig. 1(f)). The poles
of a
K
4
gadget are any two of its vertices. A
star
is a graph
K
1
,k
for some
k
gadget
is a set of
k
≥
3.A
radius-2 star
is a star in which at least one edge has been subdivided once (see Fig.2(a)).
A
degree-3 spider
is an arbitrary subdivision of
K
1
,
3
.A
1-connected extended degree-3
spider
is a degree-3 spider with two optional additional edges: an edge connecting two
vertices adjacent to the uniquedegree-3 vertex and an edge connecting two leaves (see
Fig.2(b)).A
2-connected extended degree-3 spider
is either a cycle or a cycle where an
edge is replaced by a
K
3
gadget, a
C
4
gadget, or a kite gadget (see Fig.2(c)).An
ex-
tended degree-3 spider
is either a 1-connected extended degree-3 spider or a 2-connected
extended degree-3 spider. A
caterpillar
is a tree such that removing all leaves we get a
path, called the
spine
of the caterpillar. A
generalized caterpillar
is a caterpillar in which
each edge of the spine can be replaced by a
K
3
gadget, or a
C
4
gadget, or a kite gadget,
and for each endvertex
u
of the spine, one edge connecting
u
to a leaf can be replaced
by a
K
3
gadget, or a
C
4
gadget, or a kite gadget, or a
K
4
gadget (see Fig.2(d)).
We define a new family of graphs that we call
fatcaterpillars
and that is a subfamily
of generalized caterpillars. A
fatcaterpillar
is a graph obtained from a caterpillar by
replacing some of the edges of the spine with a
K
3
gadget (see Fig. 2(e)). Notice that fat
caterpillars are exactly the generalized caterpillars with no cycle of length larger than
three. Let
G
be the subgraph of
G
obtained by removing all degree-one vertices;
G
consists of a path
ʠ
=(
v
1
,v
2
,...,v
k
) plus a set of vertices each adjacent to two con-
secutive vertices of
ʠ
. The vertices of
ʠ
are called the
pathvertices
of
G
; in particular
v
1
and
v
k
are called
extremepathvertices
. The remaining vertices of
G
are called the
tip vertices
of
G
; a tip vertex that is adjacent to
v
i
and
v
i
+1
will be denoted by
u
i
. Each
vertex of
G
of degree one is adjacent to a path vertex. The degree-one vertices adjacent
to
v
i
will be denoted by
w
i,j
, with
j
=1
,
2
,...,h
i
,where
h
i
≥
≥
0. We start with a
technical lemma that will be used to characterize EAPgraphs.
Lemma 4.
A graph
G
is an EAPgraph if andonly if
ihs
(
G
)=1
.
The next lemma can be proved by showing that, in each case,
ihs
(
G
)
>
1,which,by
Lemma 4, implies that
G
∈
EAP
.
