Site

Balanced And Unbalanced Girths Special Subclasses

One may consider two types of parity for each closed-walk. This leads into four different types of closed-walk:

  • Type 00: that is a closed-walk of even length with an even number of negative edges.

  • Type 01: that is a closed-walk of odd length with an even number of negative edges.

  • Type 10: that is a closed-walk of even length with an odd number of negative edges.

  • Type 11: that is a closed-walk of odd length with an odd number of negative edges.

The logic of the index: following the order of adjectives in terms balanced/unbalanced even/odd cycle, the first term of the type determines balance of the closed-walk while the second determines its parity. The association of 0 to balance and even or 1 to unbalanced and odd is so that the rule of binary sum (i+i',j+j') works for determining the type of a closed-walk obtained from merging two closed-walks both starting at a same vertex.

  • Definition of girth of type ij (i,j ∈ {0,1}): that is the length of a shortest closed-walk of type ij and is denoted by gij(G, 𝛴 ). When there is no closed-walk of type ij, we define
    gij(G, 𝛴 )= ∞.

  • Observations
    • g00(G, 𝛴 )=0 when G has no edge and g00(G, 𝛴 )=2 otherwise.
    • if G is connected and two of the three values of g01(G, 𝛴 ), g10(G, 𝛴 ), g11(G, 𝛴 ) are finite, then so is the third one, but there is no function to bound the value of the third based on the values of the first two.
  • Special subclasses
    • g01(G, 𝛴 )=g11(G, 𝛴 )= ∞
      As there are no unbalanced-cycles, we may resign to have all edges of positive signs. Thus this case is the most natural consideration of graphs as a subclass of signed graphs.

      This class of signed graphs will be denoted by G10, meaning of the three types 01, 10, 11 only cycles of type 10 may exist.

    • g01(G, 𝛴 )=g10(G, 𝛴 )= ∞
      In this case a cycle is odd if and only if it is unbalanced. Thus the signature is equivalent to all edges being negative. In this case while purely homomorphism and coloring functions behave the same as graphs, when correlation with minor is considered, much stronger results are expected.

      This class of signed graphs will be denoted by G11, meaning of the three types 01, 10, 11 only cycles of type 11 may exist.

    • g10(G, 𝛴 )=g11(G, 𝛴 )= ∞
      In this case the underlying graph has no odd-cycle, thus it is bipartite. As any signature on a bipartite graph satisfies this condition, we have the set of all signed bipartite graphs. Restriction on this subclass of signed graph still captures coloring and homomorphisms of graphs.

      This class of signed graphs will be denoted by G01, meaning of the three types 01, 10, 11 only cycles of type 01 may exist.