Search

In the paper, we introduce the signless Laplacian A B C -matrix Q ̃ (G) = D ¯ (G) + A ̃ (G) , where D ¯ (G) is the diagonal matrix of A B C -degrees and A ̃ (G) is the A B C -matrix of G. The eigenvalues of the matrix Q ̃ (G) are the signless Laplacian A B C -eigenvalues of G. We give some basic properties of the matrix Q ̃ (G) , which includes relating independence number and clique number with signless Laplacian A B C -eigenvalues. For bipartite graphs, we show that the signless Laplacian A B C -spectrum and the Laplacian A B C -spectrum are the same. We characterize the graphs with exactly two distinct signless Laplacian A B C -eigenvalues. Also, we consider the problem of the characterization of the graphs with exactly three distinct signless Laplacian A B C -eigenvalues and solve it for bipartite graphs and, in some cases, for non-bipartite graphs. We also introduce the concept of the trace norm of the matrix Q ̃ (G) − t r (Q ̃ (G)) n I , called the signless Laplacian A B C -energy of G. We obtain some upper and lower bounds for signless Laplacian A B C -energy and characterize the extremal graphs attaining it. Further, for graphs of order at most 6, we compare the signless Laplacian energy and the A B C -energy with the signless Laplacian A B C -energy and found that the latter behaves well, as there is a single pair of graphs with the same signless Laplacian A B C -energy unlike the 26 pairs of graphs with same signless Laplacian energy and eight pairs of graphs with the same A B C -energy. [ABSTRACT FROM AUTHOR]

We extend the notion of balance from the realm of signed and gain graphs to conjugate skew gain graphs which are skew gain graphs where the labels on the oriented edges get conjugated when we reverse the orientation. We characterize the balance in a conjugate skew gain graph in several ways especially by dealing with its adjacency matrix and the g -Laplacian matrix. We also deal with the concept of anti-balance in conjugate skew gain graphs. [ABSTRACT FROM AUTHOR]

This paper established the idea of minimum evdominating matrix of semigraph and calculated its energy. The minimum ev-dominating energy EmeD(G) of a semigraph G is the sum of the absolute values of the eigenvalues of the minimum ev-dominating matrix. Here some results are also derived in connection with the energy of minimum evdominating matrix. Some lower bounds are also established. [ABSTRACT FROM AUTHOR]

Let A(G) be the adjacency matrix of a simple connected undirected graph G. A graph G of order n is said to be non-singular (respectively singular) if A(G) is non-singular (respectively singular). The spectrum of a graph G is the set of all its eigenvalues denoted by spec(G). The antireciprocal (respectively reciprocal) eigenvalue property for a graph G can be defined as "Let G be a non-singular graph G if the negative reciprocal (respectively positive reciprocal) of each eigenvalue is likewise an eigenvalue of G, then G has anti-reciprocal (respectively reciprocal) eigenvalue property." Furthermore, a graph G is said to have strong anti-reciprocal eigenvalue property (resp. strong reciprocal eigenvalue property) if the eigenvalues and their negative (resp. positive) reciprocals are of same multiplicities. In this article, graphs satisfying anti-reciprocal eigenvalue (or property (-R)) and strong anti-reciprocal eigenvalue property (or property (-SR)) are discussed. [ABSTRACT FROM AUTHOR]

For the adjacency matrix A(G) and diagonal matrix of the vertex degrees D(G) of a simple graph G, the A(G) matrix is the convex combinations of D(G) and A(G), and is defined as A(G) = D(G)+(1)A(G), for 0 n be the eigenvalues of A(G) (which we call -adjacency eigenvalues of the graph G). The generalized adjacency energy also called -adjacency energy of the graph G is defined as EA (G) = is the average vertex degree, m is the size and n is the order of G. The -adjacency energy of a graph G merges the theory of energy (adjacency energy) and the signless Laplacian energy, as EA0 (G) = E (G) and 2E A 12 (G) = QE(G), where E (G) is the energy and QE(G) is the signless Laplacian energy of G. In this paper, we obtain some new upper and lower bounds for the generalized adjacency energy of a graph, in terms of different graph parameters like the vertex covering number, the Zagreb index, the number of edges, the number of vertices, etc. We characterize the extremal graphs attained these bounds. [ABSTRACT FROM AUTHOR]

In this article, we discuss the spectral properties of the general extended adjacency matrix for chain graphs. In particular, we discuss the eigenvalues of the general extended adjacency matrix of the chain graphs and obtain its general extended adjacency inertia. We obtain bounds for the largest and the smallest general extended adjacency eigenvalues and characterize the extremal graphs. We also obtain a lower bound for the spread of the general extended adjacency matrix. We characterize chain graphs with all the general extended adjacency eigenvalues being simple and chain graphs that are non-singular under the general extended adjacency matrix. Further, we determine the explicit formula for the determinant and the trace of the square of the general extended adjacency matrix of chain graphs. Finally, we discuss the energy of the general extended adjacency matrix and obtain some bounds for it. We characterize the extremal chain graphs attaining these bounds. [ABSTRACT FROM AUTHOR]

Two linear algebra problems implore a solution to them, creating the themes pursued in this paper. The first problem interfaces with graph theory via binary 0-1 adjacency matrices and their Laplacian counterparts. More contemporary spatial statistics/econometrics applications motivate the second problem, which embodies approximating the eigenvalues of massively large versions of these two aforementioned matrices. The proposed solutions outlined in this paper essentially are a reformulated multiple linear regression analysis for the first problem and a matrix inertia refinement adapted to existing work for the second problem. [ABSTRACT FROM AUTHOR]

Spectral problems are considered generated by the Sturm-Liouville equation on equilateral trees with the Dirichlet boundary conditions at the pendant vertices and continuity and Kirchhoff's conditions at the interior vertices. It is proved that there are no co-spectral (i.e., having the same spectrum of such problem) among equilateral trees of = 8 vertices. All co-spectral trees of 9 vertices are presented. [ABSTRACT FROM AUTHOR]

For a simple connected graph G with node set V(G) = {w1,w2, ...,wn} and degree sequence di, the atom-bond connectivity (ABC) matrix of G has an (i j)-th entry q di+dj-2 didj if wi is adjacent to wj and 0, otherwise. The multiset of all eigenvalues of ABC matrix is known as the ABC spectrum and their absolute sum is known as the ABC energy of G. Two graphs of same order are known as ABC equienergetic if they have the same ABC energy but share different ABC spectrum. We describe the ABC spectrum of some special graph operations and as an application, we construct the ABC equienergetic graphs. Further, we give linear regression analysis of ABC index/energy with the physical properties of anticancer drugs. We observe that they are better correlated with ABC-energy. [ABSTRACT FROM AUTHOR]

Let D(G) and A(G), respectively, be the diagonal matrix of vertex de- grees and the adjacency matrix of a connected graph G. The generalized adjacency matrix of G is defined as Aα(G) = αD(G) + (1 − α)A(G), α ∈ [0, 1]. The spread of the generalized adjacency matrix, denoted by S(Aα(G)), is defined as the difference of the largest and smallest eigenvalues of Aα(G). The spread S(Q(G)) of Q(G), the signless Laplacian matrix of G and S(A(G)) of A(G) are similarly defined. In this paper, we establish the relationships between S(Aα(G)), S(Q(G)) and S(A(G)). Further, we find bounds for S(Aα(G)) involving different parameters of G. Also, we obtain lower bounds for S(Aα(G)) in terms of the clique number and independence number of G, and we characterize the extremal graphs in some cases. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a simple connected graph with vertex set V and edge set E, respectively. The term "anti-reciprocal eigenvalue property" refers to a non-singular graph G for which, − 1 λ ∈ σ (G) , whenever λ ∈ σ (G) , ∀ λ ∈ σ (G) . Here, σ (G) is the multiset of all eigenvalues of A (G) . Moreover, if multiplicities of eigenvalues and their negative reciprocals are equal, then that graph is said to have strong anti-reciprocal eigenvalue properties, and the graph is referred to as a strong anti-reciprocal graph (or (− S R) graph). In this article, a new family of graphs F n (k , j) is introduced and the energy of F 5 (k , k 2) k ≥ 2 is calculated. Furthermore, with the help of F 5 (k , k 2) , some families of (− S R) graphs are constructed. [ABSTRACT FROM AUTHOR]

Let G be a graph with the adjacency matrix A (G) , and let D (G) be the diagonal matrix of the degrees of G. Nikiforov first defined the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G) , 0 ≤ α ≤ 1 , which shed new light on A (G) and Q (G) = D (G) + A (G) , and yielded some surprises. The α − adjacency energy E A α (G) of G is a new invariant that is calculated from the eigenvalues of A α (G) . In this work, by combining matrix theory and the graph structure properties, we provide some upper and lower bounds for E A α (G) in terms of graph parameters (the order n, the edge size m, etc.) and characterize the corresponding extremal graphs. In addition, we obtain some relations between E A α (G) and other energies such as the energy E (G) . Some results can be applied to appropriately estimate the α -adjacency energy using some given graph parameters rather than by performing some tedious calculations. [ABSTRACT FROM AUTHOR]

Let Gw be a simple weighted graph with adjacency matrix A(Gw). The set of all eigenvalues of A(Gw) is called the spectrum of weighted graph Gw denoted by σ(Gw). The reciprocal eigenvalue property (or property R) for a connected weighted nonsingular graph Gw is defined as, if η ∈ σ(Gw) then 1 η ∈ σ(Gw). Further, if η and 1 η have the same multiplicities for each η ∈ σ(Gw) then this graph is said to have strong reciprocal eigenvalue property (or property SR). Similarly, a connected weighted nonsingular graph Gw is said to have anti-reciprocal eigenvalue property (or property -R) if η ∈ σ(Gw) then - 1 η ∈ σ(Gw). Furthermore, if η and - 1 η have the same multiplicities for each η ∈ σ(Gw) then strong anti-reciprocal eigenvalue property (or property -SR) holds for the weighted graph Gw. In this article, classes of weighted noncorona graphs satisfying property R and property -SR are studied. [ABSTRACT FROM AUTHOR]

In this paper, we study the prime order Cayley graph assigned to the group ℤn for different values of n. We specify some of the graph theoretical properties such as chromatic and perfect matching numbers. Furthermore, we determine the adjacency matrices and eigenvalues of the prime order Cayley graph associated with groups ℤn and 풟2n. [ABSTRACT FROM AUTHOR]

For a simple graph with vertex set { v 1 , v 2 , ... , v n } with degree sequence d v i of vertex v i , i = 1 , 2 , ... , n , the inverse sum indeg matrix ( I S I -matrix) A I S I (G) = (a i j) n × n of G is defined by a i j = d v i d v j d v i + d v j , if v i is adjacent to v j , and zero, otherwise. The multiset of eigenvalues of A I S I (G) is the I S I -spectrum of G and the sum of their absolute values is the I S I -energy of G . In this paper, we modify the two results of (Li, Ye and Broersma, 2022), give the correct characterization of the extremal graphs and thereby obtain better bounds than the already known results. Moreover, we also discuss the QSPR analysis and carry the statistical modelling (linear, logarithmic and quadratic) of the physicochemical properties of anticancer drugs with the I S I -index (energy). [ABSTRACT FROM AUTHOR]

A singular graph G, defined when its adjacency matrix is singular, has important applications in mathematics, natural sciences and engineering. The chemical importance of singular graphs lies in the fact that if the molecular graph is singular, the nullity (the number of the zero eigenvalue) is greater than 0, then the corresponding chemical compound is highly reactive or unstable. By this reasoning, chemists have a great interest in this problem. Thus, the problem of characterization singular graphs was proposed and raised extensive studies on this challenging problem thereafter. The graph obtained by conglutinating the starting vertices of three paths P s 1 , P s 2 , P s 3 into a vertex, and three end vertices into a vertex on the cycle C a 1 , C a 2 , C a 3 , respectively, is denoted as γ (a 1 , a 2 , a 3 , s 1 , s 2 , s 3) . Note that δ (a 1 , a 2 , a 3 , s 1 , s 2) = γ (a 1 , a 2 , a 3 , s 1 , 1 , s 2) , ζ (a 1 , a 2 , a 3 , s) = γ (a 1 , a 2 , a 3 , 1 , 1 , s) , φ (a 1 , a 2 , a 3) = γ (a 1 , a 2 , a 3 , 1 , 1 , 1) . In this paper, we give the necessity and sufficiency that the γ − graph, δ − graph, ζ − graph and φ − graph are singular and prove that the probability that a randomly given γ − graph, δ − graph, ζ − graph or φ − graph being singular is equal to 325 512 , 165 256 , 43 64 , 21 32 , respectively. From our main results, we can conclude that such a γ − graph( δ − graph, ζ − graph, φ − graph) is singular if at least one cycle is a multiple of 4 in length, and surprisingly, the theoretical probability of these graphs being singular is more than half. This result promotes the understanding of a singular graph and may be promising to propel the solutions to relevant application problems. [ABSTRACT FROM AUTHOR]

We consider signed graphs with just 2 or 3 distinct eigenvalues, in particular (i) those with at least one simple eigenvalue, and (ii) those with vertex-deleted subgraphs which themselves have at most 3 distinct eigenvalues. We also construct new examples using weighing matrices and symmetric 3-class association schemes. [ABSTRACT FROM AUTHOR]

The A γ matrix of a graph G is determined by A γ (G) = (1 − γ) A (G) + γ D (G) , where 0 ≤ γ ≤ 1 , A (G) and D (G) are the adjacency and the diagonal matrices of node degrees, respectively. In this case, the A γ matrix brings together the spectral theories of the adjacency, the Laplacian, and the signless Laplacian matrices, and many more γ adjacency-type matrices. In this paper, we obtain the A γ eigenvalues of zero divisor graphs of the integer modulo rings and the von Neumann rings. These results generalize the earlier published spectral theories of the adjacency, the Laplacian and the signless Laplacian matrices of zero divisor graphs. [ABSTRACT FROM AUTHOR]

For a finite group G and a subset X≠ 0 of G, the commuting graph, indicated by G = C(G, X), is the simple connected graph with vertex set X and two distinct vertices x and y are edge connected in G if and only if they commute in X. The Aα matrix of G is specified as Aα(G) = αD(G) + (1-α)A(G), α ∈ [0, 1], where D(G) is the diagonal matrix of vertex degrees while A(G) is the adjacency matrix of G. In this article, we investigate the Aα matrix for commuting graphs of finite groups and we also find the Aα eigenvalues of the dihedral, the semidihedral and the dicyclic groups. We determine the upper bounds for the largest Aα eigenvalue for these graphs. Consequently, we get the adjacency eigenvalues, the Laplacian eigenvalues, and the signless Laplacian eigenvalues of these graphs for particular values of α. Further, we show that these graphs are Laplacian integral. [ABSTRACT FROM AUTHOR]

Let G be a graph with n vertices and m edges. The minimum edge dominating energy is defined as the sum of the absolute values of eigenvalues of the minimum edge dominating matrix of the graph G. In this paper, some lower and upper bounds for the minimum edge dominating energy of graph G are established. [ABSTRACT FROM AUTHOR]

We consider signed graphs Ġ whose spectra are comprised of exactly two (distinct) eigenvalues that differ only in sign, abbreviated to signed graphs with two symmetric eigenvalues. We obtain some relationships between such signed graphs and their star complements. Our results include structural examinations and constructions of infinite families of signed graphs with two symmetric eigenvalues. We also determine the bases for the eigenspaces of the eigenvalues of Ġ in terms of the eigenspaces of its star complement. In particular, we consider the case in which a star complement has two symmetric eigenvalues, as well. [ABSTRACT FROM AUTHOR]

If A(G) and D(G) are respectively the adjacency matrix and the diagonal matrix of vertex degrees of a connected graph G, the generalized adjacency matrix Aα(G) is defined as Aα(G) = α D(G) + (1 - α) A(G), where 0 ≤ α ≤ 1. The Aα (or generalized) spectral radius λ(Aα(G)) (or simply λα) is the largest eigenvalue of Aα(G). In this paper, we show that λα ≤ α Δ + (1 - α)√ 2m ( 1 - 1/ω), where m, Δ and ω = ω(G) are respectively the size, the largest degree and the clique number of G. Further, if G has order n, then we show that ... where di and mi are respectively the degree and the average 2-degree of the vertex Vi. [ABSTRACT FROM AUTHOR]

The nullity of a graph G is the multiplicity of zero as an eigenvalue of its adjacency matrix. An assignment of weights to the vertices of a graph, that satisfies a zero sum condition over the neighbors of each vertex, and uses maximum number of independent variables is denoted by a high zero sum weighting of the graph. This applicable tool is used to determine the nullity of the graph. Two types of graphs are defined, and the change of their nullities is studied, namely, the graph G+ab constructed from G by adding a new vertex ab which is joint to all neighbors of both vertices a and b of G, and G•ab which is obtained from G+ab by removing both vertices a and b. [ABSTRACT FROM AUTHOR]

Abstract Let (G,∗) be a finite group and S={x∈G|x≠x −1} be a subset of G containing its non-self invertible elements. The inverse graph of G denoted by Γ(G) is a graph whose set of vertices coincides with G such that two distinct vertices x and y are adjacent if either x∗y∈S or y∗x∈S. In this paper, we study the energy of the dihedral and symmetric groups, we show that if G is a finite non-abelian group with exactly two non-self invertible elements, then the associated inverse graph Γ(G) is never a complete bipartite graph. Furthermore, we establish the isomorphism between the inverse graphs of a subgroup D p of the dihedral group D n of order 2p and subgroup S k of the symmetric groups S n of order k! such that 2 p = n ! ( p , n , k ≥ 3 and p , n , k ∈ ℤ + ) . $2p = n!~(p,n,k \geq 3~\text {and}~p,n,k \in \mathbb {Z}^{+}).$

Three eigenvalue-based topological molecular descriptors are compared using several datasets of alkanes. Two of them are well-known and frequently employed in various QSPR/QSAR investigations, and third-one is a newly derived whose predictive potential is yet to be proven. The relations among them are found and discussed. Structural parameters that govern these relations are identified and the corresponding formulas based on multiple linear regression have been obtained. It has been shown that all three investigated indices are encoding almost the same structural information of a molecule. They differ only by the extent of the sensitivity on a structural branching of a molecule and on the number of non-bonding molecular orbitals.

Gain graphs are graphs where the edges are given some orientation and labeled with the elements (called gains) from a group so that gains are inverted when we reverse the direction of the edges. Generalizing the notion of gain graphs, skew gain graphs have the property that the gain of a reversed edge is the image of edge gain under an anti-involution. In this paper, we study two different types, Laplacian and g-Laplacian matrices for a skew gain graph where the skew gains are taken from the multiplicative group Fx of a field F of characteristic zero. Defining incidence matrix, we also prove the matrix tree theorem for skew gain graphs in the case of the g-Laplacian matrix. [ABSTRACT FROM AUTHOR]

For 0 ≤ α ≤ 1, Nikiforov proposed to study the spectral properties of the family of matrices Aα(G) = αD(G)+(1 - α)A(G) of a graph G, where D(G) is the degree diagonal matrix and A(G) is the adjacency matrix of G. The α-spectral radius of G is the largest eigenvalue of Aα(G). For a graph with two pendant paths at a vertex or at two adjacent vertices, we prove results concerning the behavior of the α-spectral radius under relocation of a pendant edge in a pendant path. We give upper bounds for the α-spectral radius for unicyclic graphs G with maximum degree ∆ ≥ 2, connected irregular graphs with given maximum degree and some other graph parameters, and graphs with given domination number, respectively. We determine the unique tree with the second largest α-spectral radius among trees, and the unique tree with the largest α-spectral radius among trees with given diameter. We also determine the unique graphs so that the difference between the maximum degree and the α-spectral radius is maximum among trees, unicyclic graphs and non-bipartite graphs, respectively. [ABSTRACT FROM AUTHOR]

The location of the nontrivial poles of a generalized zeta function is derived from the spectrum of Ramanujan graphs and bounds are established for irregular graphs. The existence of a similarity transformation of the diagonal matrix given by a specified set of eigenvalues to an adjacency matrix of a graph is proven, and the method yields a set of finite graphs with eigenvalues determined approximately by a finite subset of the poles of the Ihara zeta function.

A Hamiltonian graph G is said to be hyper-Hamiltonian when G − v is Hamiltonian for any vertex v of G. In this paper, sufficient conditions for a graph to be hyper-Hamiltonian based on different parameters, such as degree and number of edges, are presented. Furthermore, other sufficient conditions for hyper-Hamiltonicity are obtained from spectral parameters, such as the spectral radii of the adjacency matrix, the signless Laplacian matrix and the distance matrix. Results on hyper-Hamiltonicity of a threshold graph through the eigenvalues of its Laplacian matrix are also presented. [ABSTRACT FROM AUTHOR]

In this paper our focus is on regular signed graphs with exactly 3 (distinct) eigenvalues. We establish certain basic results; for example, we show that they are walk-regular. We also give some constructions and determine all the signed graphs with 3 eigenvalues, under the constraint that they are either signed line graphs or have vertex degree 3. We also report our result of computer search on those with at most 10 vertices. [ABSTRACT FROM AUTHOR]

In this paper, we discuss various connections between the smallest eigenvalue of the adjacency matrix of a graph and its structure. There are several techniques for obtaining upper bounds on the smallest eigenvalue, and some of them are based on Rayleigh quotients, Cauchy interlacing using induced subgraphs, and Haemers interlacing with vertex partitions and quotient matrices. In this paper, we are interested in obtaining lower bounds for the smallest eigenvalue. Motivated by results on line graphs and generalized line graphs, we show how graph decompositions can be used to obtain such lower bounds. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to highlight the role played by the anti-regular graph within the class of threshold graphs. Using the fact that every threshold graph contains a maximal anti-regular graph, we show that some known results, and new ones, on the spectral properties of threshold graphs can be deduced from (i) the known results on the eigenvalues of anti-regular graphs, (ii) the subgraph structure of threshold graphs, and (iii) eigenvalue interlacing. In particular, we prove a strengthened version of the recently proved fact that no threshold graph contains an eigenvalue in the interval Ω = [ − 1 − 2 2 , − 1 + 2 2 ] , except possibly the trivial eigenvalues −1 and/or 0, determine the inertia of a threshold graph, and give partial results on a conjecture regarding the optimality of the non-trivial eigenvalues of an anti-regular graph within the class of threshold graphs. [ABSTRACT FROM AUTHOR]

Three eigenvalue-based topological molecular descriptors are compared using several datasets of alkanes. Two of them are well-known and frequently employed in various QSPR/QSAR investigations, and third-one is a newly derived whose predictive potential is yet to be proven. The relations among them are found and discussed. Structural parameters that govern these relations are identified and the corresponding formulas based on multiple linear regression have been obtained. It has been shown that all three investigated indices are encoding almost the same structural information of a molecule. They differ only by the extent of the sensitivity on a structural branching of a molecule and on the number of non-bonding molecular orbitals. [ABSTRACT FROM AUTHOR]

In this paper we consider a concept of strong regularity of signed graphs—a generalization of strong regularity of graphs. We establish certain structural and spectral properties of such signed graphs and determine or characterize those belonging to specified classes. Theoretical results are followed by examples and discussions. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with n vertices v 1 , ... , v n and m edges. Let A (G) = [ a i j ] n × n be the adjacency matrix of G , that is a i j = 1 if v i and v j are adjacent, and a i j = 0 , otherwise. Let λ 1 , ... , λ n be the eigenvalues of A (G). The energy of G , denoted by E (G) , is defined as | λ 1 | + ⋯ + | λ n |. It is well known that 2 m ≤ E (G) ≤ 2 m n. In this paper we improve the latter lower bound and prove that if all eigenvalues of G are non-zero, then E (G) ≥ 2 | λ 1 λ n | | λ 1 | + | λ n | 2 m n , where | λ 1 | ≥ ⋯ ≥ | λ n |. We show that the equality holds if and only if G = n 2 K 2 or G = p K β + 1 ⋃ q T β + 1 , where p and q are some non-negative integers and β ≥ 2 and T β + 1 is the graph K β + 1 , β + 1 ∖ M , where M is a perfect matching of K β + 1 , β + 1. Finally by studying the | λ 1 λ n | | λ 1 | + | λ n | of graphs, we find some lower bounds for the energy of graphs. In particular, we obtain that if G has no eigenvalue in the interval (− 1 , 1) , then E (G) ≥ 2 m 2 n − 2 n , and the equality holds if and only if G is the complete graph K n. [ABSTRACT FROM AUTHOR]

The Gershgorin Circle Theorem is a well-known and efficient method for bounding the eigenvalues of a matrix in terms of its entries. If A is a symmetric matrix, by writing A = B + x 1 , where 1 is the matrix with unit entries, we consider the problem of choosing x to give the optimal Gershgorin bound on the eigenvalues of B , which then leads to one-sided bounds on the eigenvalues of A. We show that this x can be found by an efficient linear program (whose solution can in may cases be written in closed form), and we show that for large classes of matrices, this shifting method beats all existing piecewise linear or quadratic bounds on the eigenvalues. We also apply this shifting paradigm to some nonlinear estimators and show that under certain symmetries this also gives rise to a tractable linear program. As an application, we give a novel bound on the lowest eigenvalue of a adjacency matrix in terms of the "top two" or "bottom two" degrees of the corresponding graph, and study the efficacy of this method in obtaining sharp eigenvalue estimates for certain classes of matrices. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph with n vertices and m edges. Let W (G) = (G , w) be the weighted graph corresponding to G. Let λ 1 , λ 2 , ... , λ n be the eigenvalues of the adjacency matrix A (W (G)) of the weighted graph W (G). The energy E (W (G)) of a weighted graph W (G) is defined as the sum of absolute value of the eigenvalues of W (G). In this paper, we obtain upper bounds for the energy E (W (G)) , in terms of the sum of the squares of weights of the edges, the maximum weight, the maximum degree d 1 , the second maximum degree d 2 and the vertex covering number τ of the underlying graph G. As applications to these upper bounds we obtain some upper bounds for the energy (adjacency energy), the extended graph energy, the Randić energy and the signed energy of the connected graph G. We also obtain some new families of weighted graphs where the energy increases with increase in weights of the edges. [ABSTRACT FROM AUTHOR]

For a sequence of adjacency matrices, describing the unfolding of a network from the graph of a star, through graphs of a broom, to the graph of a link with constant vertices and edges, we show that the leading eigenvalue (the spectral radius) satisfies a simple algebraic equation. The equation allows easy numerical computation of the leading eigenvalue as well as a direct proof of its monotonicity in terms of the maximal degree of vertices. [ABSTRACT FROM AUTHOR]

Abstract Finding a diagonal matrix congruent to A − c I for constants c , where A is the adjacency matrix of a graph G allows us to quickly tell the number of eigenvalues in a given interval. If G has clique-width k and a corresponding k -expression is known, then diagonalization can be done in time O (poly (k) n) where n is the order of G. [ABSTRACT FROM AUTHOR]

Abstract In this paper we introduce a new graph matrix, named the anti-adjacency matrix or eccentricity matrix, which is constructed from the distance matrix of a graph by keeping for each row and each column only the largest distances. This matrix can be interpreted as the opposite of the adjacency matrix, which is instead constructed from the distance matrix of a graph by keeping for each row and each column only the distances equal to 1. We show that the eccentricity matrix of trees is irreducible, and we investigate the relations between the eigenvalues of the adjacency and eccentricity matrices. Finally, we give some applications of this new matrix in terms of molecular descriptors, and we conclude by proposing some further research problems. [ABSTRACT FROM AUTHOR]

We study the eigenvalues of the unique connected anti-regular graph A n . Using Chebyshev polynomials of the second kind, we obtain a trigonometric equation whose roots are the eigenvalues and perform elementary analysis to obtain an almost complete characterization of the eigenvalues. In particular, we show that the interval Ω = [ − 1 − 2 2 , − 1 + 2 2 ] contains only the trivial eigenvalues λ = − 1 or λ = 0 , and any closed interval strictly larger than Ω will contain eigenvalues of A n for all n sufficiently large. We also obtain bounds for the maximum and minimum eigenvalues, and for all other eigenvalues we obtain interval bounds that improve as n increases. Moreover, our approach reveals a more complete picture of the bipartite character of the eigenvalues of A n , namely, as n increases the eigenvalues are (approximately) symmetric about the number − 1 2 . We also obtain an asymptotic distribution of the eigenvalues as n → ∞ . Finally, the relationship between the eigenvalues of A n and the eigenvalues of a general threshold graph is discussed. [ABSTRACT FROM AUTHOR]

Connected planar graphs are of interest to a variety of scholars. Being able to simulate a database of such graphs with selected properties would support specific types of inference for spatial analysis and other network-based disciplines. This paper presents a simple, efficient, and flexible connected planar graph generator for this purpose. It also summarizes a comparison between an empirical set of specimen graphs and their simulated counterpart set, and establishes evidence for positing a conjecture about the principal eigenvalue of connected planar graphs. Finally, it summarizes a probability assessment of the algorithm’s outcomes as well as a comparison between the new algorithm and selected existing planar graph generators. [ABSTRACT FROM AUTHOR]

Let G be a simple undirected graph. Let 0 ≤ α ≤ 1 . Let A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) where D ( G ) and A ( G ) are the diagonal matrix of the vertex degrees of G and the adjacency matrix of G , respectively. Let p ( G ) > 0 and q ( G ) be the number of pendant vertices and quasi-pendant vertices of G , respectively. Let m G ( α ) be the multiplicity of α as an eigenvalue of A α ( G ) . It is proved that m G ( α ) ≥ p ( G ) − q ( G ) with equality if each internal vertex is a quasi-pendant vertex. If there is at least one internal vertex which is not a quasi-pendant vertex, the equality m G ( α ) = p ( G ) − q ( G ) + m N ( α ) is determined in which m N ( α ) is the multiplicity of α as an eigenvalue of the matrix N . This matrix is obtained from A α ( G ) taking the entries corresponding to the internal vertices which are non quasi-pendant vertices. These results are applied to search for the multiplicity of α as an eigenvalue of A α ( G ) when G is a path, a caterpillar, a circular caterpillar, a generalized Bethe tree or a Bethe tree. For the Bethe tree case, a simple formula for the nullity is given. [ABSTRACT FROM AUTHOR]

We derive an inequality that includes the largest eigenvalue of the adjacency matrix and walks of an arbitrary length of a signed graph. We also consider certain particular cases. [ABSTRACT FROM AUTHOR]

For an undirected simple graph G , the line graph L ( G ) is the graph whose vertex set is in one-to-one correspondence with the edge set of G where two vertices are adjacent if their corresponding edges in G have a common vertex. The energy E ( G ) is the sum of the absolute values of the eigenvalues of G . The vertex connectivity κ ( G ) is referred as the minimum number of vertices whose deletion disconnects G . The positive inertia ν + ( G ) corresponds to the number of positive eigenvalues of G . Finally, the matching number β ( G ) is the maximum number of independent edges of G . In this paper, we derive a sharp upper bound for the energy of the line graph of a graph G on n vertices having a vertex connectivity less than or equal to k . In addition, we obtain upper bounds on E ( G ) in terms of the edge connectivity, the inertia and the matching number of G . Moreover, a new family of hyperenergetic graphs is obtained. [ABSTRACT FROM AUTHOR]

In a certain class of graphs, a graph is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum. A connected graph containing two or three cycles is called a bicyclic graph if its number of edges is equal to its number of vertices plus one. In this paper, we characterize the minimizing graph among all the connected graphs that belong to a class of graphs whose complements are bicyclic with two cycles. [ABSTRACT FROM AUTHOR]

We consider only simple graphs. A graph G is said to be nonsingular if its adjacency matrix A ( G ) is nonsingular. The inverse of a nonsingular graph G is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A ( G ) via a diagonal matrix of ±1s. An invertible graph G is said to be a self-inverse graph if G is isomorphic to its inverse. Let H be the class of connected bipartite graphs with unique perfect matchings. We consider the problem of characterizing the graphs in H which are self-inverse graphs. In this article, we answer this problem for the class of unicyclic graphs. The study of the strong reciprocal eigenvalue property is closely related to the study of graphs which are isomorphic to their inverse graphs. A nonsingular graph G is said to satisfy the property (SR) if the reciprocal of each eigenvalue of the adjacency matrix A ( G ) is also an eigenvalue of A ( G ) and they both have the same multiplicities. In this article, we show that if a unicyclic graph G in H has property (SR), then G is invertible and the inverse graph of G is unicyclic. As an application, we show that a noncorona unicyclic graph in H with property (SR) can have one of the five specified structures. Finally, our discussions lead to the following problem. Does there exist a unicyclic graph G ∈ H which has property (SR) but G is not self-inverse? [ABSTRACT FROM AUTHOR]

We consider only simple graphs. Consider connected bipartite graphs with unique perfect matchings such that the graph obtained by contracting all matching edges is also bipartite. On the class H g of such graphs G the equivalence of the following statements are known. i) The reciprocal of the spectral radius of the adjacency matrix A ( G ) is the least positive eigenvalue of the adjacency matrix. ii) The graph is isomorphic to its inverse, where the inverse of a graph G is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A ( G ) via a diagonal matrix of ±1s. iii) The graph has the reciprocal eigenvalue property, that is, the reciprocal of each eigenvalue of the adjacency matrix A ( G ) is also an eigenvalue of A ( G ) . iv) The graph has the strong reciprocal eigenvalue property, that is, the reciprocal of each eigenvalue of the adjacency matrix A ( G ) is also an eigenvalue of A ( G ) and they both have the same multiplicities. v) The graph is a corona graph, that is, it is obtained by taking a bipartite graph and then by inserting a new adjacent vertex of degree one at each vertex. It is known that the statements iii) and iv) are not equivalent, if we allow nonbipartite graphs. However, the equivalence of these two is not yet known for the class of bipartite graphs with unique perfect matchings, where we relax the condition of bipartiteness of the contracted graph. In this article, we establish the equivalence of the first four statements for a class larger than H g . We then supply a constructive structural description of those graphs. [ABSTRACT FROM AUTHOR]

Graphs G and H are called cospectral if they have the same characteristic polynomial. If eigenvalues are integral, then corresponding graphs are called integral graph. In this article we introduce a construction to produce pairs of cospectral integral regular graphs. Generalizing the construction of G4(a, b) and G5(a, b) due to Wang and Sun, we define graphs G4(G,H) and G5(G,H) and show that they are cospectral integral regular when G is an integral q- regular graph of order m and H is an integral q-regular graph of order (b -- 2)m for some integer b ≥3. [ABSTRACT FROM AUTHOR]