Bertrand Guenin

By a cycle in a graph we mean a subset of the edges with the property that every vertex of the subgraph induced by these edges has even degree. We write

c y c l e (G)

$cycle(G)$ for the set of all cycles of

G

$G$ and write

c u t (G)

$cut(G)$ for the set of all cuts (also viewed as sets of edges) of

G .

$G.$ We can view

c y c l e (G)

$cycle(G)$ and

c u t (G)

$cut(G)$ as orthogonal binary vector spaces. Consider a graph

G

$G$ with a two vertex cutset. If

G^{'}

$G'$ is obtained from

G

$G$ by flipping the subgraph on one side of the

2

$2$ -separation as indicated in the following figure then

G^{'}

$G'$ is a 2-flip of

G .

$G.$ We call a 1-flip the identification of two vertices in distinct components or splitting two blocks into different components. Two graphs are equivalent if they are related by a sequence of

1

$1$ -flips and

2

$2$ -flips.

Theorem 1

If $cycle(G)=cycle(G’)$ or equivalently $cut(G)=cut(G’)$ then $G$ and $G'$ are equivalent. In particular, if $G$ or $G'$ is $3$ -connected then $G=G’.$

Generalizing the problem.

A signed-graph is a pair

(G, Σ)

$(G,\Sigma)$ where

G

$G$ is a graph and

Σ \subseteq E G .

$\Sigma\subseteq EG.$ A cycle

C

$C$ is even (resp. odd) if

| C \cap Σ |

$|C\cap\Sigma|$ is even (resp. odd). We write

e c y c l e (G, Σ)

$ecycle(G,\Sigma)$ for the set of all even cycles of

(G, Σ) .

$(G,\Sigma).$ A graft is a pair

(G, T)

$(G,T)$ where

G

$G$ is a graph and

T \subseteq V G

$T\subseteq VG$ where

| T |

$|T|$ is even. If there exists a component of

G

$G$ with an odd number of vertices in

T

$T$ then every cut of

(G, T)

$(G,T)$ is defined to be even. Otherwise, a cut

δ (U)

$\delta(U)$ is even (resp. odd) if

| T \cap U |

$|T\cap U|$ is even (resp. odd). We write

e c u t (G, T)

$ecut(G,T)$ for the set of all even cuts of

(G, T) .

$(G,T).$

We are interested in generalizing Theorem 1 to signed-graphs and grafts. More precisely, we are interested in the following two problems,

Given a pair of signed-graphs $(G_1,\Sigma_1)$ , $(G_2,\Sigma_2)$ for which $ecycle(G_1,\Sigma_1)$ $=$ $ecycle(G_2,\Sigma_2)$ , what is the relationship between $(G_1,\Sigma_1)$ and $(G_2,\Sigma_2)$ ?
Given a pair of grafts $(G_1,T_1)$ , $(G_2,T_2)$ for which $ecut(G_1,T_1)$ $=$ $ecut(G_2,T_2)$ , what is the relationship between $(G_1,T_1)$ and $(G_2,T_2)$ ?

Observe that

e c y c l e (G_{i}, Σ_{i})

$ecycle(G_i,\Sigma_i)$

=

$=$

c y c l e (G_{i})

$cycle(G_i)$ when

Σ_{i} = \emptyset .

$\Sigma_i=\emptyset.$ Hence, Problem 1 generalizes the problem of characterizing when two graphs have the same cycles. Similarly,

e c u t (G_{i}, T_{i})

$ecut(G_i,T_i)$

=

$=$

c u t (G_{i})

$cut(G_i)$ when

T_{i} = \emptyset .

$T_i=\emptyset.$ Hence, Problem 2 generalizes the problem of characterizing when two graphs have the same cuts.

Suppose

G_{1}

$G_1$ and

G_{2}

$G_2$ are equivalent. Then

e c y c l e (G_{1}, Σ_{1})

$ecycle(G_1,\Sigma_1)$

=

$=$

c y c l e (G_{2}, Σ_{2})

$cycle(G_2,\Sigma_2)$ exactly when

Σ_{1}

$\Sigma_1$ and

Σ_{2}

$\Sigma_2$ are related by resigning, and

e c u t (G_{1}, T_{1})

$ecut(G_1,T_1)$

=

$=$

e c u t (G_{2}, T_{2})

$ecut(G_2,T_2)$ exactly when a

T_{1}

$T_1$ -join of

G_{1}

$G_1$ is a

T_{2}

$T_2$ -join of

G_{2}

$G_2$ . Hence, for equivalent graphs

G_{1}

$G_1$ and

G_{2}

$G_2$ problems 1 and 2 are solved and it suffices to restrict our attention to the case where

G_{1}, G_{2}

$G_1,G_2$ are not equivalent.

Denote by

G_{1}

$G_1$ the (edge labeled) graph on the left and by

G_{2}

$G_2$ the (edge labeled graph) on the right. Note that

G_{1}

$G_1$ and

G_{2}

$G_2$ are not equivalent. Define,

Then observe that

(G_{1}, Σ_{1})

$(G_1,\Sigma_1)$ and

(G_{2}, Σ_{2})

$(G_2,\Sigma_2)$ have the same set of even cycles. Hence, an answer to Problem 1, will involve the aforementioned construction. Suppose we now define

T_{1}

$T_1$ and

T_{2}

$T_2$ to denote the set of all vertices in

G_{1}

$G_1$ and

G_{2}

$G_2$ respectively. Then observe that

(G_{1}, T_{1})

$(G_1,T_1)$ and

(G_{2}, T_{2})

$(G_2,T_2)$ have the same even-cuts. Hence, an answer to Problem 2, will involve the aforementioned construction as well. The previous examples show in particular that even assuming high connectivity for

G_{1}

$G_1$ and

G_{2}

$G_2$ the answer to problems 1 and 2 is non-trivial.

Problem 1 and Problem 2 are equivalent.

We have now seen a pair of inequivalent graphs for which we were able to construct both a pair of signed-graphs with same even-cycles and a pair of grafts with the same even cuts. This is part of a general phenomena,

Theorem 2

Let $G_1, G_2$ be inequivalent graphs (with the same edge label). Then the following are equivalent,

(a) There exists $\Sigma_1,\Sigma_2$ such that $ecycle(G_1,\Sigma_1)=ecycle(G_2,\Sigma_2)$ ,
(b) There exists $T_1,T_2$ such that $ecut(G_1,T_1)=ecut(G_2,T_2).$

In addition if (a) respectively (b) hold then

Σ_{1}, Σ_{2}

$\Sigma_1,\Sigma_2$ are unique (up to resigning) and

T_{1}, T_{2}

$T_1,T_2$ are unique. We say that a pair of inequivalent graphs for which (a), (b) hold in the previous Theorem, are siblings. Thus Problem 1 and Problem 2 are equivalent to the problem of characterizing siblings. Theorem 2 can be found in the following paper,

Shih's theorem.

Given a pair of graphs $G_1,G_2$ where

$(\star)\quad\quad cycle(G_1)\subseteq cycle(G_2)\quad\&\quad\dim(cycle(G_1))=\dim(cycle(G_2))-1,$

what is the relationship between $G_1$ and $G_2$ ?

Condition (

⋆

$\star$ ) holds, if and only if for some

Σ_{2}

$\Sigma_2$ we have

c y c l e (G_{1}) = e c y c l e (G_{2}, Σ_{2})

$cycle(G_1)=ecycle(G_2,\Sigma_2)$ where

(G_{2}, Σ_{2})

$(G_2,\Sigma_2)$ has a least one odd cycle. Hence, the problem that Shih investigated is a special case of Problem 1.

So what are pairs of graphs that satisfy (

⋆

$\star$ )? As an example consider a connected graph

G_{1}

$G_1$ with distinct vertices

a

$a$ and

b

$b$ and let

G_{2}

$G_2$ be obtained from

G_{1}

$G_1$ by identifying vertices

a

$a$ and

b

$b$ . Then clearly, every cycle of

G_{1}

$G_1$ is a cycle of

G_{2}

$G_2$ . Moreover, as

\dim (c y c l e (G_{1}))

$\dim(cycle(G_1))$

=

$=$

| E G_{1} | - | V G_{1} | + 1

$|EG_1|-|VG_1|+1$ and

\dim (c y c l e (G_{2}))

$\dim(cycle(G_2))$

=

$=$

| E G_{2} | - | V G_{2} | + 1

$|EG_2|-|VG_2|+1$ , we have

\dim [c y c l e (G_{1})] = \dim [c y c l e (G_{2})] - 1

$\dim[cycle(G_1)]=\dim[cycle(G_2)]-1$ .

This is not the only construction. Consider the following pair of graphs where

G_{1}

$G_1$ is the graph on the left and

G_{2}

$G_2$ the graph on the right. Then the pair

G_{1}, G_{2}

$G_1, G_2$ also satisfies (

⋆

$\star$ ).

In his PhD thesis (Ohio State Univ. 1982), Shih characterizes the exact relation between pairs of graphs satisfying (

⋆

$\star$ ). Unfortunately, this result was never published and has been largely forgotten. It is important, however, and has found applications in the theory of graphic frame matroids for instance. We give a more accessible proof of his result in the following paper,

The general problem.

Consider the general problem again, namely what is the relationship between a pair of siblings

G_{1}

$G_1$ and

G_{2}

$G_2$ ? Recall that

G_{1}, G_{2}

$G_1,G_2$ are siblings if they are not equivalent and for some

Σ_{1}, Σ_{2}

$\Sigma_1,\Sigma_2$ ,

e c y c l e (G_{1}, Σ_{1})

$ecycle(G_1,\Sigma_1)$

=

$=$

e c y c l e (G_{2}, Σ_{2})

$ecycle(G_2,\Sigma_2)$ or equivalently for some

T_{1}, T_{2}

$T_1,T_2$ ,

e c u t (G_{1}, T_{1})

$ecut(G_1,T_1)$

=

$=$

e c u t (G_{2}, T_{2})

$ecut(G_2,T_2)$ for some

T_{1}, T_{2}

$T_1,T_2$ .

We give a complete answer for the case where both

G_{1}

$G_1$ and

G_{2}

$G_2$ are

4

$4$ -connected. Informally speaking the result says that either we can explain the relationship between

G_{1}

$G_1$ and

G_{2}

$G_2$ using Shih's theorem, or

G_{1}

$G_1$ and

G_{2}

$G_2$ are as in the previous example where

G_{1}

$G_1$ and

G_{2}

$G_2$ are both isomorphic to

K_{6}

$K_6$ .

2. Bridges in signed graphs

A path with at least one edge with ends having degree at least

3

$3$ and internal vertices having degree

2

$2$ is a segment. A graph

S

$S$ is a $G$ -subdivision where

G

$G$ is a graph, if

S

$S$ is obtained by replacing each edge be a non-empty set of series edges. If

S

$S$ is a subgraph of

H

$H$ and

S

$S$ is a

G

$G$ -subdivision, then

S

$S$ is a $G$ -subdivision in $H$ . Consider a subgraph

S

$S$ of a graph

H

$H$ . An $S$ -bridge in $H$ is a subgraph

B

$B$ of

H

$H$ such that

E B \cap E S = \emptyset

$EB\cap ES=\emptyset$ and either

E B

$EB$ consists of a single edge with both ends in

V S

$VS$ , or for some component

C

$C$ of

H ∖ V S

$H\setminus VS$ ,

B

$B$ is induced by the edges of

H

$H$ with at least one end in

V C

$VC$ . We say that

V B \cap V S

$VB\cap VS$ are the attachments of

B

$B$ . An

S

$S$ -bridge

B

$B$ in

H

$H$ is stable if no segment of

S

$S$ includes all the attachments of

B

$B$ .

Theorem 3

Let $G,H$ be graphs where $G$ has minimum degree $3$ and where $H$ is $3$ -connected and simple. If there exists a $G$ -subdivision in $H$ then there exists a $G$ -subdivision $S$ in $H$ where all $S$ -bridges are stable.

Bridges have been studied extensively and play an important role in structural graph theory. The theory of bridges has been used to prove such well-known results as Kuratowski's Theorem and Tutte's famous result that every 4-connected graph with at least 4 vertices has a Hamiltonian cycle.

Preserving parity of cycles

Let

G

$G$ be a graph with minimum degree three and let

S

$S$ be a

G

$G$ -subdivision. For each

e \in E G

$e\in EG$ denote by

Z_{e}

$Z_e$ the corresponding set of series edges in

S

$S$ . Define

Φ : 2^{E G} \to 2^{E S}

$\Phi: 2^{EG}\rightarrow 2^{ES}$ where

Φ (L) := \cup_{e \in L} E Z_{e}

$\Phi(L):=\cup_{e\in L}EZ_e$ . Observe that edges

L \subseteq E G

$L\subseteq EG$ form a cycle of

G

$G$ if and only if edges

Φ (L) \subseteq E S

$\Phi(L)\subseteq ES$ form a cycle of

S

$S$ . However,

| L |

$|L|$ and

| Φ (L) |

$|\Phi(L)|$ may have different parities. We want to extend the theory of bridges to a framework where

Φ

$\Phi$ preserves parity of cycles.

A signed graph is a pair

(G, Σ)

$(G, \Sigma)$ where

G

$G$ is a graph and

Σ \subseteq E G

$\Sigma\subseteq EG$ . The edges of

G

$G$ in

Σ

$\Sigma$ are odd and the other edges are even. The parity of a subgraph

F

$F$ of

G

$G$ is defined as the parity of

| E F \cap Σ |

$|EF\cap \Sigma|$ . A signed graph

(S, Λ)

$(S,\Lambda)$ is a $(G,\Sigma)$ -subdivision if

S

$S$ is a

G

$G$ -subdivision and for every

e \in E G

$e\in EG$ we have

e \in Σ

$e\in\Sigma$ if and only if the corresponding segment

Z_{e}

$Z_e$ of

S

$S$ satisfies

| E Z_{e} \cap Λ |

$|EZ_e\cap\Lambda|$ odd. Then edges

L \subseteq E G

$L\subseteq EG$ form a cycle of

G

$G$ if and only if

Φ (L)

$\Phi(L)$ form the edges of a cycle of

S

$S$ , moreover

L

$L$ is odd in

(G, Σ)

$(G,\Sigma)$ if and only if

Φ (L)

$\Phi(L)$ is odd in

(S, Λ)

$(S,\Lambda)$ . Hence, our definition of subdivision for signed graphs preserve parity of cycles. If

(S, Λ)

$(S,\Lambda)$ is a subgraph of

(H, Γ)

$(H,\Gamma)$ and

(S, Λ)

$(S,\Lambda)$ is a

(G, Σ)

$(G,\Sigma)$ -subdivision, then

(S, Λ)

$(S,\Lambda)$ is a $(G,\Sigma)$ -subdivision in $(H,\Gamma)$ .

A natural question is whether Theorem 3 extends to the context of signed graphs. Namely,

Question:

Consider signed graphs $(G,\Sigma)$ and $(H,\Gamma)$ where $G$ has minimum degree $3$ and $H$ is $3$ -connected and simple. Assuming that there exists a $(G,\Sigma)$ -subdivision in $(H,\Gamma)$ , does there exists an $(G,\Sigma)$ -subdivision $(S,\Lambda)$ in $(H,\Gamma)$ where all $S$ -bridges are stable?

Alas this is not the case. The next figure shows a configuration of unstable bridges with all attachments in segment

Z

$Z$ that cannot be eliminated by choosing a different subdivision. Dashed lines correspond to odd edges and solid lines correspond to even edges (in particular, all edges of

Z

$Z$ are even). The shaded vertex

x

$x$ is the only attachments of a stable bridges on

Z

$Z$ .

Assuming

3

$3$ -connectivity we show we can find a

(G, Σ)

$(G,\Sigma)$ -subdivision

(S, Λ)

$(S,\Lambda)$ in

(H, Γ)

$(H,\Gamma)$ where all unstable

S

$S$ -bridges fall into one of three classes, illustrated by

B_{1}, B_{2}, B_{3}

$B_1,B_2,B_3$ in the previous figure. If we assume

4

$4$ -connectivity then, we can find a subdivision where all unstable bridges are of the same type.

Theorem 4

Consider signed graphs $(H,\Gamma)$ and $(G,\Sigma)$ where $G$ has minimum degree $3$ and where $H$ is $4$ -connected and simple. Suppose that there exists a $(G,\Sigma)$ -subdivision in $(H,\Gamma)$ . Then there exists a $(G,\Sigma)$ -subdivision $(S,\Lambda)$ in $(H,\Gamma)$ such that for every bridge $B$ that has all attachments in a segment $Z$ , $B$ has distinct attachments $s_1,\ldots,s_p, t_1,\ldots,t_q$ where $p,q\geq 1$ , and the vertices $s_1,\ldots,s_p,t_1,\ldots,t_q$ appear on $Z$ in the order stated. If $w\in V(s_1Zt_q)\setminus\{s_1,t_q\}$ is an attachment of a stable $S$ -bridge, then $w\in V(s_pZt_1)$ . Moreover, $\cup_{i=1}^p \delta_B(s_i)$ is a signature of $(H,\Gamma)| EB\cup EZ$ .

Here given a path

Z

$Z$ and vertices

x, y

$x,y$ of

Z

$Z$ ,

x Z y

$xZy$ denotes the subpath of

Z

$Z$ with ends

x, y

$x,y$ .

Bertrand Guenin - graphs

1. Generalization of Whitney's theorem.

Generalizing the problem.

Problem 1 and Problem 2 are equivalent.

Shih's theorem.

The general problem.

2. Bridges in signed graphs

Preserving parity of cycles