Minimal strong digraphs

DOI10.1016/J.DISC.2011.11.010MaRDI QIDQ409422zbMATH OpenOpenAlexFDO

Authors J. García-López, C. Marijuán

Publication date 13 April 2012

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

isospectral strong digraphsminimal strong digraphsstrong digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Abstract: We introduce adequate concepts of expansion of a digraph to obtain a sequential construction of minimal strong digraphs. We characterize the class of minimal strong digraphs whose expansion preserves the property of minimality. We prove that every minimal strong digraph of order $ngeq2$ is the expansion of a minimal strong digraph of order $n-1$ and we give sequentially generative procedures for the constructive characterization of the classes of minimal strong digraphs. Finally we describe algorithms to compute unlabeled minimal strong digraphs and their isospectral classes.

Recommendations

• On strong digraphs with a unique minimally strong subdigraph
• Minimal strong connected digraphs
• On the upper generalized exponents of ministrong digraphs
• Upper generalized exponents of ministrong digraphs
• On spectral radius of strongly connected digraphs

Cites work

• scientific article; zbMATH DE number 3465341 (Why is no real title available?)
• scientific article; zbMATH DE number 3294293 (Why is no real title available?)
• scientific article; zbMATH DE number 3338381 (Why is no real title available?)
• scientific article; zbMATH DE number 3409391 (Why is no real title available?)
• A Simplified Form for Nearly Reducible and Nearly Decomposable Matrices
• A special class of irreducible matrices. The nearly reducible matrices
• A unified treatment of nearly reducible and nearly decomposable matrices
• Counting strong digraphs
• Decomposition of Directed Graphs
• Minimally 2-connected graphs.
• Minimally strong digraphs
• On Minimal Blocks
• On basis diagraphs
• On minimal strong blocks
• Parallel concepts in graph theory
• The Number of Strong Digraphs
• The nonnegative inverse eigenvalue problem from the coefficients of the characteristic polynomial. EBL digraphs

Cited in

(7)

• Simple dynamics on graphs
• On strong digraphs with a unique minimally strong subdigraph
• Structural properties of minimal strong digraphs versus trees
• Structure of cycles in minimal strong digraphs
• Minimal strong connected digraphs
• Structural and spectral properties of minimal strong digraphs
• scientific article; zbMATH DE number 3910427 (Why is no real title available?)

Describes a project that uses

Uses Software

• nauty

This page was built for publication: Minimal strong digraphs

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