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
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=d−λmin(A(G))−λ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.
In 1978 Gutman introduced the energy of a graph as the sum of the absolute values of graph eigenvalues, and ever since then graph energy has been intensively studied. Since graph energy is the trace norm of the adjacency matrix, matrix norms provide a natural background for its study. Thus, this paper surveys research on matrix norms that aims to expand and advance the study of graph energy. The focus is exclusively on the Ky Fan and the Schatten norms, both generalizing and enriching the trace norm. As it turns out, the study of extremal properties of these norms leads to numerous analytic problems with deep roots in combinatorics. The survey brings to the fore the exceptional role of Hadamard matrices, conference matrices, and conference graphs in matrix norms. In addition, a vast new matrix class is studied, a relaxation of symmetric Hadamard matrices. The survey presents solutions to just a fraction of a larger body of similar problems bonding analysis to combinatorics. Thus, open problems and questions are raised to outline topics for further investigation.
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) where 0≤α≤1. 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. This bound extends previous bounds of Godsil, Lovász, and Stevanović. The proof is based on 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.
This paper presents sufficient conditions for Hamiltonian paths and cycles in graphs. Letting λ(G) denote the spectral radius of the adjacency matrix of a graph G, the main results of the paper are: (1) Let k≥1, n≥k3/2+k+4, and let G be a graph of order n, with minimum degree δ(G)≥k. If λ(G)≥n−k−1, then G has a Hamiltonian cycle, unless G=K1∨(Kn−k−1+Kk) or G=Kk∨(Kn−2k+Kk). (2) Let k≥1, n≥k3/2+k2/2+k+5, and let G be a graph of order n, with minimum degree δ(G)≥k. If λ(G)≥n−k−2, then G has a Hamiltonian path, unless G=Kk∨(Kn−2k−1+Kk+1) or G=Kn−k−1+Kk+1 In addition, it is shown that in the above statements, the bounds on n are tight within an additive term not exceeding 2.
In 1993 Hong asked what are the best bounds on the k'th largest eigenvalue λk(G) of a graph G of order n. This challenging question has never been tackled for any 2<k<n. In the present paper tight bounds are obtained for all k>2, and even tighter bounds are obtained for the k'th largest singular value λk∗(G). Some of these bounds are based on Taylor's strongly regular graphs, and other on a method of Kharaghani for constructing Hadamard matrices. The same kind of constructions are applied to other open problems, like Nordhaus-Gaddum problems of the kind: How large can λk(G)+λk(Gˉ) be? These constructions are successful also in another open question: How large can the Ky Fan norm λ1∗(G)+...+λk∗(G) be ? Ky Fan norms of graphs generalize the concept of graph energy, so this question generalizes the problem for maximum energy graphs. In the final section, several results and problems are restated for (−1,1)-matrices, which seem to provide a more natural ground for such research than graphs. Many of the results in the paper are paired with open questions and problems for further study.
This note presents a new spectral version of the graph Zarankiewicz problem: How large can be the maximum eigenvalue of the signless Laplacian of a graph of order n that does not contain a specified complete bipartite subgraph. A conjecture is stated about general complete bipartite graphs, which is proved for infinitely many cases. More precisely, it is shown that if G is a graph of order n, with no subgraph isomorphic to K2,s+1, then the largest eigenvalue q(G) of the signless Laplacian of G satisfies q(G)≤2n+2s+21(n−2s)2+8s, with equality holding if and only if G is a join of K1 and an s-regular graph of order n−1.
Let qmin(G) stand for the smallest eigenvalue of the signless Laplacian of a graph G of order n. This paper gives some results on the following extremal problem: How large can $q_\min\left( G\right) $ be if G is a graph of order n, with no complete subgraph of order r+1? It is shown that this problem is related to the well-known topic of making graphs bipartite. Using known classical results, several bounds on qmin are obtained, thus extending previous work of Brandt for regular graphs. In addition, using graph blowups, a general asymptotic result about the maximum qmin is established. As a supporting tool, the spectra of the Laplacian and the signless Laplacian of blowups of graphs are calculated.
The p-spectral radius of a graph G of order n is defined for any real number p≥1 as λ(p)(G)=max{2∑{i,j}∈E(G) xixj:x1,…,xn∈R and ∣x1∣p+⋯+∣xn∣p=1}. The most remarkable feature of λ(p) is that it seamlessly joins several other graph parameters, e.g., λ(1) is the Lagrangian, λ(2) is the spectral radius and λ(∞)/2 is the number of edges. This paper presents solutions to some extremal problems about λ(p), which are common generalizations of corresponding edge and spectral extremal problems. Let Tr(n) be the r-partite Turán graph of order n. Two of the main results in the paper are: (I) Let r≥2 and p>1. If G is a Kr+1-free graph of order n, then λ(p)(G)<λ(p)(Tr(n)), unless G=Tr(n). (II) Let r≥2 and p>1. If G is a graph of order n, with λ(p)(G)>λ(p)(Tr(n)), then G has an edge contained in at least cnr−1 cliques of order r+1, where c is a positive number depending only on p and r.
Given a connected graph G of order n and a nonnegative symmetric matrix A=[ai,j] of order n, define the function FA(G) as% FA(G)=∑1≤i<j≤ndG(i,j)ai,j, where dG(i,j) denotes the distance between the vertices i and j in G. In this note it is shown that FA(G)≤FA(P)for some path of order n. Moreover, if each row of A has at most one zero off-diagonal entry, then FA(G)<FA(P)for some path of order n, unless G itself is a path. In particular, this result implies two conjectures of Aouchiche and Hansen: - the spectral radius of the distance Laplacian of a connected graph G of order n is maximal if and only if G is a path; - the spectral radius of the distance signless Laplacian of a connected graph G of order n is maximal if and only if G is a path.
Let G be a graph of order n and let q(G) be the largest eigenvalue of the signless Laplacian of G. Let Sn,k be the graph obtained by joining each vertex of a complete graph of order k to each vertex of an independent set of order n−k; and let Sn,k+ be the graph obtained by adding an edge to Sn,k. It is shown that if k≥2, n≥400k2, and G is a graph of order n, with no cycle of length 2k+2, then q(G)<q(Sn,k+), unless G=Sn,k+. This result completes the proof of a conjecture of de Freitas, Nikiforov and Patuzzi.
Let G be a graph of order n and let μ1(G)≥⋯≥μn(G) be the eigenvalues of its adjacency matrix. This note studies eigenvalue problems of Nordhaus-Gaddum type. Let G be the complement of a graph G. It is shown that if s≥2 and n≥15(s−1), then ∣μs(G)∣+∣μs(G)∣≤n/2(s−1)−1. Also if s≥1 and n≥4s, then ∣μn−s+1(G)∣+∣μn−s+1(G)∣≤n/2s+1. If s=2k+1 for some integer k, these bounds are asymptotically tight. These results settle infinitely many cases of a general open problem.
Let G be graph on n vertices and G(t) its blow-up graph of order t. In this paper, we determine all eigenvalues of the Laplacian and the signless Laplacian matrix of G(t) and its complement G(t)ˉ.
In this paper extremal problems for uniform hypergraphs are studied in the general setting of hereditary properties. It turns out that extremal problems about edges are particular cases of a general analyic problem about a recently introduced graph parameter. The paper builds a basis for the systematic study of this parameter and illustrates a range of various proof tools. It is shown that extremal problems about the number of edges of uniform hypergraphs are asymptotically equivalent to extremal problems about the largest eigenvalue; this result is new even for 2-graphs. Several concrete problems are adressed and solutions to many more are suggested. A number of open problems are raised and directions for further studies are outlined.
We give a combinatorial extension of the classical inequalities of Maclaurin about symmetric functions of several variables. We discuss two problems - one analytical and another combinatorial - and show that they are in some sense equaivalent. These results complete and extend earlier results of Motzkin and Straus, Khadzhiivanov, Sos and Straus, Fisher and Ryan, and Petingi and Rodriguez.
This paper develops analityc methods for investigating uniform hypergraphs. Its starting point is the spectral theory of 2-graphs, in particular, the largest and the smallest eigenvalues of 2-graphs. On the one hand, this simple setup is extended to weighted r-graphs, and on the other, the eigenvalues-numbers are generalized to eigenvalues-functions, which encompass also other graph parameters like Lagrangians and number of edges. The resulting theory is new even for 2-graphs, where well-settled topics become challenges again. The paper covers a multitude of topics, with more than a hundred concrete statements to underpin an analytic theory for hypergraphs. Essential among these topics are a Perron-Frobenius type theory and methods for extremal hypergraph problems. Many open problems are raised and directions for possible further research are outlined.
This paper gives tight upper bounds on the largest eigenvalue q(G) of the signless Laplacian of graphs with no 4-cycle and no 5-cycle. If n is odd, let F_{n} be the friendship graph of order n; if n is even, let F_{n} be F_{n-1} with an edge hanged to its center. It is shown that if G is a graph of order n, with no 4-cycle, then q(G)<q(F_{n}), unless G=F_{n}. Let S_{n,k} be the join of a complete graph of order k and an independent set of order n-k. It is shown that if G is a graph of order n, with no 5-cycle, then q(G)<q(S_{n,2}), unless G=S_{n,k}. It is shown that these results are significant in spectral extremal graph problems. Two conjectures are formulated for the maximum q(G) of graphs with forbidden cycles.
This paper gives a tight upper bound on the spectral radius of the signless Laplacian of graphs of given order and clique number. More precisely, let G be a graph of order n, let A be its adjacency matrix, and let D be the diagonal matrix of the row-sums of A. If G has clique number r, then the largest eigenvalue q(G) of the matrix Q=A+D satisfies q(G)<= 2(1-1/r)n. If G is a complete regular r-partite graph, then equality holds in the above inequality. This result confirms a conjecture of Hansen and Lucas.
This paper gives tight upper bound on the largest eigenvalue q(G) of the signless Laplacian of graphs with no paths of given order. The main ingredient of our proof is a stability result of its own interest, about graphs with large minimum degree and with no long paths. This result extends previous work of Ali and Staton.
In this paper, we mainly study the trace norm of the adjacency matrix of a graph, also known as the energy of graph. We give the maximum trace norms for the graph and its complement. In fact, the above problem is stated and solved in a more general setup - for nonnegative matrices with bounded entries. In particular, this study exhibits analytical matrix functions attaining maxima on matrices with rigid and complex combinatorial structure. In the last section the same questions are studied for Ky Fan norms. Possibe directions for further research are outlined, as it turns out that the above problems are just a tip of a larger multidimensional research area.
This note answers extremal questions like: what is the maximum number of edges in a graph of order n, which belongs to some hereditary property. The same question is answered also for the spectral radius and other similar parameters.
Let G be a graph of order n, and let q1(G)≥...≥qn(G) be the eigenvalues of the Q-matrix of G, also known as the signless Laplacian of G. In this paper we give a necessary and sufficient condition for the equality qk(G)=n−2, where 1<k≤n. In particular, this result solves an open problem raised by Wang, Belardo, Huang and Borovicanin. We also show that [ q_{2}(G) \geqδ(G)] and determine that equality holds if and only if G is one of the following graphs: a star, a complete regular multipartite graph, the graph K1,3,3, or a complete multipartite graph of the type K1,...,1,2,...,2.
In recent years several classical results in extremal graph theory have been improved in a uniform way and their proofs have been simplified and streamlined. These results include a new Erdős-Stone-Bollobás theorem, several stability theorems, several saturation results and bounds for the number of graphs with large forbidden subgraphs. Another recent trend is the expansion of spectral extremal graph theory, in which extremal properties of graphs are studied by means of eigenvalues of various matrices. One particular achievement in this area is the casting of the central results above in spectral terms, often with additional enhancement. In addition, new, specific spectral results were found that have no conventional analogs. All of the above material is scattered throughout various journals, and since it may be of some interest, the purpose of this survey is to present the best of these results in a uniform, structured setting, together with some discussions of the underpinning ideas.
We introduce and study a new type of Ramsey-Turan problems, a typical example of which is the following one: let c>0 and G be a graph of sufficiently large order n with minimum degree >3n/4. If the edges of G are colored in blue or red, then for every 3<k<(1/8-c)n, there exists a monochromatic cycle of length k.
A number of famous results about triangle-free graphs determine the maximum chromatic number of graphs of order n with minimum degree greater than n/3. In this note these results are extended to Kr-free graphs.
In the recent years, the trace norm of graphs has been extensively studied under the name of graph energy. In this paper some of this research is extended to more general matrix norms, like the Schatten p-norms and the Ky Fan k-norms. Whenever possible the results are given both for graphs and general matrices. In various contexts a puzzling fact was observed: the Schatten p-norms are widely different for 1<=p<2 and for p>=2.
We show that if G is a graph of sufficiently large order n containing as many r-cliques as the r-partite Turan graph of order n; then for some C>0 G has more than Cn^(r-1) (r+1)-cliques sharing a common edge unless G is isomorphic to the the r-partite Turan graph of order n. This structural result generalizes a previous result that has been useful in extremal graph theory.
In the recent years, the trace norm of graphs has been extensively studied under the name of graph energy. The trace norm is just one of the Ky Fan k-norms, given by the sum of the k largest singular values, which are studied more generally in the present paper. Several relations to chromatic number, spectral radius, spread, and to other fundamental parameters are outlined. Some results are extended to more general matrices.
In this note, extending some results of Erdos, Frankl, Rodl, Alexeev, Bollobas and Thomason we determine asymptotically the number of graphs which do not contain certain large subgraphs. In particular, if H_1,...,H_n,... are graphs with chromatic numbers r_1,...,r_n,... and order o(log n), we dermine asymptotically the number of graphs of order n not containing H_n as a subgraph. We also give similar results for induced subgraphs.
We prove that for all r≥2 and c>0, every graph of order n with at least cn^{r} cliques of order r contains a complete r-partite graph with each part of size ⌊crlogn⌋. This result implies a concise form of the Erdős-Stone theorem.
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.