TY - JOUR
T1 - Structure of cycles in minimal strong digraphs
AU - Arcos-Argudo, Miguel
AU - García-López, Jesús
AU - Pozo-Coronado, Luis M.
PY - 2019/6/30
Y1 - 2019/6/30
N2 - This work shows a study about the structure of the cycles contained in a Minimal Strong Digraph (MSD). The structure of a given cycle is determined by the strongly connected components (or strong components, SCs)that appear after suppressing the arcs of the cycle. By this process and by the contraction of all SCs into single vertices we obtain a Hasse diagram from the MSD. Among other properties, we show that any SC conformed by more than one vertex (non trivial SC)has at least one linear vertex (a vertex with indegree and outdegree equal to 1)in the MSD (Theorem 1); that in the Hasse diagram at least one linear vertex exists for each non trivial maximal (resp. minimal)vertex (Theorem 2); that if an SC contains a number λ of vertices of the cycle then it contains at least λ linear vertices in the MSD (Theorem 3); and, finally, that given a cycle of length q contained in the MSD, the number α of linear vertices contained in the MSD satisfies α≥⌊(q+1)∕2⌋ (Theorem 4).
AB - This work shows a study about the structure of the cycles contained in a Minimal Strong Digraph (MSD). The structure of a given cycle is determined by the strongly connected components (or strong components, SCs)that appear after suppressing the arcs of the cycle. By this process and by the contraction of all SCs into single vertices we obtain a Hasse diagram from the MSD. Among other properties, we show that any SC conformed by more than one vertex (non trivial SC)has at least one linear vertex (a vertex with indegree and outdegree equal to 1)in the MSD (Theorem 1); that in the Hasse diagram at least one linear vertex exists for each non trivial maximal (resp. minimal)vertex (Theorem 2); that if an SC contains a number λ of vertices of the cycle then it contains at least λ linear vertices in the MSD (Theorem 3); and, finally, that given a cycle of length q contained in the MSD, the number α of linear vertices contained in the MSD satisfies α≥⌊(q+1)∕2⌋ (Theorem 4).
KW - Linear vertex
KW - Minimal strong digraphs
KW - Strong component
KW - Structure of the cycles
UR - http://www.scopus.com/inward/record.url?scp=85049320156&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2018.06.022
DO - 10.1016/j.dam.2018.06.022
M3 - Article
SN - 0166-218X
VL - 263
SP - 35
EP - 41
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -