BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Write ρ(G) for the spectral radius of a graph G and Sn,r for the join Kr∨Kn−r. Let n>r≥2 and G be a Kr+1-saturated graph of order n. Recently Kim, Kim, Kostochka, and O determined exactly the minimum value of ρ(G) for r=2, and found an asymptotically tight bound on ρ(G) for r≥3. They also conjectured that ρ(G)>ρ(Sn,r−1), unless G=Sn,r−1. In this note their conjecture is proved.
It is well known that a graph is bipartite if and only if the spectrum of its adjacency matrix is symmetric. In the present paper, this assertion is dissected into three separate matrix results of wider scope, which are extended also to hypermatrices. To this end the concept of bipartiteness is generalized by a new monotone property of cubical hypermatrices, called odd-colorable matrices. It is shown that a nonnegative symmetric r-matrix A has a symmetric spectrum if and only if r is even and A is odd-colorable. This result also solves a problem of Pearson and Zhang about hypergraphs with symmetric spectrum and disproves a conjecture of Zhou, Sun, Wang, and Bu. Separately, similar results are obtained for the H-spectram of hypermatrices.
Let G be a graph of order n and size m, and let mck(G) be the maximum size of a k-cut of G. It is shown that mck(G)≤kk−1(m−2μmin(G)n), where μmin(G) is the smallest eigenvalue of the adjacency matrix of G. An infinite class of graphs forcing equality in this bound is constructed.
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% \textit{-spectral theory}, and the study of the signless Laplacian--the Q\textit{-spectral theory}. During the years many similarities and differences between these two theories have been established. 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 by Aα(G):=αD(G)+(1−α)A(G), 0≤α≤1. This study sheds new light on A(G) and Q(G), and yields some surprises, in particular, a novel spectral Turán theorem. A number of challenging open problems are discussed.
The energy of a graph is the sum of the absolute values of the eigenvalues of its adjacency matrix. This note is about the energy of regular graphs. It is shown that graphs that are close to regular can be made regular with a negligible change of the energy. Also a k-regular graph can be extended to a k-regular graph of a slightly larger order with almost the same energy. As an application, it is shown that for every sufficiently large n, there exists a regular graph G of order n whose energy ∥G∥∗ satisfies ∥G∥∗>21n3/2−n13/10. Several infinite families of graphs with maximal or submaximal energy are given, and the energy of almost all regular graphs is determined.
The trace norm ∥G∥∗ of a graph G is the sum of its singular values, i.e., the absolute values of its eigenvalues. The norm ∥G∥∗ has been intensively studied under the name of graph energy, a concept introduced by Gutman in 1978. This note studies the maximum trace norm of r-partite graphs, which raises some unusual problems for r>2. It is shown that, if G is an r-partite graph of order n, then ∥G∥∗<2n3/21−1/r+(1−1/r)n. For some special r this bound is tight: e.g., if r is the order of a symmetric conference matrix, then, for infinitely many n, there is a graph G of order n with ∥G∥∗>2n3/21−1/r−(1−1/r)n.
Let G be a graph of order n and let q(G) be that largest eigenvalue of the signless Laplacian of G. In this note it is shown that if k>1 and q(G)>=n+2k-2, then G contains cycles of length l whenever 2<l<2k+3. This bound is asymptotically tight. It implies an asymptotic solution to a recent conjecture about the maximum q(G) of a graph G with no cycle of a specified length.
Let G be a k-degenerate graph of order n. It is well-known that G has no more edges than Sn,k, the join of a complete graph of order k and an independent set of order n−k. In this note it is shown that Sn,k is extremal for some spectral parameters of G as well. More precisely, letting μ(H) and q(H) denote the largest eigenvalues of the adjacency matrix and the signless Laplacian of a graph H, the inequalities μ(G)<μ(Sn,k) and q(G)<q(Sn,k) hold, unless G=Sn,k. The latter inequality is deduced from the following general bound, which improves some previous bounds on q(G): If G is a graph of order n, with m edges, with maximum degree Δ and minimum degree δ, then q(G)≤min{2Δ,21(Δ+2δ−1+(Δ+2δ−1)2+16m−8(n−1+Δ)δ)}. Equality holds if and only if G is regular or G has a component of order Δ+1 in which every vertex is of degree δ or Δ, and all other components are δ-regular.
We characterize the r-graph with maximal p-spectral radius among the k-partite r-graphs of order n, and the 3-graph with maximal p-spectral radius among the k-chromatic 3-graphs of order n.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.