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
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom