Structure of cycles in minimal strong digraphs

Arcos-Agudo, Miguel and García López De Lacalle, Jesús and Pozo Coronado, Luis Miguel (2019). Structure of cycles in minimal strong digraphs. "Discretet Applied Matemathics", v. 263 ; pp. 35-41. ISSN 0166-218X. https://doi.org/10.1016/j.dam.2018.06.022.

Description

Title: Structure of cycles in minimal strong digraphs
Author/s:
  • Arcos-Agudo, Miguel
  • García López De Lacalle, Jesús
  • Pozo Coronado, Luis Miguel
Item Type: Article
Título de Revista/Publicación: Discretet Applied Matemathics
Date: 30 June 2019
ISSN: 0166-218X
Volume: 263
Subjects:
Freetext Keywords: Minimal strong digraphs; Structure of the cycles; Linear vertex; Strong component
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Matemática Aplicada a las Tecnologías de la Información y las Comunicaciones
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] PDF - Users in campus UPM only until 30 June 2021 - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (834kB)

Abstract

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 contained in the MSD, the number of linear vertices contained in the MSD satisfies α≥ ⌊(q+1)/2⌋ (Theorem 4).

More information

Item ID: 64357
DC Identifier: http://oa.upm.es/64357/
OAI Identifier: oai:oa.upm.es:64357
DOI: 10.1016/j.dam.2018.06.022
Official URL: https://www.sciencedirect.com/science/article/abs/pii/S0166218X18303585?via%3Dihub
Deposited by: Memoria Investigacion
Deposited on: 22 Jan 2021 15:40
Last Modified: 22 Jan 2021 15:40
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM