Minimum cuts of distance-regular digraphs

MaRDI QIDQ2409834zbMATH OpenFDO

Authors Saleh Ashkboos, Gholamreza Omidi, Fateme Shafiei, Khosro Tajbakhsh

Publication date 16 October 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p2

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

connectivitydistance-regular digraphsminimum cutsstrongly regular digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Review text

Summary: In this paper, we investigate the structure of minimum vertex and edge cuts of distance-regular digraphs. We show that each distance-regular digraph \(\Gamma\), different from an undirected cycle, is super edge-connected, that is, any minimum edge cut of \(\Gamma\) is the set of all edges going into (or coming out of) a single vertex. Moreover, we will show that except for undirected cycles, any distance regular-digraph \(\Gamma\) with diameter \(D=2\), degree \(k\leq 3\) or \(\lambda=0\) (\(\lambda\) is the number of 2-paths from \(u\) to \(v\) for an edge \(uv\) of \(\Gamma\)) is super vertex-connected, that is, any minimum vertex cut of \(\Gamma\) is the set of all out-neighbors (or in-neighbors) of a single vertex in \(\Gamma\). These results extend the same known results for the undirected case with quite different proofs.

Recommendations

• Lower bounds of \(|X|\) and \(|Y|\) of edge-cut \( (X,Y)\) and maximality and superiority of a digraph
• Superconnectivity of regular graphs with small diameter
• On super-edge-connected digraphs and bipartite digraphs
• Double-super-connected digraphs
• Minimum arc-cuts of normally regular digraphs and Deza digraphs

Cites work

• A directed graph version of strongly regular graphs
• Algebraic characterizations of distance-regular graphs
• Certain distance-regular digraphs and related rings of characteristic 4
• Digraphs
• Distance-regular digraphs of girth 4
• Distance-transitive and distance-regular digraphs
• Eigenvalues and perfect matchings
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs
• Maximally connected digraphs
• On the superconnectivity of generalized \(p\)-cycles
• Spectra of graphs
• Strongly regular graphs, partial geometries and partially balanced designs
• The connectivity of strongly regular graphs
• The girth of a directed distance-regular graph
• The vertex-connectivity of a distance-regular graph
• Weakly distance-regular digraphs
• Weakly distance-regular digraphs.

Cited in

(3)

• Minimum arc-cuts of normally regular digraphs and Deza digraphs
• Small cutsets in arc-transitive digraphs of prime degree
• On the combinatorial structure and algebraic characterizations of distance-regular digraphs

This page was built for publication: Minimum cuts of distance-regular digraphs

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