Premium
On the super‐restricted arc‐connectivity of s ‐geodetic digraphs
Author(s) -
Balbuena Camino,
GarcíaVázquez Pedro,
Hansberg Adriana,
Montejano Luis Pedro
Publication year - 2013
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21462
Subject(s) - digraph , combinatorics , arc (geometry) , iterated function , mathematics , strongly connected component , cardinality (data modeling) , connectivity , geodetic datum , discrete mathematics , graph , computer science , geometry , data mining , mathematical analysis , cartography , geography
Abstract For a strongly connected digraph D the restricted arc‐connectivity λ′( D ) is defined as the minimum cardinality of an arc‐cut over all arc‐cuts S satisfying that D ‐ S has a non‐trivial strong component D 1 such that D ‐ V ( D 1 ) contains an arc. In this paper we prove that every digraph on at least 4 vertices and of minimum degree at least 2 is λ′ ‐connected and λ′( D ) ≤ξ′( D ), where ξ′( D ) is the minimum arc‐degree of D . Also in this paper we introduce the concept of super‐ λ′ digraphs and provide a sufficient condition for an s ‐geodetic digraph to be super‐ λ′. Further, we show that the h ‐iterated line digraph L h ( D ) of an s ‐geodetic digraph is super‐ λ′ for a particular h . © 2012 Wiley Periodicals, Inc. NETWORKS, 2013