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

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 2n−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