Search

The energy of a simple graph G , E ( G ) , is the sum of the absolute values of the eigenvalues of its adjacency matrix. The energy of line graph and the signless Laplacian energy of graph G are denoted by E ( L G ) ( L G is the line graph of G ) and LE + ( G ) , respectively. In this paper we obtain a relation between E ( L G ) and LE + ( G ) of graph G . From this relation we characterize all the graphs satisfying E ( L G ) = LE + ( G ) + 4 m n − 4 . We also present a relation between E ( G ) and E ( L G ) . Moreover, we give an upper bound on E ( L G ) of graph G and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

Graphs G and H are called cospectral if they have the same characteristic polynomial, equivalently, if they have the same eigenvalues considering multiplicities. In this article we introduce a construction to produce pairs of cospectral regular graphs. We also investigate conditions under which the graphs are integral. [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 signed graph, where G is the underlying simple graph and σ : E ( G ) → { + , − } is the sign function on the edges of G . In this paper we consider the spectral characterization problem extended to the adjacency matrix and Laplacian matrix of signed graphs. After giving some basic results, we study the spectral determination of signed lollipop graphs, and we show that any signed lollipop graph is determined by the spectrum of its Laplacian matrix. [ABSTRACT FROM AUTHOR]

In this paper we determine the unique graph with minimal least eigenvalue (of the adjacency matrix) within the set of connected graphs of fixed order n and size m , whenever m = ⌈ n 2 ⌉ ⌊ n 2 ⌋ + a , where a is a fixed integral constant in [ 1 , ⌈ n 2 ⌉ − 1 ] . [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]

A graph in a certain graph class is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum among all graphs in that class. Bell et al. have identified a subclass within the connected graphs of order n and size m in which minimizing graphs belong (the complements of such graphs are either disconnected or contain a clique of size n/2 ). In this paper we discuss the minimizing graphs of a special class of graphs of order n whose complements are connected and contains exactly one cycle (namely the class Ucn of graphs whose complements are unicyclic), and characterize the unique minimizing graph in Ucn when n ≥ 20. [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A, and let H(t)=exp(itA). For an eigenvalue μ of A with multiplicity k, a star set for μ in G is a vertex set X of G such that |X|=k and the induced subgraph G-X does not have μ as an eigenvalue. G is said to have perfect state transfer from the vertex u to the vertex v if there is a time τ such that |H(τ)u,v|=1. The unitary operator H(t) has important applications in the transfer of quantum information. In this paper, we give an expression of H(t). For a star set X of graph G, perfect state transfer does not occur between any two vertices in X. We also give some results for the existence of perfect state transfer in a 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: The Randić index R of a graph G is defined as the sum of over all edges of G, where denotes the degree of a vertex in G. is the largest eigenvalue of the signless Laplacian matrix of G, where D is the diagonal matrix with degrees of the vertices on the main diagonal and A is the adjacency matrix of G. Hansen and Lucas [18] conjectured (1) and equality holds for and (2) with equality if and only if for and for , respectively. In this paper, we prove the conjecture (1) and obtain a result very close to the conjecture (2). Moreover, we give some results relating harmonic index and the largest eigenvalue of the adjacency matrix. [Copyright &y& Elsevier]

Abstract: We calculate the Smith normal form of the adjacency matrix of each of the following graphs or their complements (or both): complete graph, cycle graph, square of the cycle, power graph of the cycle, distance matrix graph of cycle, Andrásfai graph, Doob graph, cocktail party graph, crown graph, prism graph, Möbius ladder. The proofs operate by finding the abelianization of a cyclically presented group whose relation matrix is column equivalent to the required adjacency matrix. [Copyright &y& Elsevier]

Abstract: This paper studies the problem of estimating the spectral radius of trees with the given number of vertices and maximum degree. We obtain the new upper bounds on the spectral radius of the trees, and the results are the best upper bounds expressed by the number of vertices and maximum degree, at present. Let be a tree on n vertices with maximum degree Δ, where . Denote by the spectral radius of T. We prove that [(1)] if , then , and equality holds if and only if T is an almost completely full-degree tree of 3 levels; [(2)] if , then , and equality holds if and only if T is a completely full-degree tree of 3 levels; [(3)] if , then , where . [Copyright &y& Elsevier]

Abstract: We derive some structural and spectral properties of regular bipartite graphs with three distinct non-negative eigenvalues. Next, we consider the relations between these graphs and two-class partially balanced incomplete block designs, and we present a number of situations when the graphs we consider are in fact the incidence graphs of those designs. As a consequence, we give a several constructions of connected regular bipartite graphs with six distinct eigenvalues, and we also determine all such graphs with degree 3, and all such graphs on at most 20 vertices. [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: Let be a simple graph of order with triangle(s). Also let be the eigenvalues of the adjacency matrix of graph . X. Yong [X. Yong, On the distribution of eigenvalues of a simple undirected graph, Linear Algebra Appl. 295 (1999) 73–80] conjectured that (i) is complete if and only if and also (ii) is complete if and only if . Here we disprove this conjecture by a counter example. Wang et al. [J.F. Wang, F. Belardo, Q.X. Huang, B. Borovićanin, On the two largest Q-eigenvalues of graphs, Discrete Math. 310 (2010) 2858–2866] conjectured that friendship graph is determined by its adjacency spectrum. Here we prove this conjecture. The eccentricity of a vertex is the maximum distance from it to another vertex and the average eccentricity of a graph is the mean value of eccentricities of all vertices of . Moreover, we mention three conjectures, obtained by the system AutoGraphiX, about the average eccentricity , girth and the spectral radius of graphs (see Aouchiche (2006) [1], available online at http://www.gerad.ca/~agx/). We give a proof of one conjecture and disprove two conjectures by counter examples. [Copyright &y& Elsevier]

Abstract: The rank of a graph is that of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced trees as well as bipartite graphs with a given rank and characterize those graphs achieving the maximum order. [Copyright &y& Elsevier]

Abstract: We determine all trees whose second largest eigenvalue does not exceed . Next, we consider two classes of bipartite graphs, regular and semiregular, with small number of distinct eigenvalues. For all graphs considered we determine those whose second largest eigenvalue is equal to . Some additional results are also given. [Copyright &y& Elsevier]

Abstract: Let be two simple connected graphs. Denote the corona and the edge corona of by and , respectively. In this paper, we first introduce a new invariant, the -coronal of a graph matrix , where the matrix is associated with a graph in a prescribed way. Then it is used to compute the signless Laplacian spectrum of and in terms of the signless Laplacian spectrum of and . In addition, the spectrum of are also given in terms of the spectrum of and . Finally, as an application of these results, we construct many pairs of nonisomorphic signless Laplacian cospectral graphs. [Copyright &y& Elsevier]

Abstract: A -graph is a graph consisting of two cycles and with just a vertex in common. Fan and Luo in Theorem 4.4 alleged that a -graph is determined by its adjacency spectrum if it contains no cycle . However, according to Theorem 6.3 we find that the result in Theorem 4.4 is not completely correct. In this paper, we prove that is DAS if and only if , and has a unique cospectral mate if . [Copyright &y& Elsevier]

Abstract: We give a new characterization of skew Hadamard matrices of order n in terms of spectral data for tournaments of order . [Copyright &y& Elsevier]

Abstract: A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree. For let be a generalized Bethe tree of levels and let such that (1) the edges of connecting vertices at consecutive levels have the same weight, and (2) for , each set of children of at the level defines a clique in which the edges have weight For let be the graph obtained from and the cliques at the levels for all Let be the graph obtained from the graphs joined at their respective roots. We give a complete characterization of the eigenvalues, including their multiplicities, of the Laplacian, signless Laplacian and adjacency matrices of the graph . Finally, we characterize the normalized Laplacian eigenvalues when is an unweighted graph. [Copyright &y& Elsevier]

Abstract: The rank of a graph G is defined to be the rank of its adjacency matrix. In this paper, we consider the following problem: what is the structure of a connected graph G with rank 5? or equivalently, what is the structure of a connected n-vertex graph G whose adjacency matrix has nullity ? In this paper, we completely characterize connected graphs G whose adjacency matrix has rank 5. [Copyright &y& Elsevier]

Abstract: Suppose that is the graph obtained by taking the box product of a path of length and a path of length . Let be the adjacency matrix of . In 1996, Rara showed that, if , then . We extend this result to allow and to be any positive integers, and show that [Copyright &y& Elsevier]

Abstract: Haemers et al. [W.H. Haemers, X.G. Liu, Y.P. Zhang, Spectral characterizations of lollipop graphs, Linear Algebra Appl. 428 (2008) 2415–2423] first investigated the spectral characterizations of the so called lollipop graphs with order , which is obtained by identifying a vertex of a cycle with order and a pendent vertex of a path with order . For the graphs with least eigenvalue at least , Cvetković and Lepović [D. Cvetković, M. Lepović, Cospectral graphs with least eigenvalue at least , Publ. Inst. Math., Nouv. Sér. 78(92) (2005) 51–63] introduced the discriminant and the star value of a graph, whose relations are investigated in this paper. Employing this relation and other techniques, we prove that all line graphs of lollipop graphs are determined by their adjacency spectra. [Copyright &y& Elsevier]

Abstract: The skew energy of a digraph D is defined as the sum of the singular values of its skew adjacency matrix . In this paper, we first interpret the entries of the power of the skew adjacency matrix of a digraph in terms of the number of its walks and then focus on the question posed by Adiga et al. [C. Adiga, R. Balakrishnan, Wasin So, The skew energy of a graph, Linear Algebra Appl. 432 (2010) 1825–1835] of determining all -regular connected digraphs with optimum skew energy. [Copyright &y& Elsevier]

Abstract: Let be a function. Let be the matrix defined by if for some i and j and otherwise. We describe the Jordan canonical form of the matrix in terms of the directed graph for which is the adjacency matrix. We discuss several examples including a connection with the Collatz conjecture. [Copyright &y& Elsevier]

Abstract: We characterize the eigenvalues and energy of the line graph whenever is (i) a generalized Bethe tree, (ii) a Bethe tree, (iii) a tree defined by generalized Bethe trees attached to a path, (iv) a tree defined by generalized Bethe trees having a common root, (v) a graph defined by copies of a generalized Bethe tree attached to a cycle and (vi) a graph defined by copies of a star attached to a cycle; in this case, explicit formulas for the eigenvalues and energy of are derived. [Copyright &y& Elsevier]

Abstract: Of interest here is a characterization of the undirected graphs G such that the Laplacian matrix associated with G can be diagonalized by some Hadamard matrix. Many interesting and fundamental properties are presented for such graphs along with a partial characterization of the cographs that have this property. [Copyright &y& Elsevier]

Abstract: We consider simple graphs and their adjacency matrices. In , Rara (1996) gives methods of reducing graphs which simplify the procedure of computing the determinant of their adjacency matrices. We continue this subject matter and give a general method of reducing graphs. By the use of this method we define a formula for computing the determinant of any planar grid and in particular settle the problem of their singularity. [Copyright &y& Elsevier]

The Hoffman-Singleton graph is the unique strongly regular graph with parameters (50, 7, 0, 1). A well-known hypothesis states that a distance-regular graph in which the neighborhood of each vertex is isomorphic to the Hoffman-Singleton graph has intersection array {50, 42, 1; 1, 2, 50} or {50, 42, 9; 1, 2, 42}. In the present paper, we prove this hypothesis under the assumption that a distance-regular graph is a Terwilliger graph and the graph diameter is at most 5. [ABSTRACT FROM AUTHOR]

Abstract: The rank of a graph G is defined to be the rank of its adjacency matrix. In this paper, we consider the following problem: What is the structure of a connected graph with rank 4? This question has not yet been fully answered in the literature, and only some partial results are known. In this paper we resolve this question by completely characterizing graphs G whose adjacency matrix has rank 4. [Copyright &y& Elsevier]

Abstract: The nullity of a graph is defined as the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. We investigate a class of graphs with pendant trees, and express the nullity of such graph in terms of that of its subgraphs. As an application of our results, we characterize unicyclic graphs with a given nullity. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all graphs of a fixed order and a given vertex (edge) independence number or vertex (edge) cover number, and get some bounds for the vertex (edge) independence number, vertex (edge) cover number of a graph in terms of the least eigenvalue of the graph. [Copyright &y& Elsevier]

Abstract: A Bethe tree of levels, , is a rooted tree such that the root vertex has degree , the vertices from level to have degree and the vertices at level are leaves. In this paper, we obtain a recurrence relation for the characteristic polynomial and the Laplacian characteristic polynomial of Bethe trees. As an application, we prove that there are no integral Bethe trees except for the star , and we obtain a recurrence relation for the Laplacian-energy-like invariant of Bethe trees. [Copyright &y& Elsevier]

Abstract: The spectral excess theorem provides a quasi-spectral characterization for a (regular) graph with distinct eigenvalues to be distance-regular graph, in terms of the excess (number of vertices at distance ) of each of its vertices. The original approach, due to Fiol and Garriga in 1997, was obtained by using a local approach, so giving a characterization of the so-called pseudo-distance-regularity around a vertex. In this paper we present a new simple projection method based in a global point of view, and where the mean excess plays an essential role. [Copyright &y& Elsevier]

Abstract: A semiregular tree is a tree where all non-pendant vertices have the same degree. Among all semiregular trees with fixed order and degree, a graph with minimal (adjacency/Laplacian) spectral radius is a caterpillar. Counter examples show that the result cannot be generalized to the class of trees with a given (non-constant) degree sequence. [Copyright &y& Elsevier]

This part of our work further extends our project of building a new spectral theory of graphs (based on the signless Laplacian) by some results on graph angles, by several comments and by a short survey of recent results. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we give a criterion for the adjacency matrix of a Cayley digraph to be normal in terms of the Cayley subset . It is shown with the use of this result that the adjacency matrix of every Cayley digraph on a finite group is normal iff is either abelian or has the form for some non-negative integer , where is the quaternion group and is the abelian group of order and exponent 2. [Copyright &y& Elsevier]

Abstract: We determine all nested split graphs (i.e. graphs having no induced subgraphs equal to or ) having the second largest eigenvalue less than 1 and give some data and observations regarding obtained results. [Copyright &y& Elsevier]

Abstract: In this paper, we focus on some operations of graphs and give a kind of eigenvalue interlacing in terms of the adjacency matrix, standard Laplacian, and normalized Laplacian. Also, we explore some applications of this interlacing. [Copyright &y& Elsevier]

Abstract: The spread of a graph is defined to be the difference between the largest eigenvalue and the least eigenvalue of the adjacency matrix of the graph. Let denote the set of connected unicyclic graphs of order n and girth k, and let denote the set of connected unicyclic graphs of order n. In this paper, we determine the unique graph with minimum least eigenvalue (respectively, the unique graph with maximum spread) among all graphs in . We, finally, characterize the unique graph with minimum least eigenvalue (respectively, the unique graph with maximum spread) among all graphs in . [Copyright &y& Elsevier]

Abstract: Let G be a graph of order n and rank(G) denotes the rank of its adjacency matrix. Clearly, . In this paper we characterize all graphs G such that or n +2. Also for every integer n ⩾5 and any k, 0⩽ k ⩽ n, we construct a graph G of order n, such that . [Copyright &y& Elsevier]

Abstract: Let G be a simple graph. Let and denote the largest eigenvalue of the adjacency matrix and the Laplacian matrix of G, respectively. Let denote the largest vertex degree. If G has just one cycle, thenThe equality holds if and only if . AndThe equality holds if and only if , n is even. [Copyright &y& Elsevier]

Abstract: The higher Randić index R t (G) of a simple graph G is defined aswhere δ i denotes the degree of the vertex i and i 1 i 2⋯i t+1 runs over all paths of length t in G. In [J.A. Rodríguez, A spectral approach to the Randić index, Linear Algebra Appl. 400 (2005) 339–344], the lower and upper bound on R 1(G) was determined in terms of a kind of Laplacian spectra, and the lower and upper bound on R 2(G) were done in terms of kinds of adjacency and Laplacian spectra. In this paper we characterize the graphs which achieve the upper or lower bounds of R 1(G) and R 2(G), respectively. [Copyright &y& Elsevier]

The early research on regular graphs of the French mathematician Georges Brunel (1856–1900) is discussed. Brunel developed early graph terminology and started the French “applied” approach towards graph theory. [Copyright &y& Elsevier]

Abstract: In J.F. Wang and S.N. Shu (2012) [2], the authors lost the condition that the line graph does not contain the cycle of order 4 in Lemma 3.4, which makes their main result (i.e., Theorem 3.1) of that paper not completely correct. Here, some comments are given. [Copyright &y& Elsevier]