Information Technology Reference
In-Depth Information
Theorem 1 [
12
].
Let
M
be a multigraph with
n
vertices. Then,
M
is the double
competition multigraph of an acyclic digraph if and only if there exist an ordering
(
v
1
,...,v
n
)
of the vertices of
M
and a double indexed edge clique partition
{
S
ij
|
i, j
∈
[
n
]
}
of
M
such that the following conditions hold:
(I)
for any
i, j
∈
[
n
]
,if
|
A
i
∩
B
j
|≥
2
, then
A
i
∩
B
j
=
S
ij
;
(IV)
for any
i, j, k
∈
[
n
]
,
v
k
∈
S
ij
implies
i<k<j
,
where
A
i
and
B
j
are the sets defined by
S
i∗
:=
p
T
i
T
i
A
i
=
S
i∗
∪
,
S
ip
,
:=
{
v
b
|
a, b
∈
[
n
]
,v
i
∈
S
ab
}
,
∈
[
n
]
S
∗j
:=
q∈
[
n
]
T
j
,
T
j
:=
B
j
=
S
∗j
∪
S
qj
,
{
v
a
|
a, b
∈
[
n
]
,v
j
∈
S
ab
}
.
In this paper, we introduce the notion of the double multicompetition num-
ber of a multigraph, and we give a characterization of multigraphs with bounded
double multicompetition number and give a lower bound for the double multi-
competition numbers of multigraphs.
2 Main Results
Proposition 2.
For any multigraph
M
, there exists a nonnegative integer
k
such that
M
I
k
is the double competition multigraph of an acyclic digraph,
where
I
k
is the set of
k
isolated vertices.
∪
}∈
V
(
M
)
2
Proof.
Let
M
=(
V
(
M
)
,m
M
) be a multigraph. Let
E
1
:=
{{
x, y
|
m
M
(
{
x, y
}
)
≥
1
}
,let
A
:=
{
a
{x,y}
|{
x, y
}∈
E
1
}
, and let
Z
:=
{
z
{x,y},i
|
{
x, y
}∈
E
1
,i
∈{
1
,...,m
M
(
{
x, y
}
)
}}
. We define a digraph
D
by
V
(
D
):=
V
(
M
)
∪
A
∪
Z
m
M
(
{x,y}
)
A
(
D
):=
{
(
a
{x,y}
,x
)
,
(
a
{x,y}
,y
)
,
(
x, z
{x,y},i
)
,
(
y, z
{x,y},i
)
}
.
{
x,y
}∈
E
1
i
=1
Then, the digraph
D
is acyclic and the double competition multigraph of
D
is
M
∪
I
k
, where
k
=
|
A
|
+
|
Z
|
. Hence the proposition holds.
By Proposition
2
, we can define the following:
Definition.
For a multigraph
M
,the
double multicompetition number
of
M
is
the minimum nonnegative integer
k
such that
M
I
k
is the double competition
multigraph of an acyclic digraph. We denote it by
dk
∗
(
M
).
∪
Lemma 3.
If a multigraph
M
has no isolated vertices, then
dk
∗
(
M
)
≥
2
.
Search WWH ::
Custom Search