Information Technology Reference
In-Depth Information
which has the same vertex set as
D
and has an edge between two distinct vertices
x
and
y
if and only if
N
D
(
x
)
N
D
(
y
)
. R. D. Dutton and R. C. Brigham
[
4
] and F. S. Roberts and J. E. Steif [
13
] gave characterizations of competition
graphs by using edge clique covers of graphs. The notion of competition graphs
was introduced by J. E. Cohen [
3
] in 1968 in connection with a problem in
ecology, and several variants and generalizations of competition graphs have
been studied.
In 1987, D. D. Scott [
16
] introduced the notion of double competition graphs
as a variant of the notion of competition graphs. The
double competition graph
(or the
competition-common enemy graph
or the
CCE graph
) of a digraph
D
is the graph which has the same vertex set as
D
and has an edge between two
distinct vertices
x
and
y
if and only if both
N
D
(
x
)
∩
=
∅
N
D
(
y
)
and
N
D
(
x
)
∩
=
∅
∩
N
D
(
y
)
hold. See [
8
,
10
,
15
] for recent results on double competition graphs.
A
multigraph
M
is a pair (
V
(
M
)
,E
(
M
)) of a set
V
(
M
)of
vertices
and a
multiset
E
(
M
) of unordered pairs of vertices, called
edges
. Note that, in our
definition, multigraphs have no loops. We may consider a multigraph
M
as the
pair (
V
(
M
)
,m
M
) of the vertex set
V
(
M
) and the nonnegative integer-valued
=
∅
function
m
M
:
2
ₒ
Z
≥
0
on the set
2
of all unordered pairs of
V
where
m
M
(
) is defined to be the number of multiple edges between the vertices
x
and
y
in
M
. The notion of competition multigraphs was introduced by C. A.
Anderson, K. F. Jones, J. R. Lundgren, and T. A. McKee [
1
] in 1990 as a variant
of the notion of competition graphs. The
competition multigraph
of a digraph
D
is the multigraph which has the same vertex set as
D
and has
m
xy
multiple
edges between two distinct vertices
x
and
y
, where
m
xy
is the nonnegative integer
defined by
m
xy
=
{
x, y
}
N
D
(
x
)
N
D
(
y
)
|
∩
|
. See [
14
,
19
] for recent results on competition
multigraphs.
In [
12
], the authors introduced the notion of the double competition multi-
graph of a digraph. The
double competition multigraph
of a digraph
D
is the
multigraph which has the same vertex set as
D
and has
m
xy
multiple edges
between two distinct vertices
x
and
y
, where
m
xy
is the nonnegative integer
defined by
N
D
(
x
)
N
D
(
y
)
N
D
(
x
)
N
D
(
y
)
m
xy
=
|
∩
|·|
∩
|
.
Recall that a
clique
of a multigraph
M
is a set of vertices of
M
which are
pairwise adjacent. We consider the empty set
as a clique of any multigraph
for convenience. A multiset is also called a
family
.An
edge clique partition
of a
multigraph
M
is a family
∅
of cliques of
M
such that any two distinct vertices
x
and
y
are contained in exactly
m
M
(
F
.
A digraph
D
is said to be
acyclic
if
D
has no directed cycles. An ordering
(
v
1
,...,v
n
) of the vertices of a digraph
D
, where
n
is the number of vertices of
D
, is called an
acyclic ordering
of
D
if (
v
i
,v
j
)
{
x, y
}
) cliques in the family
F
A
(
D
) implies
i<j
.Itiswell
known that a digraph
D
is acyclic if and only if
D
has an acyclic ordering. For
a positive integer
n
, let [
n
] denote the set
∈
{
1
,
2
,...,n
}
.
In [
12
], the authors gave a characterization of the double competition multi-
graphs of acyclic digraphs in terms of edge clique partitions of the multigraphs.
Search WWH ::
Custom Search