Group Connectivity of Graphs and Signed Graphs

  • [2017-06-07]

    Speaker:Rong Luo, Department of Mathematics West Virginia University Morgantown

    Time: 2017-06-07 10:00-11:00

    Place:Room 1518,School of Mathematical Sciences 


    Detail: The concept of group connectivity was introduced by Jaeger, Linial, Payan, and Tarsi (Journal Combinatorial Theory, Ser. B, 1992) as a generalization of nowhere-zero group flows. Let A be an Abelian group. An A-connected graphs are contractible configurations of A-flow and play an important role in the study of group flows because of the fact: if H is A-connected, then any supergraph G of H (i.e. G contains H as a subgraph) admits a nowhere-zero A-flow if and only if G/H does. It is known that an A-connected graph cannot be very sparse. How dense could an A-connected graph be? This motivates us to study the extremal problem: find the maximum integer k, denoted ex(n, A), such that every graph with at most k edges is not A-connected. We determine the exact values for all finite cyclic groups. As a corollary, we present a characterization of all Zk-connected graphic sequences. As noted by Jaeger, Linial, Payan, and Tarsi, there are Z5-connected graph that are not Z6-connected. We also prove that every Z3-connected graph contains two edge-disjoint spanning trees, which implies that every Z3-connected graph is also A-connected for any Abelian group A with order at least 4. In the second part of the talk, I will introduce the concept of group connectivity of signed graphs and present some basic properties of group connectivities of signed graphs.



    Organizer: School of Mathematical Sciences


This article came from News Center of USTC.