Premium
Maximally connected digraphs
Author(s) -
Fàbrega J.,
Fiol M. A.
Publication year - 1989
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190130603
Subject(s) - digraph , combinatorics , mathematics , iterated function , corollary , undirected graph , generalization , discrete mathematics , graph , girth (graph theory) , strongly connected component , mathematical analysis
This paper introduces a new parameter I = I(G) for a loopless digraph G , which can be thought of as a generalization of the girth of a graph. Let k , λ, δ, and D denote respectively the connectivity, arc‐connectivity, minimum degree, and diameter of G. Then it is proved that λ = δ if D ⩽ 2 I and κ k = δ if D ⩽ 2 I ‐ 1. Analogous results involving upper bounds for k and λ are given for the more general class of digraphs with loops. Sufficient conditions for a digraph to be super‐λ and super‐ k are also given. As a corollary, maximally connected and superconnected iterated line digraphs and (undirected) graphs are characterized.