Eulerian Subgraphs and S-connectivity of Graphs

•A new relation between Eulerian subgraphs and flow of graphs is obtained.•Settle a conjecture of Lai et al.(2011) for all but finite many Abelian groups.•The proof combines graph theory techniques and advanced tools from group theory.•Develop several tools for studying graph structures and graph fl...

Full description

Saved in:
Bibliographic Details
Published in:Applied mathematics and computation 2020-10, Vol.382, p.125323, Article 125323
Main Authors: Han, Miaomiao, Miao, Zhengke
Format: Article
Language:English
Subjects:
Collapsible graphs
Connectivity
Eulerian graphs
Nowhere-zero flow
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•A new relation between Eulerian subgraphs and flow of graphs is obtained.•Settle a conjecture of Lai et al.(2011) for all but finite many Abelian groups.•The proof combines graph theory techniques and advanced tools from group theory.•Develop several tools for studying graph structures and graph flows with certain group values. Collapsible graphs are introduced by Caltin to study Eulerian subgraphs, and S-group-connectivity is introduced by Jaeger et al. to study flows of graphs. Lai established a connection of those graph classes by showing that collapsible graphs have S-connectivity for group S of order 4. In a survey paper in 2011, Lai et al. conjectured that this property holds for all finite Abelian groups of size at least 4. We prove this conjecture for all groups of even order |S| ≥ 4 and of large odd order |S| ≥ 53.
ISSN:0096-3003
1873-5649
DOI:10.1016/j.amc.2020.125323