2
$\begingroup$

Consider a finite set $X$ of order $n$ and a symmetric function $f: X \times X \rightarrow X$.

$f$ can straightforwardly be considered as a multidigraph with

  • $n$ "object" nodes, representing the elements of $X$, and

  • $n(n+1)/2$ "argument" nodes, representing the pairs of arguments of $f$.

Each of the $n$ object nodes has $n+1$ out-arrows to its corresponding argument nodes. Each of the $n(n+1)/2$ argument nodes has exactly 2 in-arrows from its correspoding object nodes and 1 out-arrow to its corresponding "function value" node (an object node).

Now invert the situation and consider an arbitrary multidigraph with $N = n + n(n+1)/2 = n(n+3)/2$ nodes with the property P, that $n$ of them (the object nodes) have $n+1$ out-arrows and another $n(n+1)/2$ of them (the argument nodes) have exactly 2 in-arrows and 1 out-arrow.

Question: Can - or rather: under which conditions can - be shown that a multidigraph with property P is bipartite, in the sense of:

  • the out-arrows of an object node go to an argument node and vice versa

  • the in-arrows of an object node come from an argument node and vice versa.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Your point is that you want to have unlabelled digraphs, right? So the object node x has two parallel arcs to the argument node (x,x)? I think you need to require n such parallel arcs with different targets, otherwise it seems to me that bipartness does not suffice to make the graph be a functional graph. (An example, forgetting about the functional values: consider n=3, and the disjoint union of a K_{2,4} and a digraph on three nodes, one of which has outdegree 4, the other 2 having each indegree 2) $\endgroup$
    – Martin Rubey
    Commented Jun 6, 2010 at 8:18

1 Answer 1

Reset to default
1
$\begingroup$

It's not true even for $n=1$. Consider the graph with two nodes, $a$ and $b$, with edges as follows:

  • $a\to a$
  • $a\to b$
  • $b\to b$

Thus, $a$ has exactly two out-arrows, $b$ has exactly two in-arrows and exactly one out-arrow. So it has property $P$ for $n=1$ but is not bipartite in th sense you wanted, since both $a$ and $b$ point at themselves.

(Note that the arrow $b\to b$ contributed both to the in-arrow sum and the out-arrow sum at $b$, which may not be how you wanted to consider things.)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .