Group connectivity under 3‐edge‐connectivity

Miaomiao Han, Jiaao Li, Xueliang Li, Meiling WangJournal of Graph Theory 2020 · DOI

TL;DR

This paper investigates the relationship between different types of "group connectivity" in graphs, specifically when graphs are 3-edge-connected. They prove that for most pairs of Abelian groups with the same size, if a graph is connected in one group's sense, it's also connected in the other's. This resolves a long-standing question in graph theory.

What Problem Does This Paper Address?

The paper delves into the concept of "group connectivity," an extension of the well-known "nowhere-zero flow" problem in graph theory. Tutte's theorem established that for nowhere-zero flows, the specific choice of an Abelian group of a certain size doesn't matter – if a graph admits a flow for one group, it does for any other group of the same size.

However, when extending this idea to "group connectivity," this equivalence breaks down. Previous work showed that for graphs with only 2-edge-connectivity, there exist pairs of groups (like $\mathbb{Z}_4$ and $\mathbb{Z}_2$) where a graph can be connected in the sense of one group but not the other. The authors of this paper aim to answer whether this disconnect persists for graphs with higher edge-connectivity, specifically 3-edge-connectivity. They tackle the question: for 3-edge-connected graphs, when is $S$-connectivity equivalent to $T$-connectivity for Abelian groups $S$ and $T$ of the same order?

Methods

The core of the paper's methodology involves constructing specific graphs to demonstrate or disprove certain connectivity properties. A key tool is the "2-sum operation," a way to combine two graphs by identifying pairs of vertices. This operation is used to build larger, more complex graphs from simpler ones, allowing the researchers to systematically test group connectivity.

They also leverage existing theorems, such as Jaeger et al.'s results on group connectivity for 4-edge-connected graphs and graphs with large group orders. The proofs often rely on demonstrating contradictions: assuming a graph is $S$-connected for a particular group and then showing this leads to an impossibility when considering a specific "failed" boundary function.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions of graphs rather than empirical evaluation on datasets.

Key Insights and Ideas

  • The Equivalence Holds (Mostly): The most significant finding is that for 3-edge-connected graphs, $S$-connectivity and $T$-connectivity are equivalent for groups $S$ and $T$ of the same order, unless the pair of groups is $\{\mathbb{Z}_4, \mathbb{Z}_2\}$. This is a strong generalization of previous results.
  • Construction is Key: The paper demonstrates its main results through explicit graph constructions. These constructions are crucial for showing that certain pairs of groups do exhibit different connectivity behaviors even for 3-edge-connected graphs.
  • The Role of $\mathbb{Z}_4$ and $\mathbb{Z}_2$: The pair $\{\mathbb{Z}_4, \mathbb{Z}_2\}$ emerges as a special case where the equivalence fails, even at 3-edge-connectivity. This highlights the unique properties of these specific groups in the context of graph connectivity.
  • Extending Previous Work: The paper successfully extends results from 2-edge-connected graphs to the more constrained setting of 3-edge-connected graphs, answering open problems in the field.

Key Results

The paper's main result is summarized in Corollary 1.6: For any two distinct Abelian groups $S$ and $T$ with $|S| = |T|$, every 3-edge-connected $S$-connected graph is $T$-connected if and only if $\{S, T\} \neq \{\mathbb{Z}_4, \mathbb{Z}_2\}$.

The paper also provides explicit constructions for:

  • A 3-edge-connected graph that is $\mathbb{Z}_4$-connected but not $\mathbb{Z}_2$-connected (Theorem 1.4(1)).
  • A 3-edge-connected graph that is $\mathbb{Z}_2$-connected but not $\mathbb{Z}_4$-connected (Theorem 1.4(2)).
  • Similar constructions for cubic graphs (Theorem 1.7).

Limitations and Future Work

  • Computer-Aided Proofs: While the paper presents theoretical constructions, it acknowledges that some foundational results (like Theorem 1.3) rely on computer-aided proofs.
  • 3-Edge-Cuts: The paper raises the question of whether a lower number of 3-edge-cuts in a graph could guarantee the equivalence of group connectivity. They establish bounds for this ($9 \le k \le 47$) but leave the exact value open.
  • Smallest Counterexamples: Finding the smallest 3-edge-connected graphs that are $\mathbb{Z}_4$-connected but not $\mathbb{Z}_2$-connected (and vice-versa) is suggested as future work, which could help resolve the edge-cut problem.
  • Graph Coloring Analogy: The paper notes that the dual problem for graph coloring (S-group-colorability) remains open and asks if $S$-group-colorability and $T$-group-colorability are equivalent for distinct groups $S$ and $T$ of the same order.

Summary updated

Abstract

Abstract Let be two distinct finite Abelian groups with . A fundamental theorem of Tutte shows that a graph admits a nowhere‐zero ‐flow if and only if it admits a nowhere‐zero ‐flow. Jaeger et al in 1992 introduced group connectivity as an extension of flow theory, and they asked whether such a relation holds for group connectivity analogy. It was negatively answered by Hušek et al in 2017 for graphs with edge‐connectivity 2 for the groups and . In this paper, we extend their results to 3‐edge‐connected graphs (including both cubic and general graphs), which answers open problems proposed by Hušek et al and Lai et al. Combining some previous results, this characterizes all the equivalence of group connectivity under 3‐edge‐connectivity, showing that every 3‐edge‐connected ‐connected graph is ‐connected if and only if .
BibTeX
@article{han2020group,
  author = {Miaomiao Han and Jiaao Li and Xueliang Li and Meiling Wang},
  title = {{Group connectivity under 3‐edge‐connectivity}},
  journal = {Journal of Graph Theory},
  year = {2020},
  doi = {10.1002/jgt.22623},
}

Loading related content...

Figure