3
$\begingroup$

When I asked this question before I got nary a nibble. That means either the question was too weird to resonate with anyone out there, or I did not make it clear that there was a question there that I did not know the answer to. This will attempt to clarify things, so if I get no nibble on this one, I will chalk it up to weirdness.

My current project led me to construct signed graphs as follows. The resulting graph $\Gamma$ will be a connected, signed, undirected graph with finitely many edges, with parallel edges allowed, and loops allowed, but it will shortly be obvious that loops can be ignored. The construction proceeds by ordering (enumerating) the edges as $e_1$, $e_2$, $\ldots$, $e_n$, and the edges are thought of as being added one by one, starting with the empty graph. It is convenient to let $\Gamma_i$ be the subgraph consisting of the edges $e_1$ through $e_i$ and let $\Gamma_0$ be the graph with no edges. The sign of edge $e_i$ will be positive if and only if its endpoints have valences (degrees) of like parity in $\Gamma_{i-1}$. It is clear that the signs depend on the ordering of the edges.

What is important in the construction is whether the result is balanced (every closed walk passes over an even number of negative edges).

Boundaries of polygons are easy to analyze, and the result depends only on the parity of the number of edges and is independent of the ordering. So far, experiment with pen and paper seems to hint that with every other graph, the outcome depends heavily on the edge ordering and that both balanced and unbalanced can occur. Some take a bit of experimenting to get a balanced outcome. Unbalanced outcomes are easy. Are there other graphs where the outcome is independent of the ordering of the edges?

Does anyone have any insight?

Improve this question
$\endgroup$
4
  • $\begingroup$ Try bipartite graphs. Gerhard "Insight Made Daily, Sometimes Fresh" Paseman, 2012.11.03 $\endgroup$
    – Gerhard Paseman
    Commented Nov 4, 2012 at 2:19
  • $\begingroup$ Gerhard: A square with a handle (square lollipop?) is bipartite and can be made either balanced or unbalanced depending on order. Start with two parallel edges on the square (both positive), add the handle (negative, but irrelevant) and then the other two parallel sides in any order. One will be positive and one negative making the square unbalanced. Making it balanced is easy. Start with the handle and keep going around the square without lifting your pencil. $\endgroup$
    – Matt Brin
    Commented Nov 4, 2012 at 3:16
  • $\begingroup$ Perhaps graphs with trivial automorphism group are harder to balance than those with an involution in their automorphism group. Gerhard "Then Again Maybe They're Easier" Paseman, 2012.11.03 $\endgroup$
    – Gerhard Paseman
    Commented Nov 4, 2012 at 3:27
  • $\begingroup$ So far every graph I tried that has a circle as a proper subgraph could be made both balanced and unbalanced. Some are hard. I think I just balanced the Petersen graph, but I need to go over it again. It is hard to appreciate how much the order affects things until you have tried a few. Wheels seem to be tricky to balance. The wheel with three spokes can be made all positive. The wheel with four spokes can be made all positive on the outside and all negative on the spokes. I forget how six went. I am too tired to try five. $\endgroup$
    – Matt Brin
    Commented Nov 4, 2012 at 4:14

3 Answers 3

Reset to default
1
$\begingroup$

Biparticity and automorphisms are not likely to be relevant, in my opinion.

Improve this answer
$\endgroup$
1
$\begingroup$

How about a $k$-bond---a pair of vertices with $k$ multiple edges. All of the edges will come out positive, so the order won't matter. Note that this is dual to the boundary of a polygon (a cycle).

Improve this answer
$\endgroup$
0
$\begingroup$

The only connected graphs whose balance is independent of the edge ordering are trees and polygons.

Obviously trees have this property.

A connected graph which is neither a tree nor a polygon contains a cycle $C$ with a handle $e$. Let $e'$ be an edge of the cycle adjacent to $e$. Consider edge orderings in which $e$ and $e'$ are the final two edges. The sign of $e'$, and thus the sign of the cycle $C$, depends on which of $e,e'$ is added first.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think you have proven that a graph that is not a tree and not a polygon can be made unbalanced. But I don't see that you have proven that the entire graph can be made balanced, only a particular subgraph. It is often quite hard to find an ordering that will balance a particular graph. So far, I have always succeeded (other than polygons with an odd number of sides), but the number of graphs I have tried is less than a dozen. The hardest so far was the Petersen graph and I am not so sure I didn't make a mistake. $\endgroup$
    – Matt Brin
    Commented Nov 4, 2012 at 13:35
  • $\begingroup$ Yes, you are right; sorry for not reading properly. It is a very nice question. I wonder if connected graphs that can be balanced admit a balancing sequence that starts with a spanning tree; do you have a feeling on that? $\endgroup$
    – Brendan McKay
    Commented Nov 5, 2012 at 11:04
  • $\begingroup$ Brendan: Not sure how to interpret the comment's question. Any interpretation I give it (spanning tree comes with signs assigned, e.g., all +) ends up sounding very overdetermined. Each new edge has only one choice to make the result balanced, and it had better agree with the degree criteria. How do you see the spanning tree starting out? $\endgroup$
    – Matt Brin
    Commented Nov 5, 2012 at 12:27

You must log in to answer this question.

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