0
$\begingroup$

Consider directed graphs where all nodes have 2 inputs and 2 outputs. If we design a box with N inputs and N outputs, what is the smallest number of nodes it must contain to satisfy “pair symmetry” (i.e., each input is paired with some output, but relabeling the N pairs does not change the graph). Please specify the corresponding minimal graph solutions for N=3 and N=4.

Here are two graph examples to help show what I'm looking for: alt text

Improve this question
$\endgroup$
4
  • $\begingroup$ I will be honest, I do not understand your question. In particular, the meaning of "box", "input", "output", and "pair" are not clear. Perhaps you should explain your examples in more detail. $\endgroup$
    – fkenter
    Apr 12, 2013 at 9:45
  • $\begingroup$ Each node has two lines with arrows indicating inward flow and two lines with arrows indicating outward flow; these are the two inputs and two outputs (this should be natural to people familiar with directed graphs). To draw this fast, I didn't show arrows on some lines, but please consider all lines to have a flow arrow. Both of my examples have 3 inputs and 3 outputs which are unconnected which can be itemized in pairs by writing in1, out1, in2, out2, in3, out3. Box is more like "black box" where this whole construction is like a node with many inputs and outputs. $\endgroup$
    – bobuhito
    Apr 12, 2013 at 23:14
  • $\begingroup$ As far as I undestand, the question may be formulated as follows. We have a digraph where each vertex has both in- and out-degrees equal to 2. $n$ independent vertices are marked (there are in/outputs of the black box), and for every permutation of the marked vertices there exists an automorphism of the graph inducing exactly this permutation. Is this what you meant? $\endgroup$
    – Ilya Bogdanov
    Apr 13, 2013 at 9:52
  • $\begingroup$ Yes, but marking 2*n independent vertices is probably required (as in the left example above) since I really wanted to mark the lines from the vertices. There are really n labels for permutation because of my pairing. The automorphism then needs to induce the same pairs. If you're curious, this is a practical application for building a network with many inter-communicating IOs from small primitive routers. $\endgroup$
    – bobuhito
    Apr 13, 2013 at 12:59

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.