The Double Multicompetition Number of a Multigraph - Discrete and Computational Geometry and Graphs - page 141

Proof. Let k := dk ∗ ( M ). Then, there exists an acyclic digraph D whose double
competition multigraph is M

I k . Let ( v 1 ,...,v n + k ) be an acyclic ordering of
D .Let i be the minimum index such that v i ∈

∪

V ( M ) and let j be the maximum

index such that v j ∈ j ). Since M has no isolated

vertices, the vertex v i (and v j ) has at least one incident edge. Therefore, v i (and
v j ) must have both an in-neighbor and an out-neighbor in D . Since v i has an
in-neighbor, we have i

V ( M ). Then k ≥ ( i − 1)+( n + k −

≥ 2. Since v j has an out-neighbor, we have j ≤ n + k − 1.

Thus we obtain k ≥ 2. Hence the lemma holds.

2 , dk ∗ ( P n )=2 . Example 4. For a path P n of order n with n ≥

Proof. Let P n be the path with V ( P n )= { v 1 ,...,v n } and E ( P n )= {{ v i ,v i +1 }|

i ∈{ 1 ,...,n − 1 }} . We define a digraph D by V ( D )= { v 1 ,...,v n }∪{ a, z }

n− 2
i =1 {

and A ( D )= { ( a, v 1 ) , ( a, v 2 ) }∪ ( v i ,v i +1 ) , ( v i ,v i +2 ) } ∪{ ( v n− 1 ,v n ) }∪

{ , where a and z are new vertices. Then, the digraph D is

acyclic since the ordering ( a, v 1 ,...,v n ,z ) is an acyclic ordering of D .Wecan
easily check that the double competition multigraph of D is P n ∪{

( v n− 1 ,z ) , ( v n ,z ) }

a, z } .Thus

dk ∗ ( P n ) 2. By Lemma 3 , dk ∗ ( P n ) 2. Hence dk ∗ ( P n )=2.

≤ ≥

Now, we give a characterization for multigraphs with bounded double multicom-
petition number, which is an extension of Theorem 1 .

Theorem 5. Let M be a multigraph with n vertices. Let k be a nonnegative
integer. Then, the double multicompetition number of M is at most k if and only
if there exist an integer t such that 0 k ,anordering ( v 1 ,...,v n ) of the

vertices of M , and a double indexed edge clique partition

≤ t ≤

{ S ij | i, j ∈ [ n + k ] } 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 t + i,t + j ,where A i and

B j are the sets defined for i, j ∈ [ n ] by

⊛ ⊞

⊝ ⊠ ∪{

A i = S t + i,t + p , v b−t | v i ∈ S ab ( a, b ∈{ t +1 ,...,t + n } ) } ,

p ∈ [ n + k − t ]

⊛ ⊞

⊝ ⊠ ∪{

B j = S t + q,t + j , v a−t | v j ∈ S ab ( a, b ∈{ t +1 ,...,t + n } ) } .

q ∈ [ n + k − t ]

(ii) Let Λ 1 = { 1 ,...,t } , Λ 2 = { t +1 ,...,t + n } ,and Λ 3 = { t + n +1 ,...,t + n +

( k − t )(= n + k ) } .

If ( i, j ) ∈ Λ 1 × Λ 2 , then S ij ↆ{ v 1 ,...,v ( j−t ) − 1 } .

If ( i, j ) ∈ Λ 1 × Λ 3 , then S ij ↆ{ v 1 ,...,v n } .

If ( i, j ) ∈ Λ 2 × Λ 2 and i<j , then S ij ↆ{ v ( i−t )+1 ,...,v ( j−t ) − 1 } .

If ( i, j ) ∈ Λ 2 × Λ 3 , then S ij ↆ{ v ( i−t )+1 ,...,v n } .

Otherwise, S ij = ∅ .