Search

Let G be a connected graph with adjacency matrix $ A(G) $ A (G) and distance matrix $ \mathcal {D}(G) $ D (G). The adjacency-distance matrix of G is defined as $ S(G) = \mathcal {D}(G) + A(G) $ S (G) = D (G) + A (G). In this paper, $ S(G) $ S (G) is generalized by the convex linear combinations \[ S_{\alpha}(G)=\alpha \mathcal{D}(G)+(1-\alpha)A(G) \] S α (G) = α D (G) + (1 − α) A (G) where $ \alpha \in [0,1] $ α ∈ [ 0 , 1 ]. Let $ \rho (S_{\alpha }(G)) $ ρ (S α (G)) be the spectral radius of $ S_{\alpha }(G) $ S α (G). This paper presents results on $ S_{\alpha }(G) $ S α (G) with emphasis on $ \rho (S_{\alpha }(G)) $ ρ (S α (G)) and some results on $ S(G) $ S (G) are extended to all α in some subintervals of $ [0,1] $ [ 0 , 1 ]. For $ \alpha \in [1/2,1] $ α ∈ [ 1 / 2 , 1 ] , the trees attaining the largest and the smallest $ \rho (S_{\alpha }(G)) $ ρ (S α (G)) among trees of fixed order are determined and it is proved that $ \rho (S_{\alpha }(G)) $ ρ (S α (G)) is a branching index. Moreover, for $ \alpha \in (1/2,1] $ α ∈ (1 / 2 , 1 ] , the graphs that uniquely minimize $ \rho (S_{\alpha }(G)) $ ρ (S α (G)) : among all connected graphs of fixed order and fixed connectivity, and among all connected graphs of fixed order and fixed chromatic number are characterized. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with the adjacency matrix $ A(G) $ A (G). Let $ \tau (G) $ τ (G) denote the smallest positive eigenvalue of $ A(G) $ A (G). In 1990, Pavlíková and Kr $ \breve{c} $ c ˘ -Jediný proved that among all nonsingular trees on n = 2m vertices, the comb graph (obtained by taking a path on m vertices and adding a new pendant vertex to every vertex of the path) has the maximum τ value. We consider the problem for unicyclic graphs. Let $ \mathscr {U} $ U denote the class of all connected bipartite unicyclic graphs with a unique perfect matching, and for each $ m\geq ~3 $ m ≥ 3 , let $ \mathscr {U}_n $ U n be the subclass of $ \mathscr {U} $ U with graphs on n = 2m vertices. We first obtain the classes of unicyclic graphs U in $ \mathscr {U} $ U such that $ \tau (U)\leq \sqrt {2}-1 $ τ (U) ≤ 2 − 1. We then find the unique graph $ U_o^n $ U o n (resp. $ U_e^n $ U e n ) having the maximum τ value among all graphs in $ \mathscr {U}_n $ U n when m is odd (resp. when m is even). Finally, we prove that $ U_o^6 $ U o 6 (the graph obtained from a cycle of order 4, by adding two pendants to two adjacent vertices) is the graph with maximum τ value among all graphs in $ \mathscr {U} $ U . As a consequence, we obtain a sharp upper bound for $ \tau (U) $ τ (U) when $ U\in \mathscr {U} $ U ∈ U . [ABSTRACT FROM AUTHOR]

Let G be a graph, and let $ A(G) $ A (G) be the adjacency matrix of G. The computation of permanent of $ A(G) $ A (G) is #p-complete. Computing permanent of $ A(G) $ A (G) is of great interest in quantum chemistry, statistical physics, among other disciplines. In this paper, we characterize the ordering of permanents of adjacency matrices of all graphs obtained from regular complete bipartite graph $ K_{p, p} $ K p , p by deleting six edges. As an application, we show that all graphs with a perfect matching obtained from $ K_{p, p} $ K p , p with six edges deleted are determined by their permanental polynomials. [ABSTRACT FROM AUTHOR]

We consider particular weighted directed graphs with edges having colour red, blue or green such that each red edge has weight 1, each blue edge has weight $ -1 $ − 1 and each green edge has weight $ \mathrm {i} $ i (the imaginary unit). Such a directed graph is called a 3-coloured digraph (for short, a 3-CD). Every mixed graph and every signed graph can be interpreted as a 3-CD. We first study some structural properties of 3-CDs by means of the eigenvalues of the adjacency matrix. In particular, we give spectral criteria for singularity of such digraphs. Second, we consider weight-symmetric 3-CDs, i.e. those 3-CDs that are switching isomorphic to their negation. It follows that the class of weight-symmetric 3-CDs is included in the class of 3-CDs whose spectrum is symmetric (with respect to the origin). We give some basic properties and several constructions of weight-symmetric 3-CDs and establish constructions of 3-CDs which have symmetric spectrum but are not weight-symmetric. [ABSTRACT FROM AUTHOR]

Let G n , β be the set of graphs of order n with given matching number β. Let D (G) be the diagonal matrix of the degrees of the graph G and A (G) be the adjacency matrix of the graph G. The largest eigenvalue of the nonnegative matrix A α (G) = α D (G) + A (G) is called the α-spectral radius of G. The graphs with maximal α-spectral radius in G n , β are completely characterized in this paper. In this way, we provide a general framework to attack the problem of extremal spectral radius in G n , β . More precisely, we generalize the known results on the maximal adjacency spectral radius in G n , β and the signless Laplacian spectral radius. [ABSTRACT FROM AUTHOR]

The class of unicyclic non-bipartite graphs with unique perfect matching, denoted by U , is considered in this article. This article provides a complete characterization of unicyclic graphs in U which possess tricyclic inverses. [ABSTRACT FROM AUTHOR]

It was shown in 2006 that among the nonsingular trees T (whose adjacency matrix A(T) is nonsingular), the corona trees (trees that are obtained by taking any tree T and then adding a new pendant vertex at each vertex of T) are the only ones which satisfy the reciprocal eigenvalue property (λ is an eigenvalue of A(T) if and only if 1 λ is an eigenvalue of A(T), where their multiplicities are allowed to be different). A general question remained open. Can there be a tree which has at least one zero eigenvalue and whose nonzero eigenvalues satisfy the reciprocal eigenvalue property? In this note, we show that there are no such trees with at least two vertices. The proof is a beautiful application of the product of graphs. [ABSTRACT FROM AUTHOR]

The energy of a graph is defined as the sum of the absolute values of all eigenvalues with respect to its adjacency matrix. Denote by Gn,m the set of all connected graphs having n vertices and m edges. Caporossi et al. [Caporossi G, Cvetkovi D, Gutman I, et al. Variable neighbourhood search for extremal graphs. 2. Finding graphs with external energy. J Chem Inf Comput Sci. 1999;39:984–996] conjectured that among all graphs in Gn,m, n ≥ 6 and n − 1 ≤ m ≤ 2(n − 2), the graphs with minimum energy are the star Sn with m−n + 1 additional edges all connected to the same vertices for m ≤ n + ⌊ (n − 7) / 2 ⌋ , and the bipartite graph with two vertices on one side, one of which is connected to all vertices on the other side, otherwise. In this paper, we provide a new approach to investigate the conjecture above. Especially, we determine the unique tetracyclic graph having minimum energy. [ABSTRACT FROM AUTHOR]

This article provides a combinatorial description of the inverse of the adjacency matrix of a non-singular 3-coloured digraph. The class of unicyclic 3-coloured digraphs with the cycle weight ±i and with a unique perfect matching, denoted by U g , is considered in this article. We characterize the 3-coloured digraphs in U g whose inverses are again 3-coloured digraphs. Furthermore, the 3-coloured digraphs in U g whose inverses are bipartite are also characterized. It is proved that the inverses of the 3-coloured digraphs in U g are always Laplacian non-singular. Characterizations of unicyclic 3-coloured digraphs in U g possessing unicyclic inverses are also supplied in this article. As an application, we can obtain the class of unicyclic 3-coloured digraphs with the cycle weight ±i satisfying the strong reciprocal eigenvalue property. [ABSTRACT FROM AUTHOR]

Let G be an undirected graph with adjacency matrix A (G). For a vertex u ∈ V (G) , the subgraph centrality of u in G is C S (u) = (exp ⁡ (A (G))) u u = ∑ k = 0 ∞ 1 k ! (A (G) k) u u . In this paper, we give some formulas for C S (u) by using equitable partitions and star sets of G. [ABSTRACT FROM AUTHOR]

In [A note about cospectral graphs for the adjacency and normalized Laplacian matrices. Linear Multilinear Algebra. 2010;58(3-4):387–390], Butler constructed a family of bipartite graphs, which are cospectral for both the adjacency and the normalized Laplacian matrices. In this article, we extend this construction for generating larger classes of bipartite graphs, which are cospectral for both the adjacency and the normalized Laplacian matrices. Also, we provide a couple of constructions of non-bipartite graphs, which are cospectral for the adjacency matrices but not necessarily for the normalized Laplacian matrices. [ABSTRACT FROM AUTHOR]

The class of non-bipartite unicyclic graphs with a unique perfect matching, denoted by U , is considered in this article. This article describes the entries of the inverse of the adjacency matrix of a graph in U . It is proved that the inverse graph of a graph in U is always non-bipartite. In this article, we characterize the graphs in U whose inverses are mixed graphs. Among all such graphs in U we identify those graphs whose inverses are quasi-bipartite. Furthermore, characterizations of unicyclic graphs in U possessing unicyclic and bicyclic inverses are also provided in this article. [ABSTRACT FROM AUTHOR]

Let G be a digraph and A (G) be the adjacency matrix of G. Let D (G) be the diagonal matrix with outdegrees of vertices of G. For any real α ∈ [ 0 , 1 ] , define the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G). The largest modulus of the eigenvalues of A α (G) is called the A α spectral radius of G. In this paper, we determine the digraphs which attain the maximum (or minimum) A α spectral radius among all strongly connected digraphs with given parameters such as girth, clique number, vertex connectivity or arc connectivity. We also propose an open problem. [ABSTRACT FROM AUTHOR]

Given two graphs, a backbone and a finger, a comb product is a new graph obtained by grafting a copy of the finger into each vertex of the backbone. We study the comb graphs in the case when both components are the paths of order n and k, respectively, as well as the above comb graphs with an infinite ray attached to some of their vertices. A detailed spectral analysis is carried out in both situations. [ABSTRACT FROM AUTHOR]

In this paper we consider strongly regular graphs G which admit a decomposition into two strongly regular graphs such that one of them, say H, is a star complement of G. Relations between the parameters of graphs paired in this way are determined. We also consider several particular types of strongly regular graph and determine whether such graphs can appear in the role of G or H. [ABSTRACT FROM AUTHOR]

Let be a symmetric matrix, or equivalently, a weighted graph whose edge ij has the weight. The eigenvalues of are the eigenvalues of M. We denote by the principal submatrix of M obtained by deleting from M both the ith row and the ith column. If μ is an eigenvalue of M, and thus of , of multiplicity , then vertex i of is a downer, or a neutral, or a Parter vertex, depending whether the multiplicity of μ in or, equivalently, in , is k−1, k, or k+1, respectively. In this paper, for a fixed μ, we consider vertex types according to the above classification in graphs which are generalized lexicographic products of an arbitrary graph over cliques and co-cliques, or connected regular graphs. In addition, we add some comments on constructions of large families of cospectral and integral graphs. [ABSTRACT FROM AUTHOR]

A cograph is a simple graph which contains no path on 4 vertices as an induced subgraph. We consider the eigenvalues of adjacency matrices of cographs and prove that a graph G is a cograph if and only if no induced subgraph of G has an eigenvalue in the interval. It is also shown that the multiplicity of any eigenvalue of a cograph G does not exceed the sum of multiplicities of 0 and as eigenvalues of G. We introduce a partial order on the vertex set of graphs G in terms of inclusions among the open and closed neighbourhoods of vertices, and conjecture that the multiplicity of any eigenvalue of a cograph G except for does not exceed the maximum size of an antichain with respect to that partial order. In two extreme cases (in particular for threshold graphs), the conjecture is shown to be true. Finally, we prove that bipartite -free graphs have no eigenvalue in the intervals and (0, 1 / 2). [ABSTRACT FROM AUTHOR]

Let be a signed graph, where G is the underlying simple graph and is the sign function on the edges of G. The adjacency matrix of a signed graph has or for adjacent vertices, depending on the sign of the connecting edges. In this paper, the eigenvalues of signed complete graphs are investigated. We prove that and 1 are the eigenvalues of the signed complete graph with the multiplicity at least t if there are vertices whose all incident edges are positive or negative, respectively. We study the spectrum of a signed complete graph whose negative edges induce an r-regular subgraph H. We obtain a relation between the eigenvalues of this signed complete graph and the eigenvalues of H. [ABSTRACT FROM AUTHOR]

Let be a finite-dimensional Hilbert space and be a finite frame for . For , we associate a simple graph denoted by and called frame graph, with all elements of as vertices, and two distinct vertices are adjacent when the inner product of them is nonzero. The associated graph is called a tight frame graph if the mentioned frame is tight. In this paper, we study some basic properties of and investigate the relation between the frame-theoretic properties of and the graph-theoretic properties of . For example, it is shown that trees on more than two vertices and cycles on more than five vertices are not tight frame graphs while complete graphs, complete graphs minus a single edge and the join of each graph with itself are tight frame graphs. [ABSTRACT FROM AUTHOR]

In this paper we focus on connected signed graphs of fixed number of vertices, positive edges and negative edges that maximize the largest eigenvalue (also called the index) of their adjacency matrix. In the first step we determine these signed graphs in the set of signed generalized theta graphs. Concerning the general case, we use the eigenvector techniques for getting some structural properties of resulting signed graphs. In particular, we prove that positive edges induce nested split subgraphs, while negative edges induce double nested signed subgraphs.We observe that our concept can be applied when considering balancedness of signed graphs (the property that is extensively studied in both mathematical and non-mathematical context). [ABSTRACT FROM AUTHOR]

We give sharp upper and lower bounds for the spectral radius of a nonnegative matrix with positive row sums using average 3-row sums, compare these bounds with the existing bounds using the average 2-row sums by examples, and apply them to the adjacency matrix and the signless Laplacian matrix of a digraph or a graph. [ABSTRACT FROM AUTHOR]

A weighted Bethe graphBis obtained from a weighted generalized Bethe tree by identifying each set of children with the vertices of a graph belonging to a familyFof graphs. The operation of identifying the root vertex of each ofrweighted Bethe graphs to the vertices of a connected graphof orderris introduced as the-concatenation of a family ofrweighted Bethe graphs. It is shown that the Laplacian eigenvalues (whenFhas arbitrary graphs) as well as the signless Laplacian and adjacency eigenvalues (when the graphs inFare all regular) of the-concatenation of a family of weighted Bethe graphs can be computed (in a unified way) using the stable and low computational cost methods available for the determination of the eigenvalues of symmetric tridiagonal matrices. Unlike the previous results already obtained on this topic, the more general context of families of distinct weighted Bethe graphs is herein considered. [ABSTRACT FROM PUBLISHER]

Graphs with least eigenvalue greater than or equal toare to a big extent studied by Hoffman and other authors from the early beginning of the spectral graph theory. Most of these results are summarized in the monograph [Cvetković D, Rowlinson P, Simić S. Spectral generalizations of line graphs, on graphs with least eigenvalue, Cambridge University Press, 2004], and the survey paper [Cvetković D, Rowlinson P, Simić S. Graphs with least eigenvalue: ten years on, Linear Algebra Appl. 2015;484:504–539] which is aimed to cover the next 10 years since their monograph appeared. Here, we add some further results. Among others, we identify graphs whose least eigenvalue is greater than, but closest towithin the graphs of fixed order. Some consequences of these considerations are found in the context of the highest occupied molecular orbital–lowest unoccupied molecular orbital invariants. [ABSTRACT FROM AUTHOR]

A graphis nonsingular if its adjacency matrixis nonsingular. A nonsingular graphis said to have an inverseifis signature similar to a nonnegative matrix. An-graphis a bipartite graph with a unique perfect matching. We introduce the ‘even’ness of a nonmatching edge and show that under certain conditions a connected-graph has an inverse if and only ifis bipartite, whereis the set of all even nonmatching edges. This extends some known results, providing us with a larger class of graphs possessing inverses. [ABSTRACT FROM PUBLISHER]

A signed graphconsists of an underlying graphand a sign function, which assigns each edge ofa sign, either positive or negative. The adjacency matrix of a signed graphis defined aswith, whereis the adjacency matrix of the underlying graph. The rank ofis defined to be the rank of. In this paper, we characterize the signed graphs with rankor, and characterize the signed planar graphs with rank 4. [ABSTRACT FROM PUBLISHER]

Letandbe two vertex disjoint graphs of ordersandrespectively, whereandLetbe a specified edge ofsuch thatis isomorphic toLetbe a subset of the edge set ofand letdenote the subgraph ofinduced byLetbe the graph obtained by taking one copy ofandvertex disjoint copies ofand then pasting the edgein theth copy ofwith the edgewhereThen the copies of the graphthat are pasted to the edgesare called as edge-pockets, and we sayis a graph withedge-pockets. In this article, we prove some results describing the Laplacian (resp. adjacency) spectrum ofusing the Laplacian (resp. adjacency) spectra ofandThe complete Laplacian (resp. adjacency) spectrum ofis also described in some particular cases. As an application, we show that these results enable us to construct infinitely many pairs of Laplacian (resp. adjacency) cospectral graphs. [ABSTRACT FROM AUTHOR]

A block graph is a graph in which every block is a complete graph. Letbe a block graph and letbe the adjacency matrix of. We first obtain a formula for the determinant ofover reals. It is shown thatis nonsingular overif and only if the removal of any vertex fromproduces a graph with exactly one odd component. A formula for the inverse ofoveris obtained, whenever it exists. We obtain some results for the adjacency matrices over, of claw-free block graphs, which are the same as the line graphs of trees, and for the adjacency matrices of flowers, which are block graphs with only one cut-vertex. [ABSTRACT FROM AUTHOR]

Two graphs are said to be A-cospectral if they have the same adjacency spectrum. A graphGis said to be determined by its adjacency spectrum if there is no other non-isomorphic graph A-cospectral withG. A tree is called starlike if it has exactly one vertex of degree greater than 2. In this article, we prove that the line graphs of starlike trees with maximum degree at least 12 are determined by their adjacency spectra. [ABSTRACT FROM AUTHOR]

The nullity η(G) of a graph G is the multiplicity of zero as an eigenvalue of the adjacency matrix of G. If η(G)= 1, then the core of G is the subgraph induced by the vertices associated with the nonzero entries of the kernel eigenvector. The set of vertices which are not in the core is the periphery of G. A graph G with nullity one is minimal configuration if no two vertices in the periphery are adjacent and deletion of any vertex in the periphery increases the nullity. An ∞-graph ∞(p, l, q) is a graph obtained by joining two vertex-disjoint cycles Cp and Cq by a path of length l≥ 0. Let B* be the class of bicyclic graphs with an ∞-graph as an induced subgraph. In this article, we characterize the graphs in B* which are minimal configurations. [ABSTRACT FROM AUTHOR]

The signless Laplacian matrix of a graph is defined to be the sum of its adjacency matrix and degree matrix. Let [image omitted] be the set of all the connected graphs of order n and diameter d and Gn,k the set of all connected graphs with order n and k cut vertices. In this article, we determine the graphs that have the maximal signless Laplacian spectral radius and give the upper bounds of graphs in these two sets. [ABSTRACT FROM AUTHOR]

We characterize all regular graphs whose second largest eigenvalue does not exceed 1. In the sequel, we determine all coronas, different from cones, with the same property. Some results and examples regarding unsolved cases are also given. [ABSTRACT FROM AUTHOR]

In this note we show how to construct two distinct bipartite graphs which are cospectral for both the adjacency and normalized Laplacian matrices by 'unfolding' a base bipartite graph in two different ways. [ABSTRACT FROM AUTHOR]

In this article we follow the study of the hierarchical product of graphs, an operation recently introduced in the context of networks. A well-known example of such a product is the binomial tree which is the (hierarchical) power of the complete graph on two vertices. An appealing property of this structure is that all the eigenvalues are distinct. Here we show how to obtain a graph with this property by applying the hierarchical product. In particular, we propose a generalization of the binomial tree and study some of its main properties. [ABSTRACT FROM AUTHOR]

A graph G is singular with nullity η(G), if zero is an eigenvalue of its adjacency matrix with multiplicity η(G). If η(G) = 1, then the core of G is the subgraph induced by the vertices associated with the non-zero entries of the kernel eigenvector. The set of vertices which are not in the core is called the periphery of G. A graph G with nullity one is called a minimal configuration if no two vertices in the periphery are adjacent and deletion of any vertex in the periphery increases the nullity. In this article, we describe the structure of a singular unicyclic graph and single out the class of unicyclic graphs which are minimal configurations. [ABSTRACT FROM AUTHOR]

We consider the problem of reconstructing the characteristic polynomial of a graph G from its polynomial deck, i.e. the collection of characteristic polynomials of its vertex-deleted subgraphs. Here we provide a positive solution for all unicyclic graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph. Let A(G) be the adjacency matrix of G . We give a combinatorial description of A ( G )-1 of a bipartite graph G with a unique perfect matching. As a corollary, we obtain the combinatorial description of the inverse of a nonsingular tree. A graph is said to have property (R) if 1/λis an eigenvalue of G whenever  λ  is an eigenvalue of G . Further, if  λ  and have the same multiplicity, for each eigenvalue  λ  then it is said to have the property (SR). We characterize all trees with property (R) and show that it is exactly the class of all trees with property (SR). The class of trees with property (R) is also identical to the class of corona trees, namely, the trees which can be obtained from other trees by adding pendants to all vertices. Other equivalent conditions for a tree to have property (R) are also given. [ABSTRACT FROM AUTHOR]

A graph is singular of nullity η if zero is an eigenvalue of its adjacency matrix with multiplicity η. If η( G )=1, then the core of G is the subgraph induced by the vertices associated with the non-zero entries of the zero-eigenvector. A connected subgraph of G with the least number of vertices and edges, that has nullity one and the same core as G , is called a minimal configuration. A subdivision of a graph G is obtained by inserting a vertex on every edge of G . We review various properties of minimal configurations. In particular, we show that a minimal configuration is a tree if and only if it is a subdivision of some other tree. [ABSTRACT FROM AUTHOR]

A graph G is said to be retarded regular if there is a positive integral number s such that the number of walks of length s starting at vertices of G is a constant function. Regular and semiregular graphs are retarded regular with s = 1 and s\!≤ \!2, respectively. We prove that any retarded regular connected graph is either regular or semiregular. [ABSTRACT FROM AUTHOR]