On restricted edge-connectivity of vertex-transitive multigraphs

DOI10.1080/00207160.2013.856419MaRDI QIDQ2935384zbMATH OpenOpenAlexFDO

Authors Yingzhi Tian, Jixiang Meng

Publication date 29 December 2014

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Connectivity (05C40)

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.

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

Cites work

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

Cited in

(6)

• scientific article; zbMATH DE number 5052357 (Why is no real title available?)
• scientific article; zbMATH DE number 5064073 (Why is no real title available?)
• The edge‐connectivity of vertex‐transitive hypergraphs
• On restricted edge-connectivity of half-transitive multigraphs
• Degree sequences of optimally edge-connected multigraphs.
• scientific article; zbMATH DE number 2151843 (Why is no real title available?)

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)