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

Proof. First, we show the “only-if” part. Suppose that a multigraph M has the
double multicompetition number at most k .Let M I k . Then M is

the double competition multigraph of an acyclic digraph. By Theorem 1 , there
exist an ordering ( v 1 ,...,v n + k ) of the vertices of M

:= M ∪

and a double indexed

of M such that the conditions
(I) and (IV) in Theorem 1 hold. Without loss of generality, we may assume
that I k =

edge clique partition F = { S ij | i, j ∈ [ n + k ] }

v 1 ,...,v t }∪{ v n + t +1 ,...,v n + k }

{ for some nonnegative integer t with

0 if they exist. Since the

vertices in I k are isolated, there is no clique S ij of size at least two containing
a vertex in I k . Let ( v 1 ,...,v n ):=( v t +1 ,...,v t + n ). Then, it follows from the
conditions (I) and (IV) for ( v 1 ,...,v n + k )and

≤ t ≤ k . We delete all the cliques of size one from F

F that the integer t , the ordering

( v 1 ,...,v n ), and the family satisfy the conditions (i) and (ii).

Next, we show the “if” part. Suppose that there exist an integer t such that

F

0 k ,anordering( v 1 ,...,v n ) of the vertices of M , and a double indexed

edge clique partition

≤ t ≤

of M such that the conditions (i)
and (ii) hold. Then, we define a digraph D by V ( D ):= V ( M )

{ S ij | i, j ∈ [ n + k ] }

∪ A ∪ Z , where

A := { a 1 ,...,a t } and Z := { z 1 ,...,z k−t } ,and

⊛ ⊞

⊝ ⊠

A ( D ):= { ( a i ,v ) , ( v, v j−t ) }

v ∈ S ij

( i,j ) ∈ Λ 1 × Λ 2

⊛ ⊞

⊝ ⊠

∪ { ( a i ,v ) , ( v, z j− ( n + t ) ) }

( i,j ) ∈ Λ 1 × Λ 3

v∈S ij

⊛ ⊞

⊝ ⊠

∪ { ( v i−t ,v ) , ( v, v j−t ) }

( i,j ) ∈ Λ 2 × Λ 2 ,i<j v∈S ij

⊛ ⊞

⊝ ⊠ .

∪ { ( v i−t ,v ) , ( v, z j− ( n + t ) ) }

( i,j ) ∈ Λ 2 × Λ 3 v∈S ij

Then, we can check that the ordering ( a 1 ,...,a t ,v 1 ,...,v n ,z 1 ,...,z k−t )isan
acyclic ordering of D . Therefore the digraph D is acyclic. By the definition of
the digraph D , it follows that

N D ( v h )=

S t + h,j

j∈ Λ 2 ∪ Λ 3 ,t + h<j

∪{ v j−t | v h ∈ S ij , ( i, j ) ∈ (Λ 1 ∪ Λ 2 ) × Λ 2 ,i < j }

∪{ z j− ( n + t ) | v h ∈ S ij , ( i, j ) ∈ (Λ 1 ∪ Λ 2 ) × Λ 3 } ,

N D ( v h )= S i,t + h

i∈ Λ 1 ∪ Λ 2 ,i<t + h

∪{ a i | v h ∈ S ij , ( i, j ) ∈ Λ 1 × (Λ 2 ∪ Λ 3 ) }

∪{ v i−t | v h ∈ S ij , ( i, j ) ∈

Λ 2 × (Λ 2 ∪ Λ 3 ) ,i < j

}