On restricted edge-connectivity of vertex-transitive multigraphs

DOI10.1080/00207160.2013.856419zbMATH Open1305.05115arXiv1401.3187OpenAlexW2081716679MaRDI QIDQ2935384FDOQ2935384

Authors: Yingzhi Tian, Jixiang Meng 

Publication date: 29 December 2014

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Abstract: Let $G=(V,E)$ be a multigraph (it has multiple edges, but no loops). The edge connectivity, denoted by $lambda(G)$, is the cardinality of a minimum edge-cut of $G$. We call $G$ maximally edge-connected if $lambda(G)=delta(G)$, and $G$ super edge-connected if every minimum edge-cut is a set of edges incident with some vertex. The restricted edge-connectivity $lambd{a}^{\prime }(G)$ of $G$ is the minimum number of edges whose removal disconnects $G$ into non-trivial components. If $lambd{a}^{\prime }(G)$ achieves the upper bound of restricted edge-connectivity, then $G$ is said to be $lambd{a}^{\prime }$-optimal. A bipartite multigraph is said to be half-transitive if its automorphism group is transitive on the sets of its bipartition. In this paper, we will characterize maximally edge-connected half-transitive multigraphs, super edge-connected half-transitive multigraphs, and $lambd{a}^{\prime }$-optimal half-transitive multigraphs.

Full work available at URL: https://arxiv.org/abs/1401.3187

Recommendations

• On restricted edge-connectivity of half-transitive multigraphs
• scientific article; zbMATH DE number 1545446
• On super restricted edge-connectivity of vertex-transitive graphs
• On super 2-restricted and 3-restricted edge-connected vertex transitive graphs
• scientific article; zbMATH DE number 5052357

zbMATH Keywords

multigraphsvertex-transitiverestricted edge-connectivitysuper edge-connectedmaximally edge-connected

Mathematics Subject Classification ID

Connectivity (05C40)

Cites Work

• Circulants and their connectivities
• Conditional connectivity
• On computing a conditional edge-connectivity of a graph
• Super restricted edge-connectivity of vertex-transitive graphs
• Optimally super-edge-connected transitive graphs
• Minimale \(n\)-fach kantenzusammenhängende Graphen
• On a kind of restricted edge connectivity of graphs
• Conditional edge connectivity properties, reliability comparisons and transitivity of graphs
• Sufficient conditions for restricted-edge-connectivity to be optimal
• On super 2-restricted and 3-restricted edge-connected vertex transitive graphs
• On super restricted edge-connectivity of vertex-transitive graphs
• Combinatorial optimization problems in the analysis and design of probabilistic networks

Cited In (6)

• Title not available (Why is that?)
• Title not available (Why is that?)
• The edge‐connectivity of vertex‐transitive hypergraphs
• On restricted edge-connectivity of half-transitive multigraphs
• Degree sequences of optimally edge-connected multigraphs.
• Title not available (Why is that?)

This page was built for publication: On restricted edge-connectivity of vertex-transitive multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2935384)