Search

Let G be a connected graph on n vertices and D (G) be its distance matrix. The formula for computing the determinant of this matrix in terms of the number of vertices is known when the graph is either a tree or a unicyclic graph. In this work we generalize these results, obtaining the determinant of the distance matrix of any graph whose block decomposition consists of edges, unicyclic and bicyclic graphs. [ABSTRACT FROM AUTHOR]

• Rank behavior of distance matrices. • Nullity of the distance matrix of threshold graphs. • Nullity of the distance matrix of trivially perfect graphs. Let G be a connected graph with V (G) = { v 1 , ... , v n }. The (i , j) -entry of the distance matrix D (G) of G is the distance between v i and v j. In this article, using the well-known Ramsey's theorem, we prove that for each integer k ≥ 2 , there is a finite amount of graphs whose distance matrices have rank k. We exhibit the list of graphs with distance matrices of rank 2 and 3. Besides, we study the rank of the distance matrices of graphs belonging to a family of graphs with their diameters at most two, the trivially perfect graphs. We show that for each η ≥ 1 there exists a trivially perfect graph with nullity η. We also show that for threshold graphs, which are a subfamily of the family of trivially perfect graphs, the nullity is bounded by one. [ABSTRACT FROM AUTHOR]

Let B (n , q) be the class of block graphs on n vertices having all their blocks of the same size. We prove that if G ∈ B (n , q) has at most three pairwise adjacent cut vertices then the minimum spectral radius ρ (G) is attained at a unique graph. In addition, we present a lower bound for ρ (G) when G ∈ B (n , q). [ABSTRACT FROM AUTHOR]

Let G (n , α) be the class of block graphs on n vertices and prescribed independence number α. In this article we prove that the maximum spectral radius ρ (G) , among all graphs G ∈ G (n , α) , is reached at a unique graph. As a byproduct we obtain an upper for ρ (G) , when G ∈ G (n , α). [ABSTRACT FROM AUTHOR]

Abstract: A circle graph is the intersection graph of a family of chords on a circle. There is no known characterization of circle graphs by forbidden induced subgraphs that do not involve the notions of local equivalence or pivoting operations. We characterize circle graphs by a list of minimal forbidden induced subgraphs when the graph belongs to one of the following classes: linear domino graphs, -tidy graphs, and tree-cographs. We also completely characterize by minimal forbidden induced subgraphs the class of unit Helly circle graphs, which are those circle graphs having a model whose chords have all the same length, are pairwise different, and satisfy the Helly property. [Copyright &y& Elsevier]