Search

This contribution gives an extensive study on spectra of mixed graphs via its Hermitian adjacency matrix of the second kind { ($N$-matrix for short)} introduced by Mohar \cite{0001}. This matrix is indexed by the vertices of the mixed graph, and the entry corresponding to an arc from $u$ to $v$ is equal to the sixth root of unity $\omega=\frac{1+{\bf i}\sqrt{3}}{2}$ (and its symmetric entry is $\bar{\omega}=\frac{1-{\bf i}\sqrt{3}}{2}$); the entry corresponding to an undirected edge is equal to 1, and 0 otherwise. The main results of this paper include the following: {equivalent} conditions for a mixed graph that shares the same spectrum of its $N$-matrix with its underlying graph are given. A sharp upper bound on the spectral radius is established and the corresponding extremal mixed graphs are identified. Operations which are called two-way and three-way switchings are discussed--they give rise to some cospectral mixed graphs. We extract all the mixed graphs whose rank of its $N$-matrix is $2$ (resp. 3). Furthermore, we show that {if $M_G$ is a connected mixed graph with rank $2,$ then $M_G$ is switching equivalent to each connected mixed graph to which it is cospectral}. However, this does not hold for some connected mixed graphs with rank $3$. We identify all mixed graphs whose eigenvalues of its $N$-matrix lie in the range $(-\alpha,\, \alpha)$ for $\alpha\in\left\{\sqrt{2},\,\sqrt{3},\,2\right\}$., Comment: 31pages,15figures

We describe how eight copies of the Best code can be imbedded in the binary Hamming graph of length 10 in such a way that they form part of a partition design π1. We study those isometries of the binary Hamming graph which stabilize π1. A partition design π2, coarser than π1, will be the subject of the second part of this work. Let M be the adjacency matrix of π2. We will show that M is extreme in some sense. Namely, π2 has the following interesting property: π2 is the unique partition design with adjacency matrix M.

Let G be a graph without loops and multiple edges. If V(G) = (V[in1]), V2, …, vn, we define the adjacency matrix of G to be the n × n (0, I)-matrix A (G) = (aij), where aij = 1 if vivjϵ E (G) and aij = 0 otherwise. G is said to be singular if the matrix A(G) is singular. Reduction procedures which will decrease the amount of computation needed to obtain the determinant of the adjacency matrices of some graphs are introduced. One of these reduction procedures is used in proving the singularity of square planar grid Pn × Pn.

Recently, several results bounding above the diameter and/or the mean distance of a graph from its eigenvalues have been presented. They use the eigenvalues of either the adjacency or the Laplacian matrix of the graph. The main object of this paper is to compare both methods. As expected, they are equivalent for regular graphs. However, the situation is different for nonregular graphs: While no method has a definite advantage when bounding above the diameter, the use of the Laplacian matrix seems better when dealing with the mean distance. This last statement follows from improved bounds on the mean distance obtained in the paper.

We present a sequence of graphs G n for which χ(G n ) ⩾ Ω( rk (A(G n )) 4 3 ) .

“Which graphs are determined by their spectrum (DS for short)?” is a fundamental question in spectral graph theory. It is generally very hard to show a given graph to be DS and few results about DS graphs are known in literature. In this paper, we consider the above problem in the context of the generalized Q -spectrum. A graph G is said to be determined by the generalized Q -spectrum (DGQS for short) if, for any graph H , H and G have the same Q -spectrum and so do their complements imply that H is isomorphic to G . We give a simple arithmetic condition for a graph being DGQS. More precisely, let G be a graph with adjacency matrix A and degree diagonal matrix D . Let Q = A + D be the signless Laplacian matrix of G , and W Q ( G ) = [ e , Q e , … , Q n − 1 e ] ( e is the all-ones vector) be the Q -walk matrix. We show that if det W Q ( G ) 2 ⌊ 3 n − 2 2 ⌋ (which is always an integer) is odd and square-free, then G is DGQS.

Let G be a simple connected graph with n vertices and m edges. The spectral radius ρ ( G ) of G is the largest eigenvalue of its adjacency matrix. In this paper, we firstly consider the effect on the spectral radius of a graph by removing a vertex, and then as an application of the result, we obtain a new sharp upper bound of ρ ( G ) which improves some known bounds: If ( k − 2 ) ( k − 3 ) 2 ≤ m − n ≤ k ( k − 3 ) 2 , where k ( 3 ≤ k ≤ n ) is an integer, then ρ ( G ) ≤ 2 m − n − k + 5 2 + 2 m − 2 n + 9 4 . The equality holds if and only if G is a complete graph K n or K 4 − e , where K 4 − e is the graph obtained from K 4 by deleting some edge e .

It is well-known that the paths are determined by the spectrum of the adjacency matrix. For digraphs, every digraph whose underlying graph is a tree is cospectral to its underlying graph with respect to the Hermitian adjacency matrix ( H -cospectral). Thus every (simple) digraph whose underlying graph is isomorphic to P n is H -cospectral to P n . Interestingly, there are others. This paper finds digraphs that are H -cospectral with the path graph P n and whose underlying graphs are nonisomorphic, when n is odd, and finds that such graphs do not exist when n is even. In order to prove this result, all digraphs whose Hermitian spectral radius is smaller than 2 are determined.

A signed graph is a pair Γ = ( G , σ ) , where x = ( V ( G ) , E ( G ) ) is a graph and σ : E ( G ) → { + 1 , − 1 } is the sign function on the edges of G . For any α ∈ [ 0 , 1 ] we consider the matrix A α ( Γ ) = α D ( G ) + ( 1 − α ) A ( Γ ) , where D ( G ) is the diagonal matrix of the vertex degrees of G , and A ( Γ ) is the adjacency matrix of Γ . Let m A α ( Γ ) ( α ) be the multiplicity of α as an A α ( Γ ) -eigenvalue, and let G have p ( G ) pendant vertices, q ( G ) quasi-pendant vertices, and no components isomorphic to K 2 . It is proved that m A α ( Γ ) ( α ) = p ( G ) − q ( G ) whenever all internal vertices are quasi-pendant. If this is not the case, it turns out that m A α ( Γ ) ( α ) = p ( G ) − q ( G ) + m N α ( Γ ) ( α ) , where m N ( Γ ) ( α ) denotes the multiplicity of α as an eigenvalue of the matrix N α ( Γ ) obtained from A α ( Γ ) taking the entries corresponding to the internal vertices which are not quasi-pendant. Such results allow to state a formula for the multiplicity of 1 as an eigenvalue of the Laplacian matrix L ( Γ ) = D ( G ) − A ( Γ ) . Furthermore, it is detected a class G of signed graphs whose nullity – i.e. the multiplicity of 0 as an A ( Γ ) -eigenvalue – does not depend on the chosen signature. The class G contains, among others, all signed trees and all signed lollipop graphs. It also turns out that for signed graphs belonging to a subclass G ′ ⊂ G the multiplicity of 1 as Laplacian eigenvalue does not depend on the chosen signatures. Such subclass contains trees and circular caterpillars.

We study functions defined on the vertices of the Hamming graphs $H(n,q)$. The adjacency matrix of $H(n,q)$ has $n+1$ distinct eigenvalues $n(q-1)-q\cdot i$ with corresponding eigenspaces $U_{i}(n,q)$ for $0\leq i\leq n$. In this work, we consider the problem of finding the minimum possible support (the number of nonzeros) of functions belonging to a direct sum $U_i(n,q)\oplus U_{i+1}(n,q)\oplus\ldots\oplus U_j(n,q)$ for $0\leq i\leq j\leq n$. For the case $n\geq i+j$ and $q\geq 3$ we find the minimum cardinality of the support of such functions and obtain a characterization of functions with the minimum cardinality of the support. In the case $n \frac{n}{2}$,$\,q\ge 5$., Comment: 17 pages, 3 figures

Let G be a graph with n vertices, and let A ( G ) and D ( G ) denote respectively the adjacency matrix and the degree matrix of G . Define A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) for any real α ∈ [ 0 , 1 ] . The collection of eigenvalues of A α ( G ) together with multiplicities are called the A α -spectrum of G . A graph G is said to be determined by its A α -spectrum if all graphs having the same A α -spectrum as G are isomorphic to G . We first prove that some graphs are determined by their A α -spectra for 0 ≤ α 1 , including the complete graph K n , the union of cycles, the complement of the union of cycles, the union of copies of K 2 and K 1 , the complement of the union of copies of K 2 and K 1 , the path P n , and the complement of P n . Setting α = 0 or 1 2 , those graphs are determined by A - or Q -spectra. Secondly, when G is regular, we show that G is determined by its A α -spectrum if and only if the join G ∨ K m ( m ≥ 2 ) is determined by its A α -spectrum for 1 2 α 1 . Furthermore, we also show that the join K m ∨ P n ( m , n ≥ 2 ) is determined by its A α -spectrum for 1 2 α 1 . In the end, we pose some related open problems for future study.

Let G be a finite, connected graph. An arithmetical structure on G is a pair of positive integer vectors d , r such that ( diag ( d ) − A ) r = 0 , where A is the adjacency matrix of G . We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the torsion part of the cokernels of the matrices ( diag ( d ) − A ) ). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients 2 n − 1 n − 1 , and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.

It is well known that spectral Tur\'{a}n type problem is one of the most classical {problems} in graph theory. In this paper, we consider the spectral Tur\'{a}n type problem. Let $G$ be a graph and let $\mathcal{G}$ be a set of graphs, we say $G$ is \textit{$\mathcal{G}$-free} if $G$ does not contain any element of $\mathcal{G}$ as a subgraph. Denote by $\lambda_1$ and $\lambda_2$ the largest and the second largest eigenvalues of the adjacency matrix $A(G)$ of $G,$ respectively. In this paper we focus on the characterization of graphs without short odd cycles according to the adjacency eigenvalues of the graphs. Firstly, an upper bound on $\lambda_1^{2k}+\lambda_2^{2k}$ of $n$-vertex $\{C_3,C_5,\ldots,C_{2k+1}\}$-free graphs is established, where $k$ is a positive integer. All the corresponding extremal graphs are identified. Secondly, a sufficient condition for non-bipartite graphs containing an odd cycle of length at most $2k+1$ in terms of its spectral radius is given. At last, we characterize the unique graph having the maximum spectral radius among the set of $n$-vertex non-bipartite graphs with odd girth at least $2k+3,$ which solves an open problem proposed by Lin, Ning and Wu [Eigenvalues and triangles in graphs, Combin. Probab. Comput. 30 (2) (2021) 258-270]., Comment: 15 pages. It is accepted by Discrete Mathematics

The eccentricity matrix e ( G ) of a graph G is constructed from the distance matrix of G by keeping only the largest distances for each row and each column. This matrix can be interpreted as the opposite of the adjacency matrix obtained from the distance matrix by keeping only the distances equal to 1 for each row and each column. The e-eigenvalues of a graph G are those of its eccentricity matrix e ( G ) . Wang et al. [24] proposed the problem of determining the maximum e-spectral radius of trees with given order. In this paper, we consider the above problem of n-vertex trees with given diameter. The maximum e-spectral radius of n-vertex trees with fixed odd diameter is obtained, and the corresponding extremal trees are also determined. Recently, Wei et al. [22] determined all connected graphs on n vertices of maximum degree less than n − 1 , whose least eccentricity eigenvalues are in [ − 2 2 , − 2 ] . Denote by S n the star on n vertices. For tree T with order n ≥ 3 , it [22] was proved that e n ( T ) ≤ − 2 with equality if and only if T ≅ S n . According to the above results, the trees of order n ≥ 3 with least e-eigenvalues in [ − 2 2 , 0 ) are only S n . Motivated by [22] , we determine the trees with least e-eigenvalues in [ − 2 − 13 , − 2 2 ) .

In this paper, we study 24 possibilities of directed strongly regular graphs with adjacency matrix of rank 6, our proof is based on two effective algorithms. At last, we get 4 families of directed strongly regular graphs with realizable parameter sets, exclude 20 families of directed strongly regular graphs with feasible parameter sets; partially solve the classification problem of directed strongly regular graphs with adjacency matrix of rank 6.

The transition matrix of a graph G corresponding to the adjacency matrix A is defined by H ( t ) ≔ exp − i t A , where t ∈ R . The graph is said to exhibit pretty good state transfer between a pair of vertices u and v if there exists a sequence t k of real numbers such that lim k → ∞ H ( t k ) e u = γ e v , where γ is a complex number of unit modulus. We present a class of circulant graphs admitting pretty good state transfer. Also we find some circulant graphs not exhibiting pretty good state transfer. This generalizes several pre-existing results on circulant graphs admitting pretty good state transfer.

The index of a signed graph is the largest eigenvalue of its adjacency matrix. For positive integers n and m ≤ n 2 / 4 , we determine the maximum index of complete signed graphs with n vertices and m negative edges and characterize the signed graphs achieving this maximum. This settles (the corrected version of) a conjecture by Koledin and Stanic (2017).

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 ] , Nikiforov defined the matrix A α ( G ) as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . In this paper, we study the k th largest eigenvalue of A α -matrix of graphs, where 1 ≤ k ≤ n . We present several upper and lower bounds on the k th largest eigenvalue of A α -matrix and characterize the extremal graphs corresponding to some of these obtained bounds. As applications, some bounds we obtained can generalize some known results on adjacency matrix and signless Laplacian matrix of graphs. Finally, we solve a problem proposed by Nikiforov (2017).

Let α ≠ β be two positive scalars. A Euclidean representation of a simple graph G in R r is a mapping of the nodes of G into points in R r such that the squared Euclidean distance between any two distinct points is α if the corresponding nodes are adjacent and β otherwise. A Euclidean representation is spherical if the points lie on an ( r − 1 ) -sphere, and is J -spherical if this sphere has radius 1 and α = 2 β . Let dim E ( G ) , dim S ( G ) and dim J ( G ) denote, respectively, the smallest dimension r for which graph G admits a Euclidean, spherical and J -spherical representation. In this paper, we extend and simplify the results of Roy (2010) and Nozaki and Shinohara (2012) by deriving exact simple formulas for dim E ( G ) and dim S ( G ) in terms of the eigenvalues of V T A V , where A is the adjacency matrix of G and V is the matrix whose columns form an orthonormal basis for the orthogonal complement of the vector of all 1’s. We also extend and simplify the results of Musin (2018) by deriving explicit formulas for determining the J -spherical representation of G and for determining dim J ( G ) in terms of the largest eigenvalue of A , the adjacency matrix of the complement graph G . As a by-product, we obtain several other related results and in particular we answer a question raised by Musin in Musin (2018).

The adjacency spectrum of a graph , which is denoted by Spec(), is the multiset of eigenvalues of its adjacency matrix. We say that two graphs and are cospectral if Spec()=Spec(). In this paper for each prime number p, p23, we construct a large family of cospectral non-isomorphic Cayley graphs over the dihedral group of order 2p.

Let Γ be a simple undirected graph on a finite vertex set and let A be its adjacency matrix. Then Γ is singular if A is singular. The problem of characterizing singular graphs is easy to state but very difficult to resolve in any generality. In this paper we investigate the singularity of graphs for which the dihedral group acts transitively on vertices as a group of automorphisms.

The rank of a graph is defined to be the rank 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. A reduced graph G is said to be maximal if any reduced graph containing G as a proper induced subgraph has a higher rank. The main intent of this paper is to present some results on maximal graphs. First, we introduce a characterization of maximal trees (a reduced tree is a maximal tree if it is not a proper subtree of a reduced tree with the same rank). Next, we give a near-complete characterization of maximal ‘generalized friendship graphs.’ Finally, we present an enumeration of all maximal graphs with ranks 8 and 9. The ranks up to 7 were already done by Lepovic (1990), Ellingham (1993), and Lazic (2010).

Let G be a complex unit gain graph which is obtained from an undirected graph Γ by assigning a complex unit φ ( v i v j ) to each oriented edge v i v j such that φ ( v i v j ) φ ( v j v i ) = 1 for all edges. The Laplacian matrix of G is defined as L ( G ) = D ( G ) − A ( G ) , where D ( G ) is the degree diagonal matrix of Γ and A ( G ) = ( a i j ) has a i j = φ ( v i v j ) if v i is adjacent to v j and a i j = 0 otherwise. In this paper, we provide a combinatorial description of det ( L ( G ) ) that generalizes that for the determinant of the Laplacian matrix of a signed graph.

An interval matrix is the adjacency matrix of an interval digraph or equivalently the biadjacency matrix of an interval bigraph. In this paper we investigate the forbidden substructures of an interval bigraph. Our method finds hitherto existing forbidden substructures for interval matrices, and via a more concise statement, as well as a new example showing that these substructures are not exhaustive.

A graph is called integral if all eigenvalues of its adjacency matrix consist entirely of integers. We prove that for a given nullity more than 1, there are only finitely many integral trees. It is also shown that integral trees with nullity 2 and 3 are unique., 14 pages, 4 figures; This is a through revision of the first version including the correction of Lemma 13 (of first version) which was not correct as stated. We thank a referee for pointing out this mistake

An odd [ 1 , b ] -factor of a graph G is a spanning subgraph H such that for each vertex v ∈ V ( G ) , d H ( v ) is odd and 1 ≤ d H ( v ) ≤ b . Let λ 3 ( G ) be the third largest eigenvalue of the adjacency matrix of G . For positive integers r ≥ 3 and even n , Lu et al. (2010) proved a lower bound for λ 3 ( G ) in an n -vertex r -regular graph G to guarantee the existence of an odd [ 1 , b ] -factor in G . In this paper, we improve the bound; it is sharp for every r .

The eccentricity matrix e ( G ) of a graph G is constructed from the distance matrix of G by keeping only the largest distances for each row and each column. This matrix can be interpreted as the opposite of the adjacency matrix obtained from the distance matrix by keeping only the distances equal to 1 for each row and each column. In this paper we focus on the eccentricity matrix of graphs. Let T be an n -vertex tree and let e n ( T ) be the least e -eigenvalue of T . On the one hand, we determine the n -vertex trees with the minimum e -spectral radius. On the other hand, for n ⩾ 3 , we show that e n ( T ) ⩽ − 2 with equality if and only if T is a star. As a consequence, we solve two conjectures proposed by Wang et al. (2018). Furthermore, we identify all the trees with given order and diameter having the minimum e -spectral radius . Finally, we determine all the n -vertex connected graphs whose maximum degrees are less than n − 1 and least e -eigenvalues are in [ − 2 2 , − 2 ] .

The work of Wang et al. (2020) established an upper bound on the multiplicity of a real number as an adjacency eigenvalue of an undirected simple graph G according to the dimension of its cycle space and the number of its pendants. The work of Cardoso et al. (2018) studied the multiplicity of α as an eigenvalue of α D ( G ) + ( 1 − α ) A ( G ) , α ∈ [ 0 , 1 ) , where D ( G ) is the diagonal matrix of degrees and A ( G ) is the adjacency matrix of G , which was ported to signed graphs by the work of Belardo et al. (2019). Here, on the one hand, we consider both the Wang–Wei–Jin-type and Cardoso–Pasten–Rojo-type routines developed for graphs to the level of mixed graphs and complex unit gain graphs. On the other hand, we consider Belardo–Brunetti–Ciampella-type routines developed for signed graphs to the level of mixed graphs and complex unit gain graphs. We show that, with suitable adaption, such routines can be successfully ported to mixed graphs and complex unit gain graphs. By these obtained results in the current paper, the corresponding results for undirected graphs, oriented graphs and signed graphs are deduced.

The transition matrix of a graph Γ with the adjacency matrix A is defined by H ( t ) ≔ exp ( − i t A ) , where t ∈ R and i = − 1 . The graph is said to admit a pretty good state transfer between a pair of vertices u and v if for any e > 0 , there is a time t such that | e v t H ( t ) e u | ≥ 1 − e . The state transfer is perfect if the above inequality holds for e = 0 . Perfect (pretty good) state transfer on graphs has received extensive attention recently due to their significant applications in quantum information processing and quantum computations. In this paper, we study pretty good state transfer on Cayley graphs over dihedral groups. We find that if n is a power of 2, then Cay ( D n , S ) exhibits pretty good state transfer for some subset S in D n , some concrete constructions are provided. We also show that this is basically the only case for a non-integral Cayley graph Cay ( D n , S ) to have PGST.

We examine the binary code from the row span of an adjacency matrix of the Paley graph of order q 2 , where q is a prime power such that q 2 ≡ 1 ( mod 8 ) . We show that the code and its dual are respectively [ q 2 , q 2 − 1 2 , q + 1 ] 2 and [ q 2 , q 2 + 1 2 , q ] 2 codes. We obtain spanning sets of minimum-weight vectors for these codes, and in the case of q a prime we show that the code can be used for partial permutation decoding using a certain information set.

A tournament of order n is usually considered as an orientation of the complete graph K n . In this note, we consider a more general definition of a tournament that we call a C -tournament, where C is the adjacency matrix of a multigraph G , and a C -tournament is an orientation of G . The score vector of a C -tournament is the vector of outdegrees of its vertices. In 1965 Hakimi obtained necessary and sufficient conditions for the existence of a C -tournament with a prescribed score vector R and gave an algorithm to construct such a C -tournament which required, however, some backtracking. We give a simpler and more transparent proof of Hakimi's theorem, and then provide a direct construction of such a C -tournament which works even for weighted graphs.

It is known that two regular graphs of minimum degree 2 are cospectral if and only if they have the same Ihara zeta function. In this article we present other families of graphs for which the spectrum of the adjacency matrix and the Ihara zeta function determine each other.

Let G be a simple graph of order n with t triangle(s). Also let λ 1 ( G ) , λ 2 ( G ) , … , λ n ( G ) be the eigenvalues of the adjacency matrix of graph G . X. Yong [X. Yong, On the distribution of eigenvalues of a simple undirected graph, Linear Algebra Appl. 295 (1999) 73–80] conjectured that (i) G is complete if and only if det ( A ( G ) ) = ( − 1 ) n − 1 ( n − 1 ) and also (ii) G is complete if and only if | det ( A ( G ) ) | = n − 1 . Here we disprove this conjecture by a counter example. Wang et al. [J.F. Wang, F. Belardo, Q.X. Huang, B. Borovicanin, On the two largest Q-eigenvalues of graphs, Discrete Math. 310 (2010) 2858–2866] conjectured that friendship graph F t 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 ecc ( G ) of a graph G is the mean value of eccentricities of all vertices of G . Moreover, we mention three conjectures, obtained by the system AutoGraphiX, about the average eccentricity ( ecc ( G ) ) , girth ( g ( G ) ) and the spectral radius ( λ 1 ( G ) ) 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.

Let G be a simple graph of order n and let P G ∗ (λ)=|λI−A ∗ | denote the Seidel characteristic polynomial, where A ∗ is the Seidel adjacency matrix of G. Let P ∗ (G) be the collection of Seidel characteristic polynomials P G i ∗ (λ) of vertex deleted subgraphs G⧹i (i=1,2,…,n) . If G and H are two switching equivalent graphs, using the Seidel formal product and the Seidel angle matrices, we prove that P ∗ (G)= P ∗ (H) . Further, let PG(λ)=|λI−A| be the characteristic polynomial of the graph G, where A is the adjacency matrix of G. Let S be any subset of the vertex set V(G) and let GS be the graph obtained from the graph G by adding a new vertex x which is adjacent exactly to the vertices from S. In particular, if G is a regular graph of degree r, we prove that P G S (λ)= (−1) n+1 λ+r+1 (λ− r )P G S ( λ )+ (λ+r+1−|S|) 2 λ+r+1 P G ( λ ) , where G S denotes the complement of G S , r =(n−1)−r and λ =−λ−1 . Using the last relation we prove that the polynomial reconstruction conjecture is true for all graphs GS for which G is regular.

Let A be a Hermitian matrix whose graph is G (i.e. there is an edge between the vertices i and j in G if and only if the (i,j) entry of A is non-zero). Let @l be an eigenvalue of A with multiplicity m"A(@l). An edge e=ij is said to be Parter (resp., neutral, downer) for @l,A if m"A(@l)-m"A"-"e(@l) is negative (resp., 0, positive ), where A-e is the matrix resulting from making the (i,j) and (j,i) entries of A zero. For a tree T with adjacency matrix A a subset S of the edge set of G is called an edge star set for an eigenvalue @l of A, if |S|=m"A(@l) and A-S has no eigenvalue @l. In this paper the existence of downer edges and edge star sets for non-zero eigenvalues of the adjacency matrix of a tree is proved. We prove that neutral edges always exist for eigenvalues of multiplicity more than 1. It is also proved that an edge e=uv is a downer edge for @l,A if and only if u and v are both downer vertices for @l,A; and e=uv is a neutral edge if u and v are neutral vertices. Among other results, it is shown that any edge star set for each eigenvalue of a tree is a matching.

We consider a bipartite distance-regular graph @C with vertex set X, diameter D>=4, and valency k>=3. Let C^X denote the vector space over C consisting of column vectors with rows indexed by X and entries in C. For z@?X, let z@? denote the vector in C^X with a 1 in the z^t^h row and 0 in all other rows. For 0@?i@?D, let @C"i(z) denote the set of vertices in X that are distance i from z. Fix x,y@?X with distance @?(x,y)=2. For 0@?i,j@?D, we define w"i"j=@?z@?, where the sum is over all vertices z@?@C"i(x)@?@C"j(y). Define a parameter @D in terms of the intersection numbers by @D=(b"1-1)(c"3-1)-(c"2-1)p"2"2^2. For 2@?i@?D-2 we define vectors w"i"i^+=@?|@C"1(x)@?@C"1(y)@?@C"i"-"1(z)|z@?, where the sum is over all vertices z@?@C"i(x)@?@C"i(y). We define W=span{w"i"j,w"h"h^+|0@?i,j@?D,2@?h@?D-2}. In [M. MacLean, An inequality involving two eigenvalues of a bipartite distance-regular graph, Discrete Math. 225 (2000) 193-216], MacLean defined what it means for @C to be taut. Assume D is odd. We show @C is taut if and only if @D 0 and the subspace W is invariant under multiplication by the adjacency matrix.

The generalized power of a simple graph G , denoted by G k , s , is obtained from G by blowing up each vertex into an s -set and each edge into a k -set, where 1 ? s ? k 2 . When s < k 2 , G k , s is always odd-bipartite. It is known that G k , k 2 is non-odd-bipartite if and only if G is non-bipartite, and G k , k 2 has the same adjacency (respectively, signless Laplacian) spectral radius as G . In this paper, we prove that, regardless of multiplicities, the H -spectrum of A ( G k , k 2 ) (respectively, Q ( G k , k 2 ) ) consists of all eigenvalues of the adjacency matrices (respectively, the signless Laplacian matrices) of the connected induced subgraphs (respectively, modified induced subgraphs) of G . As a corollary, G k , k 2 has the same least adjacency (respectively, least signless Laplacian) H -eigenvalue as G . We also discuss the limit points of the least adjacency H -eigenvalues of hypergraphs, and construct a sequence of non-odd-bipartite hypergraphs whose least adjacency H -eigenvalues converge to - 2 + 5 .

In this paper we give a criterion for the adjacency matrix of a Cayley digraph to be normal in terms of the Cayley subset S. It is shown with the use of this result that the adjacency matrix of every Cayley digraph on a finite group G is normal iff G is either abelian or has the form Q8×Z2n for some non-negative integer n, where Q8 is the quaternion group and Z2n is the abelian group of order 2n and exponent 2.

Suppose that f is a (⩽ k )-to-1 function from a vertex set of a graph G onto a vertex set of a graph H . We ask when f extends to a continuous (⩽ k )-to-1 map from G onto H . In an earlier paper, the authors answered this question, for the case that k is odd, with local conditions only on the adjacency matrix for H and the inverse adjacency matrix for G . For the present case, when k is even, global conditions are needed and we capture these conditions in a matrix C that exists iff f extends and that describes how the subtle part of the extension must be constructed.

Graham and Pollak proved that one needs at least n − 1 complete bipartite subgraphs (bicliques) to partition the edge set of the complete graph on n vertices. In this paper, we study the generalizations of their result to coverings of graphs with specified multiplicities and to complete uniform hypergraphs. We also discuss the recently disproved Alon–Saks–Seymour Conjecture (which proposed a generalization of the previous result of Graham and Pollak) and compute the exact values of the ranks of the adjacency matrices of the known counterexamples to the Alon–Saks–Seymour Conjecture. The rank of the adjacency matrix of a graph G is related to important problems in computational complexity and provides a non-trivial lower bound for the minimum number of bicliques that partition the edge set of G .

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.

Let D be a digraph with vertex set V ( D ) and A be the adjacency matrix of D . The largest eigenvalue of A , denoted by ? ( D ) , is called the spectral radius of the digraph D . In this paper, we establish some sharp upper or lower bounds for digraphs with some given graph parameters, such as clique number, girth, and vertex connectivity, and characterize the corresponding extremal graphs. In addition, we give the exact value of the spectral radii of those digraphs.

The energy of a graph is the sum of the absolute values of the eigenvalues of its adjacency matrix. The edge grafting operation on a graph is a kind of edge moving between two vertices of the graph. In this paper, we introduce two new edge grafting operations and show how the graph energy changes under these edge grafting operations. Let G ( n ) be the set of all unicyclic graphs with n vertices. Using these edge grafting operations and the Coulson integral formula for the energy of a monic real polynomial, we characterize the unicyclic graphs with the first to the seventh minimal energies in G ( n ) ( n ≥ 11 ) .