Information Technology Reference
In-Depth Information
The Double Multicompetition Number
of a Multigraph
B
Jeongmi Park
1
and Yoshio Sano
2(
)
1
Department of Mathematics, Pusan National University, Busan 609-735, Korea
jm1015@pusan.ac.kr
2
Division of Information Engineering, Faculty of Engineering,
Information and Systems, University of Tsukuba, Ibaraki 305-8573, Japan
sano@cs.tsukuba.ac.jp
Abstract.
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 defined to be
the number of common out-neighbors of
x
and
y
in
D
times the number
of common in-neighbors of
x
and
y
in
D
.
In this paper, we introduce the notion of the double multicompetition
number of a multigraph. It is easy to observe that, for any multigraph
M
,
M
together with suciently many isolated vertices is the double
competition multigraph of some acyclic digraph. The double multicom-
petition number of a multigraph is defined to be the minimum number
of such isolated vertices. We give a characterization of multigraphs with
bounded double multicompetition number and give a lower bound for
the double multicompetition numbers of multigraphs.
·
·
Keywords:
Intersection graph
Double competition multigraph
·
Double multicompetition number
Acyclic digraph
2010 Mathematics Subject Classification:
05C20, 05C75.
1
Introduction
The competition graph of a digraph is defined to be the intersection graph of
the family of the out-neighborhoods of the vertices of the digraph (see [
11
]for
intersection graphs). A
digraph
D
is a pair (
V
(
D
)
,A
(
D
)) of a set
V
(
D
)of
vertices
and a set
A
(
D
) of ordered pairs of vertices, called
arcs
. An arc of the form (
v, v
)
is called a
loop
.Foravertex
x
in a digraph
D
, we denote the
out-neighborhood
of
x
in
D
by
N
D
(
x
) and the
in-neighborhood
of
x
in
D
by
N
D
(
x
), i.e.,
N
D
(
x
):=
{
and
N
D
(
x
):=
.A
graph
G
is a pair (
V
(
G
)
,E
(
G
)) of a set
V
(
G
)of
vertices
and a set
E
(
G
) of unordered
pairs of vertices, called
edges
.The
competition graph
of a digraph
D
is the graph
v
∈
V
(
D
)
|
(
x, v
)
∈
A
(
D
)
}
{
v
∈
V
(
D
)
|
(
v, x
)
∈
A
(
D
)
}
Yoshio Sano - This work was supported by JSPS KAKENHI grant number 25887007.
Search WWH ::
Custom Search