Minimal strong digraphs

DOI10.1016/J.DISC.2011.11.010zbMATH Open1238.05105arXiv1004.4827OpenAlexW1970413490MaRDI QIDQ409422FDOQ409422

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

Publication date: 13 April 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (6)

• 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
• Structural and spectral properties of minimal strong digraphs
• Title not available (Why is that?)

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)