Isomorphic Boolean networks and dense interaction graphs

Abstract: A Boolean network (BN) with

n

components is a discrete dynamical system described by the successive iterations of a function

f : {0, 1}^{n} o {0, 1}^{n}

. In most applications, the main parameter is the interaction graph of

f

: the digraph with vertex set

1, d o t s, n

that contains an arc from

j

to

i

if

f_{i}

depends on input

j

. What can be said on the set

m a t h c a l G (f)

of the interaction graphs of the BNs

h

isomorphic to

f

, that is, such that

h c i r c p i = p i c i r c f

for some permutation

p i

of

{0, 1}^{n}

? It seems that this simple question has never been studied. Here, we report some basic facts. First, if

n g e q 5

and

f

is neither the identity or constant, then

m a t h c a l G (f)

is of size at least two and contains the complete digraph on

n

vertices, with

n^{2}

arcs. Second, for any

n g e q 1

, there are

n

-component BNs

f

such that every digraph in

m a t h c a l G (f)

has at least

n^{2} / 9

arcs.

This page was built for publication: Isomorphic Boolean networks and dense interaction graphs