Search

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

Let (G, w) be a weighted graph with the adjacency matrix A. The group inverse of (G, w), denoted by (G # , w #) is the weighted graph with the weight w # (v i v j) of an edge v i v j in G # is defined as the ijth entry of A # , the group inverse of A. We study the group inverse of singular weighted trees. It is shown that if (T, w) is a singular weighted tree, then (T # , w #) is again a weighted tree if and only if (T, w) is a star tree, which in turn holds if and only if (T # , w #) is graph isomorphic to (T, w). A new class T w of weighted trees is introduced and studied here. It is shown that the group inverse of the adjacency matrix of a positively weighted tree in T w is signature similar to a non-negative matrix. [ABSTRACT FROM AUTHOR]

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

We introduce a graph attached to mutually orthogonal Sudoku Latin squares. The spectra of the graphs obtained from finite fields are explicitly determined. As a corollary, we then use the eigenvalues to distinguish non-isomorphic Sudoku Latin squares. [ABSTRACT FROM AUTHOR]

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

For a simple graph G, the ABC-index is a degree based topological index and is defined as where dv is the degree of the vertex υ in G. Recently, the Laplacian ABC-matrix was introduced in [22] is defined by where is the diagonal matrix of ABC-degrees and Ã(G) is the ABC-matrix of G: The eigenvalues of the matrix are called the Laplacian ABC-eigenvalues of G. In the article, we consider the problem of characterization of connected graphs having exactly three distinct Laplacian ABC-eigenvalues. We solve this problem for bipartite graphs, multipartite graphs, unicyclic graphs, regular graphs and prove the non-existence of such graphs with diameter greater than 2. We introduce the concept of trace norm of the matrix called the Laplacian ABC-energy of G. We obtain some upper and lower bounds for the Laplacian ABC-energy and characterize the extremal graphs which attain these bounds. [ABSTRACT FROM AUTHOR]

We formalize the notion of a sedentary vertex and present a relaxation of the concept of a sedentary family of graphs introduced by Godsil (Linear Algebra Appl 614:356–375, 2021. https://doi.org/10.1016/j.laa.2020.08.027). We provide sufficient conditions for a given vertex in a graph to exhibit sedentariness. We also show that a vertex with at least two twins (vertices that share the same neighbours) is sedentary. We prove that there are infinitely many graphs containing strongly cospectral vertices that are sedentary, which reveals that, even though strong cospectrality is a necessary condition for pretty good state transfer, there are strongly cospectral vertices which resist high probability state transfer to other vertices. Moreover, we derive results about sedentariness in products of graphs which allow us to construct new sedentary families, such as Cartesian powers of complete graphs and stars. [ABSTRACT FROM AUTHOR]

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

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

In this article, we undertake the problem of finding the first four trees on a fixed number of vertices with the maximum smallest positive eigenvalue. Let T n , d denote the class of trees on n vertices with diameter d. First, we obtain the bounds on the smallest positive eigenvalue of trees in T n , d for d = 2 , 3 , 4 and then upper bounds on the smallest positive eigenvalue of trees are obtained in general class of all trees on n vertices. Finally, the first four trees on n vertices with the maximum, second maximum, third maximum and fourth maximum smallest positive eigenvalue are characterized. [ABSTRACT FROM AUTHOR]

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

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

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

An oriented graph is called singular or nonsingular according as its adjacency matrix is singular or nonsingular. In this note, by a new approach, we determine the singularity of oriented quasi-trees. The main results of Chen et al. ['Singularity of oriented graphs from several classes', Bull. Aust. Math. Soc. 102 (1) (2020), 7–14] follow as corollaries. Furthermore, we give a necessary condition for an oriented bipartite graph to be nonsingular. By applying this condition, we characterise nonsingular oriented bipartite graphs $B_{m,n}$ when $\min \{m,n\}\leq 3$. [ABSTRACT FROM AUTHOR]

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

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

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

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

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

The least eigenvalue of a connected graph is the least eigenvalue of its adjacency matrix. We characterize the connected graphs of order n and size n + k (5 ⩽ k ⩽ 8 and n ⩾ k + 5) with the minimal least eigenvalue. [ABSTRACT FROM AUTHOR]

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

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

In this paper we develop the concept of energy of a vertex introduced in Arizmendi and Juarez-Romero (2018). We derive basic inequalities, continuity properties, give examples and extend the definition to locally finite graphs. [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]

In this manuscript we continue the investigations related to the wreath product of graphs by considering the compound graph of a clique with a circuit. This product shows nice combinatorial and algebraic properties which permit with reasonable effort to compute some topological indices and the (adjacency) spectrum. [ABSTRACT FROM AUTHOR]

An oriented hypergraph is an oriented incidence structure that generalizes and unifies graph and hypergraph theoretic results by examining its locally signed graphic substructure. In this paper we obtain a combinatorial characterization of the coefficients of the characteristic polynomials of oriented hypergraphic Laplacian and adjacency matrices via a signed hypergraphic generalization of basic figures of graphs. Additionally, we provide bounds on the determinant and permanent of the Laplacian matrix, characterize the oriented hypergraphs in which the upper bound is sharp, and demonstrate that the lower bound is never achieved. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) , V = { 1 , 2 , … , n } , be a simple connected graph with n vertices, m edges, and sequence of vertex degrees d 1  ≥  d 2  ≥ ⋅⋅⋅ ≥  d n  > 0, d i = d ( i ) . A large number of vertex–degree-based topological indices is of the form T I = T I ( G ) = ∑ i ∼ j F ( d i , d j ) , where F is pertinently chosen function with the property F ( x , y ) = F ( y , x ) . To each of such topological indices a corresponding adjacency matrix A = ( a i j ) , of order n  ×  n , can be associated. The trace of matrix A is denoted as t r ( A ) . For F ( d i , d j ) = 2 d i d j d i + d j , the geometric–arithmetic topological index, GA 1 , is obtained. Upper and lower bounds for GA 1 in terms of t r ( A 2 ) are determined. Also, we generalize a number of results reported in the literature and obtain some new bounds for the indices of the form TI . [ABSTRACT FROM AUTHOR]

The characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix. Finding efficient algorithms for computing characteristic polynomial of graphs is an active area of research and for some graph classes, like threshold graphs, there exist very fast algorithms which exploit combinatorial structure of the graphs. In this paper, we put forward some novel ideas based on divisor technique to obtain fast algorithms for computing the characteristic polynomial of threshold and chain graphs. [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]

Let G be a simple graph and A ( G ) be the adjacency matrix of G . The eigenvalues of A ( G ) are referred to as the eigenvalues of G . In this paper, we characterize the graphs with the minimal least eigenvalue among all graphs whose complements are connected and have only two pendent vertices. [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]

We give counterexamples to a result in F. Esser and F. Harary [2, Theorem 3] asserting that two nonisomorphic complete r -partite graphs with the same number of vertices have different spectral radii. We then derive some results on invariant factors and apply them to obtain relationship between the parameters of integral complete multipartite graphs and their integer eigenvalues. Necessary conditions for complete multipartite graphs to be integral are obtained. [ABSTRACT FROM AUTHOR]

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 A α -characteristic polynomial of G is defined to be det ( x I n − A α ( G ) ) = ∑ j c α j ( G ) x n − j , where det ( ⁎ ) denotes the determinant of ⁎, and I n is the identity matrix of size n . The A α -spectrum of G consists of all roots of the A α -characteristic polynomial 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 . In this paper, we first formulate the first four coefficients c α 0 ( G ) , c α 1 ( G ) , c α 2 ( G ) and c α 3 ( G ) of the A α -characteristic polynomial of G . And then, we observe that A α -spectra are much efficient for us to distinguish graphs, by enumerating the A α -characteristic polynomials for all graphs on at most 10 vertices. To verify this observation, we characterize some graphs determined by their A α -spectra. [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]

A signed graph G σ consists of an underlying graph G and a sign function σ , which assigns each edge uv of G a sign σ ( u v ) , either positive or negative. The adjacency matrix of G σ is defined as A ( G σ ) = ( a u , v σ ) with a u , v σ = σ ( u v ) a u , v , where a u , v = 1 if u , v ∈ V ( G ) are adjacent, and a u , v = 0 otherwise. The positive inertia index of G σ , written as p ( G σ ) , is defined to be the number of positive eigenvalues of A ( G σ ) . Recently, Yu et al. (2016) [12] characterized the signed graphs G σ with pendant vertices such that p ( G σ ) = 2 . In this paper, we extend the above work to a more general case, characterizing the signed graphs G σ with cut points whose positive inertia index is 2. [ABSTRACT FROM AUTHOR]

Let G [ F, V k , H v ] be the graph with k pockets, where F is a simple graph of order n  ≥ 1, V k = { v 1 , … , v k } is a subset of the vertex set of F and H v is a simple graph of order m  ≥ 2, v is a specified vertex of H v . Also let G [ F, E k , H uv ] be the graph with k edge-pockets, where F is a simple graph of order n  ≥ 2, E k = { e 1 , … , e k } is a subset of the edge set of F and H uv is a simple graph of order m  ≥ 3, uv is a specified edge of H uv such that H u v − u is isomorphic to H u v − v . In this paper, we obtain some results describing the signless Laplacian spectra of G [ F, V k , H v ] and G [ F, E k , H uv ] in terms of the signless Laplacian spectra of F, H v and F, H uv , respectively. In addition, we also give some results describing the adjacency spectrum of G [ F, V k , H v ] in terms of the adjacency spectra of F, H v . Finally, as many applications of these results, we construct infinitely many pairs of signless Laplacian (resp. adjacency) cospectral graphs. [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]

Kautz digraphs K ( d , ℓ ) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related with these, the cyclic Kautz C K ( d , ℓ ) and the subKautz s K ( d , 2 ) digraphs were recently introduced by Böhmová, Huemer and the author. In this paper we propose a new method to obtain the complete spectra of subKautz s K ( d , 2 ) and cyclic Kautz C K ( d , 3 ) digraphs, for all d ≥ 3 , through the Hoffman–McAndrew polynomial and regular partitions. This approach can be useful to find the spectra of other families of digraphs with high regularity. [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]

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]

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

Given a digraph G, we propose a new method to find the recurrence equation for the number of vertices [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 . For every real α ∈ [ 0 , 1 ] , write A α ( G ) for the matrix A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . Let α 0 ( G ) be the smallest α for which A α ( G ) is positive semidefinite. It is known that α 0 ( G ) ≤ 1 / 2 . The main results of this paper are: (1) if G is d -regular then α 0 = − λ min ( A ( G ) ) d − λ min ( A ( G ) ) , where λ min ( A ( G ) ) is the smallest eigenvalue of A ( G ) ; (2) G contains a bipartite component if and only if α 0 ( G ) = 1 / 2 ; (3) if G is r -colorable, then α 0 ( G ) ≥ 1 / r . [ABSTRACT FROM AUTHOR]

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

The energy of a graph G , denoted by E ( G ) , is defined as the sum of the absolute values of all eigenvalues of G . In this paper we present some new lower bounds for energy of non-singular graphs, connected non-singular graphs and connected unicyclic non-singular graphs in terms of number of vertices, number of edges, maximum degree and Zagreb indices. [ABSTRACT FROM AUTHOR]

Let Z n be the ring of residue classes modulo n , and let Z n ⁎ be the group of its units. 90 years ago, Brauer obtained a formula for the number of representations of c ∈ Z n as the sum of k units. Recently, Yang and Tang (2015) [6] gave a formula for the number of solutions of the equation x 1 2 + x 2 2 = c with x 1 , x 2 ∈ Z n ⁎ . In this paper, we generalize this result. We find an explicit formula for the number of solutions of the equation x 1 2 + ⋯ + x k 2 = c with x 1 , … , x k ∈ Z n ⁎ . [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]