Search

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 be a simple graph with the vertex set V = { v 1 , ... , v n } and denote by d v i the degree of the vertex v i . The modified Sombor index of G is the addition of the numbers (d v i 2 + d v j 2) − 1 / 2 over all of the edges v i v j of G. The modified Sombor matrix A M S (G) of G is the n by n matrix such that its (i , j) -entry is equal to (d v i 2 + d v j 2) − 1 / 2 when v i and v j are adjacent and 0 otherwise. The modified Sombor spectral radius of G is the largest number among all of the eigenvalues of A M S (G) . The sum of the absolute eigenvalues of A M S (G) is known as the modified Sombor energy of G. Two graphs with the same modified Sombor energy are referred to as modified Sombor equienergetic graphs. In this article, several bounds for the modified Sombor index, the modified Sombor spectral radius, and the modified Sombor energy are found, and the corresponding extremal graphs are characterized. By using computer programs (Mathematica and AutographiX), it is found that there exists only one pair of the modified Sombor equienergetic chemical graphs of an order of at most seven. It is proven that the modified Sombor energy of every regular, complete multipartite graph is 2 ; this result gives a large class of the modified Sombor equienergetic graphs. The (linear, logarithmic, and quadratic) regression analyses of the modified Sombor index and the modified Sombor energy together with their classical versions are also performed for the boiling points of the chemical graphs of an order of at most seven. [ABSTRACT FROM AUTHOR]

Biclustering algorithm is an effective tool for processing gene expression datasets. There are two kinds of data matrices, binary data and non-binary data, which are processed by biclustering method. A binary matrix is usually converted from pre-processed gene expression data, which can effectively reduce the interference from noise and abnormal data, and is then processed using a biclustering algorithm. However, biclustering algorithms of dealing with binary data have a poor balance between running time and performance. In this paper, we propose a new biclustering algorithm called the Adjacency Difference Matrix Binary Biclustering algorithm (AMBB) for dealing with binary data to address the drawback. The AMBB algorithm constructs the adjacency matrix based on the adjacency difference values, and the submatrix obtained by continuously updating the adjacency difference matrix is called a bicluster. The adjacency matrix allows for clustering of gene that undergo similar reactions under different conditions into clusters, which is important for subsequent genes analysis. Meanwhile, experiments on synthetic and real datasets visually demonstrate that the AMBB algorithm has high practicability. [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]

A mixed graph D is a graph that can be obtained from a graph by orienting some of its edges. Let α be a primitive nth root of unity, then the α−Hermitian adjacency matrix of a mixed graph is defined to be the matrix Hα = [hrs] where hrs = α if rs is an arc in D, hrs = α if sr is an arc in D, hrs = 1 if sr is a digon in D and hrs = 0 otherwise. In this paper we study the cospectrality of the Hermitian adjacency matrix of a mixed graph. [ABSTRACT FROM AUTHOR]

For a vertex v in a graph G, the open support of v under addition is the sum of degrees of all its neighbors. The open support of G under addition is the sum of open supports of all its vertices. The results for open support of graphs are deeply dependent on the structure property of the graph considered, such as its symmetry. In this paper, we generalize the concept of open support to hypergraphs. We give some examples and prove a general formula for open support of hypergraphs by using the adjacency and incidence matrices method. [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]

In an earlier paper, we have introduced the Tosha-degree of an edge in a graph without multiple edges and studied some properties. In this paper, we extend the definition of Tosha-degree of an edge in a graph in which multiple edges are allowed. Also, we introduce the concepts - zero edges in a graph, T-line graph of a multigraph, Tosha-adjacency matrix, Tosha-energy, edge- adjacency matrix and edge energy of a graph G and obtain some results. [ABSTRACT FROM AUTHOR]

Let G be a graph on n vertices and λ 1 ≥ λ 2 ≥ ... ≥ λ n its eigenvalues. The Estrada index of G is defined as E E (G) = ∑ i = 1 n e λ i . In this work, we use an increasing sequence converging to the λ 1 to obtain an increasing sequence of lower bounds for E E (G). In addition, we generalize this succession for the Estrada index of an arbitrary symmetric nonnegative matrix. [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]

Abstract The spectral radius of a graph is the largest eigenvalue of the adjacency matrix corresponding to this graph. Let G be a graph with long pendant paths. In this note, we estimate the spectral radius of G , by obtaining appropriate upper and lower bounds. As an application, the spectral radius of some k-ary trees are estimated. [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]

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]

The numerical range of a simple graph G, named F(G), is the numerical range of its adjacency matrix A(G). The main purpose of this paper is to approximate F(G). Then, using this approximation, bounds for the largest and the smallest eigenvalues of G are proposed. In fact, lower bounds for the largest eigenvalues of G are presented in terms of disjoint induced subgraphs of G and the numerical range of the square of A(G). [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For every real α ∈ [ 0 , 1 ] , write A α ( G ) for the matrix A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . This paper presents some extremal results about the spectral radius ρ α ( G ) of A α ( G ) that generalize previous results about ρ 0 ( G ) and ρ 1 / 2 ( G ) . In particular, write B p , q , r be the graph obtained from a complete graph K p by deleting an edge and attaching paths P q and P r to its ends. It is shown that if α ∈ [ 0 , 1 ) and G is a graph of order n and diameter at least k , then ρ α ( G ) ≤ ρ α ( B n − k + 2 , ⌊ k / 2 ⌋ , ⌈ k / 2 ⌉ ) , with equality holding if and only if G = B n − k + 2 , ⌊ k / 2 ⌋ , ⌈ k / 2 ⌉ . This result generalizes results of Hansen and Stevanović [5] , and Liu and Lu [7] . [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For any real α ∈ [ 0 , 1 ] , Nikiforov [3] defined the matrix A α ( G ) as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . The largest eigenvalue of A α ( G ) is called the A α -spectral radius of G . In this paper, we give three edge graft transformations on A α -spectral radius. As applications, we determine the unique graph with maximum A α -spectral radius among all connected graphs with diameter d , and determine the unique graph with minimum A α -spectral radius among all connected graphs with given clique number. In addition, some bounds on the A α -spectral radius are obtained. [ABSTRACT FROM AUTHOR]

In this paper, a tolerance representation model for generating tolerance specification schemes and corresponding tolerance zones is proposed to meet the requirement of the representation of tolerance information semantics. This model is hierarchically organized and consists of five layers. They are component, geometric feature, variational geometric constraint, tolerance specification scheme, and tolerance zone layers. The mating relations between components in the component layer, the mating relations between geometric features in the geometric feature layer, the variational geometric constraints between geometric features in the variational geometric constraint layer, the tolerance specification schemes of component in the tolerance specification scheme layer, and the tolerance zones of tolerance specification schemes in the tolerance zone layer are formally defined by one or more adjacency matrices, respectively. Based on the model, a method for generating tolerance specification schemes for component and their resultant tolerance zones is designed. This method shows how to adopt a top-down strategy to carry out tolerance specification for an arbitrary assembly designed in a CAD system. The paper also provides a practical example to illustrate how the method works. [ABSTRACT FROM AUTHOR]

In this work, we introduce balance-binomial graphs, whose entries of adjacency matrix are balance-binomial coefficients. Then we obtain some characteristic properties of the graph. [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]

We consider only connected bipartite graphs G with a unique perfect matching M . Let G w be the weighted graph obtained from G by giving weights to its edges using the positive weight function w : E ( G ) → ( 0 , ∞ ) such that w ( e ) = 1 for each e ∈ M . An unweighted graph G may be viewed as a weighted graph with the weight function w ≡ 1 . A weighted graph G w is nonsingular if its adjacency matrix A ( G w ) is nonsingular. The inverse of a nonsingular weighted graph G w is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A ( G w ) via a diagonal matrix of ±1s. By G / M we denote the graph obtained from G by contracting each edge of M to a single vertex. It is known that if G / M is bipartite, then G w is invertible for each weight function w. In this article, we consider the converse of this result and show that if G w is invertible for each w, then the graph G / M is bipartite. We also supply exact conditions under which G w is invertible for one w will force that the graph G / M is bipartite. [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]

For a (simple) graph H and non-negative integers c0, c1, . . ., cd (cd ≠ 0), p(H) = Pd ...k=0 ck · Hk is the lexicographic polynomial in H of degree d, where the sum of two graphs is their join and ck · Hk is the join of ck copies of Hk. The graph Hk is the kth power of H with respect to the lexicographic product (H0 = K1). The spectrum (if H is connected and regular) and the Laplacian spectrum (in general case) of p(H) are determined in terms of the spectrum of H and ck's. Constructions of infinite families of cospectral or integral graphs are announced. [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]

We prove a result concerning the behavior of the spectral radius of a hypergraph under relocations of edges. We determine the unique hypergraphs with maximum spectral radius among connected k -uniform hypergraphs with fixed number of pendant edges, the unique k -uniform hypertrees with respectively maximum, second maximum and third maximum spectral radius, the unique k -uniform unicyclic hypergraphs ( k -uniform linear unicyclic hypergraphs, respectively) with respectively maximum and second maximum spectral radius. We also determine the unique hypergraphs with maximum spectral radius among k -uniform unicyclic hypergraphs with given girth. [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For every real α ∈ [ 0 , 1 ] , define the matrix A α ( G ) as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . This paper gives several results about the A α -matrices of trees. In particular, it is shown that if T Δ is a tree of maximal degree Δ, then the spectral radius of A α ( T Δ ) satisfies the tight inequality ρ ( A α ( T Δ ) ) < α Δ + 2 ( 1 − α ) Δ − 1 , which implies previous bounds of Godsil, Lovász, and Stevanović. The proof is deduced from some new results about the A α -matrices of Bethe trees and generalized Bethe trees. In addition, several bounds on the spectral radius of A α of general graphs are proved, implying tight bounds for paths and Bethe trees. [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A(G), and let D(G) be the diagonal matrix of the degrees of G: The signless Laplacian Q(G) of G is defined as Q(G) := A(G) +D(G). Cvetković called the study of the adjacency matrix the A-spectral theory, and the study of the signless Laplacian-the Q-spectral theory. To track the gradual change of A(G) into Q(G), in this paper it is suggested to study the convex linear combinations Aα(G) of A(G) and D(G) defined byAα (G) := αD(G) + (1 - α )A(G) , 0 ≤ α ≤ 1. This study sheds new light on A(G) and Q(G), and yields, in particular, a novel spectral Turán theorem. A number of open problems are discussed. [ABSTRACT FROM AUTHOR]

Let H be the class of connected bipartite graphs G with a unique perfect matching M . For G ∈ H , let W G be the set of weight functions w on the edge set E ( G ) such that w ( e ) = 1 for each matching edge and w ( e ) > 0 for each nonmatching edge. Let G w denote the weighted graph with G ∈ H and w ∈ W G . The graph G w is said to satisfy the reciprocal eigenvalue property, property (R) , if 1 / λ is an eigenvalue of the adjacency matrix A ( G w ) whenever λ is an eigenvalue of A ( G w ) . Moreover, if the multiplicities of the reciprocal eigenvalues are the same, we say G w has the strong reciprocal eigenvalue property, property (SR) . Let H g = { G ∈ H | G / M is bipartite } , where G / M is the graph obtained from G by contracting each edge in M to a vertex. Recently in [12] , it was shown that if G ∈ H g , then G w has property (SR) for some w ∈ W G if and only if G w has property (SR) for each w ∈ W G if and only if G is a corona graph (obtained from another graph H by adding a new pendant vertex to each vertex of H ). Now we have the following questions. Is there a graph G ∈ H ∖ H g such that G w has property (SR) for each w ∈ W G ? Are there graphs G ∈ H ∖ H g such that G w never has property (SR), not even for one w ∈ W G ? Are there graphs G ∈ H such that G w has property (SR) for some w ∈ W G but not for all w ∈ W G ? In this article, we supply answers to these three questions. We also supply a graph class larger than H g where for any graph G , if G w has property (SR) for one w ∈ W G , then G is a corona graph. [ABSTRACT FROM AUTHOR]

Eigenvectors of large matrices (and graphs) play an essential role in combinatorics and theoretical computer science. The goal of this survey is to provide an up-to-date account on properties of eigenvectors when the matrix (or graph) is random. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V(G) = {v1,v2,..., vn}. Let A(G) be the adjacency matrix of a graph G. The rows of A(G) corresponding to a vertex v of G, denoted by s(v) is the string. The Hamming index of a graph G is the sum of the Hamming distances between all pairs of vertices of G. In this paper we obtain Hamming index generated by adjacency matrix of some thorn graphs. [ABSTRACT FROM AUTHOR]

The n -vertex graph G ( = Γ ( G ) ) with a non-singular real symmetric adjacency matrix G , having a zero diagonal and singular ( n − 1 ) × ( n − 1 ) principal submatrices is termed a NSSD, a Non-Singular graph with a Singular Deck. NSSDs arose in the study of the polynomial reconstruction problem and were later found to characterise non-singular molecular graphs that are distinct omni-conductors and ipso omni-insulators. Since both matrices G and G − 1 represent NSSDs Γ ( G ) and Γ ( G − 1 ) , the value of the nullity of a one-, two- and three-vertex deleted subgraph of G is shown to be determined by the corresponding subgraph in Γ ( G − 1 ) . Constructions of infinite subfamilies of non-NSSDs are presented. NSSDs with all two-vertex deleted subgraphs having a common value of the nullity are referred to as G -nutful graphs. We show that their minimum vertex degree is at least 4. [ABSTRACT FROM AUTHOR]

We apply matrix theory over F 2 to understand the nature of so-called “successful pressing sequences” of black-and-white vertex-colored graphs. These sequences arise in computational phylogenetics, where, by a celebrated result of Hannenhalli and Pevzner, the space of sortings-by-reversal of a signed permutation can be described by pressing sequences. In particular, we offer several alternative linear-algebraic and graph-theoretic characterizations of successful pressing sequences, describe the relation between such sequences, and provide bounds on the number of them. We also offer several open problems that arose as a result of the present work. [ABSTRACT FROM AUTHOR]

The spectral radius of a graph is the largest eigenvalue of its adjacency matrix. P. Hansen and D. Stevanović (2008) [9] determined the graphs with maximum spectral radius among all connected graphs of order n with diameter D . In this paper, we generalize this result to k -connected graphs of order n with diameter D . [ABSTRACT FROM AUTHOR]

With a nonzero rectangular ( 0 , 1 ) -matrix A we associate an undirected graph G A that corresponds to the linear transformation X ↦ A X T A . We use the generalized singular-value decomopsition of incidence matrices to count the number of connected components and the number of bipartite connected components of G A . We show that G A is connected if and only if G A has no bipartite connected component or isolated vertex. We also show that if A has no row or column of 0's, then the number of connected components is 1 2 s ( s + 1 ) and the number of bipartite connected components is 1 2 s ( s − 1 ) , where s is the number of chainable components of A , that is, the number of connected components in the undirected graph with adjacency matrix ( O A A T O ) . [ABSTRACT FROM AUTHOR]

In this paper the unique graph with maximal index (i.e. the largest eigenvalue of the adjacency matrix) is identified among all connected bipartite graphs of order n and size n + k , under the assumption that k ≥ 0 and n ≥ k + 5 . [ABSTRACT FROM AUTHOR]

Let G be a simple graph with the adjacency matrix A ( G ) . A well-known result of Cvetković and Gutman states that removing a pendant vertex and its neighbour, does not change the nullity of the graph. We generalize this theorem and some other theorems similar to it for an arbitrary eigenvalue of a graph. Also, for an arbitrary eigenvalue λ , we use a corresponding star set to delete some subgraphs and to determine the multiplicity of λ . We use star sets to find some Parter–Wiener vertices, in trees. We state our results for real symmetric matrices (and so for weighted graphs) and as a corollary we use them for simple graphs. Furthermore, we use these methods to obtain some results for λ = 0 , ± 1 . [ABSTRACT FROM AUTHOR]

Assuming a uniform random model of selecting creation sequences, we show that almost every connected threshold graph has more negative than positive eigenvalues. We show that no threshold graphs have eigenvalues in ( − 1 , 0 ) . Sequences of equienergetic graphs are given including the striking result that for all n ≥ 3 , there exist n − 1 threshold graphs of order n 2 , pairwise noncospectral, each equienergetic to K n 2 . For all n > 8 , we find an n -vertex hyperenergetic threshold graph. [ABSTRACT FROM AUTHOR]

Let G = G1 ∪ G2 be the sum of two simple graphs G1, G2 having a common edge or G = G1 ∪ e1 ∪ e2 ∪ G2 be the sum of two simple disjoint graphs G1,G2 connected by two edges e1 and e2 which form a cycle C4 inside G. We give a method of computing the determinant detA(G) of the adjacency matrix of G by reducing the calculation of the determinant to certain subgraphs of G1 and G2. To show the scope and effectiveness of our method we give some examples [ABSTRACT FROM AUTHOR]

Abstract: Let be a weighted graph. The inertia of is the triple , where , , are the numbers of the positive, negative and zero eigenvalues of the adjacency matrix of including their multiplicities, respectively. , are called the positive, negative indices of inertia of , respectively. In this paper we present a lower bound for the positive, negative indices of weighted unicyclic graphs of order n with fixed girth and characterize all weighted unicyclic graphs attaining this lower bound. Moreover, we characterize the weighted unicyclic graphs of order n with two positive, two negative and at least zero eigenvalues, respectively. [Copyright &y& Elsevier]

Abstract: Let G be a finite abelian group, let E be a subset of G, and form the Cayley (directed) graph of G with connecting set E. We explain how, for various matrices associated to this graph, the spectrum can be used to give information on the Smith normal form. This technique is applied to several interesting examples, including matrices in the Bose–Mesner algebra of the Hamming association scheme . We also recover results of Bai and Jacobson–Niedermaier–Reiner on the critical group of a Cartesian product of complete graphs. [Copyright &y& Elsevier]

Abstract: A threshold graph on n vertices is coded by a binary string of length . We obtain a formula for the inertia of (the adjacency matrix of) a threshold graph in terms of the code of the graph. It is shown that the number of negative eigenvalues of the adjacency matrix of a threshold graph is the number of ones in the code, whereas the nullity is given by the number of zeros in the code that are preceded by either a zero or a blank. A formula for the determinant of the adjacency matrix of a generalized threshold graph and the inverse, when it exists, of the adjacency matrix of a threshold graph are obtained. Results for antiregular graphs follow as special cases. [Copyright &y& Elsevier]

Abstract: We give upper and lower bounds for the spectral radius of a nonnegative matrix using its row sums and characterize the equality cases if the matrix is irreducible. Then we apply these bounds to various matrices associated with a graph, including the adjacency matrix, the signless Laplacian matrix, the distance matrix, the distance signless Laplacian matrix, and the reciprocal distance matrix. Some known results in the literature are generalized and improved. [Copyright &y& Elsevier]

Abstract: Let G be a threshold graph of order n with adjacency matrix A. We present an algorithm for constructing a diagonal matrix congruent to for any x. An application, using Sylvesterʼs Law of Inertia, can determine how many eigenvalues lie in an interval, allowing efficient approximation. We prove that eigenvalues of threshold graphs, other than 0 or −1, are simple. We give the spectrum for threshold graphs , represented by . When , has the minimum eigenvalue among threshold graphs of order n, and a formula for is given. There is one more graph if . [Copyright &y& Elsevier]

Abstract: Let be the smallest number such that the adjacency matrix of any undirected graph with vertices or more has at least nonpositive eigenvalues. We show that is well-defined and prove that the values of for are 1, 3, 6, 10, 16 respectively. In addition, we prove that for all , , in which is the Ramsey number for and , and is the triangular number. This implies new lower bounds for eigenvalues of Laplacian matrices: the largest eigenvalue is bounded from below the largest degree, which generalizes some prior results. [Copyright &y& Elsevier]

Abstract: The energy of a graph G is the sum of the singular values of its adjacency matrix. It is a graph invariant used in mathematical chemistry. The normalized incidence energy of the graph G, denoted by , is defined as the sum of the singular values of its normalized incidence matrix. We find some upper and lower bounds and determine the Coulson integral formula for . Based on the integral formula, we give a way to compare the normalized incidence energies. Moreover we show a relation between normalized incidence energy and Randić energy. [Copyright &y& Elsevier]

Abstract: For a simple graph G, let rank(G) and dnzr(G) denote respectively the rank and the number of distinct nonzero rows of the adjacency matrix A(G) of G. Equivalent conditions are given for the join of two vertex-disjoint graphs to satisfy . A new proof is provided for the known relation rank(G)=dnzr(G) for cographs G. Our approach relies on the concepts of neighborhood equivalence classes, reduced graph and reduced adjacency matrix, and also on a known result that relates the spectrum of the adjacency matrix of a graph with that of its reduced adjacency matrix as well as a new characterization of the nonsingularity of a real symmetric matrix in a special 2×2 block form. Our treatment provides ways to construct graphs G, other than cographs, that satisfy rank(G)=dnzr(G). As a side result we also show that every rational number is equal to the sum of the entries of the inverse of the adjacency matrix of a connected nonsingular graph. [Copyright &y& Elsevier]

Abstract: Let G be a simple connected graph of order n with degree sequence in non-increasing order. The spectral radius of G is the largest eigenvalue of its adjacency matrix. For each positive integer at most n, we give a sharp upper bound for by a function of which generalizes a series of previous results. [Copyright &y& Elsevier]

Abstract: The positive index of inertia of a graph G, denoted by , is the number of the positive eigenvalues of the adjacency matrix of G. In this paper, we investigate the minimal positive index of inertia among all bicyclic graphs of order n with pendant vertices, and characterize the bicyclic graphs with positive index 1 or 2 among all bicyclic graphs of order n. [Copyright &y& Elsevier]

Abstract: In this paper we introduce a new parameter for a graph called the minimum universal rank. This parameter is similar to the minimum rank of a graph. For a graph G the minimum universal rank of G is the minimum rank over all matrices of the form where A is the adjacency matrix of G, J is the all ones matrix and D is the matrix with the degrees of the vertices in the main diagonal, and are scalars. Bounds for general graphs based on known graph parameters are given, as is a formula for the minimum universal rank for regular graphs based on the multiplicity of the eigenvalues of A. The exact value of the minimum universal rank of some families of graphs are determined, including complete graphs, complete bipartite graph, paths and cycles. Bounds on the minimum universal rank of a graph obtained by deleting a single vertex are established. It is shown that the minimum universal rank is not monotone on induced subgraphs, but bounds based on certain induced subgraphs, including bounds on the union of two graphs, are given. [Copyright &y& Elsevier]

Abstract: Some graphs Γ have the following property : the configuration graph (i.e. the non–collinearity graph) of the neighbourhood geometry of Γis isomorphic to Γ. For instance, the ubiquitous Petersen graph satisfies . The purpose of this paper is to reveal repercussions of property on adjacency matrices A for Γ. This will be achieved in terms of invariance under (powers of) the following mapping Θ: denote by I and J the identity matrix and the all one matrix, respectively, both of order n = k 2+1, and define Θ(A) := (k−1)I + J−A 2. If k =3 and A is an adjacency matrix for the Petersen graph, it is well known that Θ(A)= A. In 1960, Hoffman and Singleton showed that for arbitrary k the matrix equation Θ(A)= A has only very few solutions, namely for k =2,3,7 and possibly for k =57. We prove that the property implies the existence of an integer m ⩾1 such that Θ m (A)= A. We determine a standard form for such matrices which is invariant under the action of Θ. In particular, we characterize all solutions, on A, to Θ m (A)= A for k =3 and k =4, where A is an adjacency matrix of some k–regular graph, solving a conjecture posed by the authors. [Copyright &y& Elsevier]

Abstract: The problem of identifying those simple, undirected graphs with vertices and edges that have the smallest minimum eigenvalue of the adjacency matrix is considered. Several general properties of the minimizing graphs are described. These strongly suggest bipartition, to the extent possible for the number of edges. In the bipartite case, the precise structure of the minimizing graphs is given for a number of infinite classes. [Copyright &y& Elsevier]