Biology Reference
In-Depth Information
This fact guarantees that the constructions below add the maximum number of
vertices allowed by the result.
Case 1:
Suppose that
T
(
w
1
)=
∅
Then, (2
|T
(
w
1
)
|−|N
(
w
1
)
|
)
+
=0,and
.
ˆ
(
w
1
)
N
(
w
1
)
|
V
|
is either 0 or 1 depending on whether
|
|
is even or odd,
N
(
w
1
)
respectively. If
|
|
is even (odd), then no nodes are (a single node
ˆ
V
,
E
).Let
N
(
w
1
)
(
w
1
)
is) added to (
=2
p
for the natural
number
p
.Let
k
be a natural number so that 2
k
>
2
p
. List the elements
of
W
,
|
∪
V
|
2
k
.
k
lexicographically as
h
1
,
h
2
,...,
h
{−
1
,
1
}
Then, denoting the
ˆ
elements of
N
(
w
1
)
(
w
1
) as
v
i
for
i
=1
,
2
,...,
2
p
,wedefine
η
and
∪
V
γ
by
(
η
(
v
)
,
1
,
1
,...,
1)
,
∈V
v
i
+1
)
,
v
=
v
i
,
i
=1
,
2
,...p
(1
,
1
,...,
1
,
h
η
:
¯
n
+
k
:
v
V→{−
1
,
1
}
→
2
k
−i
+
p
)
,v
=
v
i
,
i
=
p
+1
,...
2
p
(1
,
1
,...,
1
,
h
and
(
γ
(
v
)
,
2
,
2
,...,
2)
,
∈W
(2
,
2
,...
2
,
0
,
0
,...
0)
,w
=
w
1
,
w
n
+
k
:
w
γ
:
W→{−
2
,
0
,
2
}
→
where
γ
(
w
1
) has
k
zeros. We mention that Lemma 6.1 is used to guar-
antee that the last
k
elements of
η
(
v
i
),for
i
=1
,
2
,...,
2
p
, can be paired
to satisfy the definition of a diversity graph.
Case 2:
Suppose
T
(
w
1
)
∅
=
. The difficulty with this case lies in the fact that
η
(
v
) is defined for
v
∈
T
(
w
1
). Notice that
N
(
w
1
)
T
(
w
1
)
T
(
w
1
)
N
(
w
1
)
(
|
|−
2
|
|
)+(2
|
|−|
|
)
+
N
(
w
1
)
T
(
w
1
)
=(
|
|−
2
|
|
)
+
≥
0
,
in (
N
(
w
1
)
∪
which
guarantees
that
there
are
enough
nodes
ˆ
(
w
1
))
T
(
w
1
) to be uniquely paired with the nodes in
T
(
w
1
).Let
V
\
ˆ
Z,Z
C
be a two set partition of (
N
(
w
1
)
(
w
1
))
T
(
w
1
) so that
{
}
∪
V
\
. Notice that the definition of
ˆ
T
(
w
1
)
(
w
1
) guarantees that both
|
Z
|
=
|
|
V
T
(
w
1
)
Z
C
|
are even.
List the elements of
T
(
w
1
),
Z
and
Z
C
so that
∪
Z
|
and
|
|
v
1
,v
2
,...,v
|T
(
w
1
)
|
}
T
(
w
1
)=
{
,
(6.3)
v
|T
(
w
1
)
|
+1
,v
|T
(
w
1
)
|
+2
,...,v
2
|T
(
w
1
)
|
}
Z
=
{
,
and
(6.4)
v
2
|T
(
w
1
)
|
+1
,v
2
|T
(
w
1
)
|
+2
,...,v
| V
(
w
1
)
|
}
Z
C
=
{
.
(6.5)
Search WWH ::
Custom Search