Local-edge-connectivity in digraphs and oriented graphs

DOI10.1016/J.DISC.2007.03.051MaRDI QIDQ2463907zbMATH OpenOpenAlexFDO

Authors Lutz Volkmann

Publication date 6 December 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2007.03.051

zbMATH Keywords

DigraphEdge-connectivityLocal-edge-connectivityMinimum degreeOriented graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Review text

The local-edge-connectivity \(\lambda(u,v)\) of two vertices \(u\) and \(v\) in a digraph \(D\) is the maximum number of edge-disjoint \(u\)-\(v\) paths in \(D\). A digraph \(D\) is said to be maximally local-edge-connected when for all pairs \(u\) and \(v\) of vertices \(\lambda(u,v)\) equals the minimum of out-degree of \(u\) and in-degree of \(v\). Some known sufficient conditions guaranteeing equality of edge-connectivity and minimum degree of an oriented graph (i.e. a digraph without 2-cycles) are shown to guarantee the maximal local-edge-connectivity too. Moreover, the validity of a result for digraphs of diameter at most three [\textit{J. Fabrega} and \textit{M. A. Fiol}, Discrete Appl. Math. 69, 271--279 (1996; Zbl 0857.05063)] is discussed for the local property.

Recommendations

• scientific article; zbMATH DE number 2192129
• Degree sequence conditions for maximally edge-connected oriented graphs
• Lower bounds of \(|X|\) and \(|Y|\) of edge-cut \( (X,Y)\) and maximality and superiority of a digraph
• Sufficient conditions for maximally edge-connected and super-edge-connected digraphs depending on the size
• Connectivity in graphs and digraphs. Maximizing vertex-, edge- and arc-connectivity with an emphasis on local connectivity properties

Cites work

• A Generalization of Line Connectivity and Optimally Invulnerable Graphs
• A Graph-Theoretic Approach to a Communications Problem
• A sufficient condition for equality of arc-connectivity and minimum degree of a digraph
• A sufficient condition for equality of edge-connectivity and minimum degree of a graph
• Bipartite graphs and digraphs with maximum connectivity
• Degree realization of undirected graphs in reduced form
• Degree sequence conditions for maximally edge-connected graphs depending on the clique number
• Edge‐connectivity in p‐partite graphs
• scientific article; zbMATH DE number 6010646 (Why is no real title available?)
• scientific article; zbMATH DE number 4208109 (Why is no real title available?)
• scientific article; zbMATH DE number 4059448 (Why is no real title available?)
• scientific article; zbMATH DE number 3497930 (Why is no real title available?)
• scientific article; zbMATH DE number 1055145 (Why is no real title available?)
• scientific article; zbMATH DE number 1062587 (Why is no real title available?)
• scientific article; zbMATH DE number 1933046 (Why is no real title available?)
• scientific article; zbMATH DE number 822753 (Why is no real title available?)
• scientific article; zbMATH DE number 843316 (Why is no real title available?)
• scientific article; zbMATH DE number 3355058 (Why is no real title available?)
• scientific article; zbMATH DE number 2230937 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Maximally connected digraphs
• On graphs with equal edge connectivity and minimum degree
• On graphs with equal edge-connectivity and minimum degree
• Results on the edge-connectivity of graphs
• Sufficient conditions for maximally connected dense graphs

Cited in

(16)

• Degree and local connectivity in digraphs
• Localization of edges in graph models of two-level algorithms
• Edge-fault-tolerant strong Menger edge connectivity on regular graphs
• Edge fault-tolerance of strongly Menger edge connected graphs
• Connectivity in graphs and digraphs. Maximizing vertex-, edge- and arc-connectivity with an emphasis on local connectivity properties
• scientific article; zbMATH DE number 6383846 (Why is no real title available?)
• scientific article; zbMATH DE number 4019097 (Why is no real title available?)
• Maximal local edge-connectivity of diamond-free graphs
• scientific article; zbMATH DE number 4101244 (Why is no real title available?)
• Connectivity properties of locally semicomplete digraphs
• Detachments Preserving Local Edge-Connectivity of Graphs
• Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
• A characterization of panconnected graphs satisfying a local ore-type condition
• scientific article; zbMATH DE number 2192129 (Why is no real title available?)
• Large vertex-flames in uncountable digraphs
• Maximally edge-connected and vertex-connected graphs and digraphs: A survey

This page was built for publication: Local-edge-connectivity in digraphs and oriented graphs

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