Cyclic Structure, Vertex Degree and Number of Linear Vertices in Minimal Strong Digraphs

Miguel Arcos-Argudo (), Jesús Lacalle and Luis M. Pozo-Coronado
Additional contact information
Miguel Arcos-Argudo: Math Innovation Group, Universidad Politécnica Salesiana, Cuenca 010102, Ecuador
Jesús Lacalle: Departmento de MATIC, ETSI Sistemas Informáticos, Universidad Politécnica de Madrid, 28031 Madrid, Spain
Luis M. Pozo-Coronado: Departmento de MATIC, ETSI Sistemas Informáticos, Universidad Politécnica de Madrid, 28031 Madrid, Spain

Mathematics, 2024, vol. 12, issue 23, 1-11

Abstract: Minimal Strong Digraphs (MSDs) can be regarded as a generalization of the concept of tree to directed graphs. Their cyclic structure and some spectral properties have been studied in several articles. In this work, we further study some properties of MSDs that have to do with bounding the length of the longest cycle (regarding the number of linear vertices, or the maximal in- or outdegree of vertices); studying whatever consequences from the spectral point of view; and giving some insight about the circumstances in which an efficient algorithm to find the longest cycle contained in an MSD can be formulated. Among other properties, we show that the number of linear vertices contained in an MSD is greater than or equal to the maximal (respectively minimal) in- or outdegree of any vertex of the MSD and that the maximal length of a cycle contained in an MSD is lesser than or equal to 2 n − m where n , m are the order and the size of the MSD, respectively; we find a bound for the coefficients of the characteristic polynomial of an MSD, and finally, we prove that computing the longest cycle contained in an MSD is an NP-hard problem.

Keywords: minimal strong digraphs; maximum length directed cycles; linear vertex; external chain; characteristic polynomial; NP-hard problem (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/23/3657/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/23/3657/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:23:p:3657-:d:1527171

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().