39 citations · 203 across the 85 of their papers we have counts for
21 papers · 1 filter
The maximum spectral radius of C_4-free graphs of given order and size
Vladimir Nikiforov
Let G be a graph of n vertices and m edges, and let G has no cycles of length 4. We give upper bounds on the adjacency spectral radius of G in terms of n and m.
Graphs with many copies of a given subgraph
Vladimir Nikiforov
We show that if a graph G of order n contains many copies of a given subgraph H, then it contains a blow-up of H of order log n.
Spectral saturation: inverting the spectral Turan theorem
Vladimir Nikiforov
We prove that if the spectral radius of a graph G of order n is larger than the spectral radius of the r-partite Turan graph of the same order, then G contains various supergraphs…
A spectral stability theorem for large forbidden graphs
Vladimir Nikiforov
We extend the classical stability theorem of Erdos and Simonovits in two directions: first, we allow the order of the forbidden graph to grow as log of order of the host graph, and…
Complete r-partite subgraphs of dense r-graphs
Vladimir Nikiforov
We determine how large r-partite graphs can be found in r-uniform graphs with n vertices and Cn^r edges, where C is a slowly decreasing function of n. This refines results of Erdos…
The energy of C4-free graphs of bounded degree
Vladimir Nikiforov
Answering some questions of Gutman, we show that, except for four specific trees, every connected graph G of order n, with no cycle of order 4 and with maximum degree at most 3, ha…
The number of cliques in graphs of given order and size
Vladimir Nikiforov
Let k_r(n,m) denote the minimum number of r-cliques in graphs with n vertices and m edges. For r=3,4 we give a lower bound on k_r(n,m) that approximates k_r(n,m) with an error smal…
A spectral condition for odd cycles in graphs
Vladimir Nikiforov
We give a sharp spectral condition for the existence of odd cycles in a graph of given order. We also prove a related stability result.
Turan's theorem inverted
Vladimir Nikiforov
Turan's theorem implies that every graph of order n with more edges than the r-partite Turan graph contains a complete graph of order r+1. We show that the same premise implies the…
Stability for large forbidden subgraphs
Vladimir Nikiforov
We extend the classical stability theorem of Erdos and Simonovits for forbidden graphs of logarithmic order.
A spectral Erdos-Stone-Bollobas theorem
Vladimir Nikiforov
We give a bound on the spectral radius of a graph implying a quantitative version of the Erdos-Stone theorem.
More spectral bounds on the clique and independence numbers
Vladimir Nikiforov
We give some new bounds for the clique and independence numbers of a graph in terms of its eigenvalues.
The spectral radius of subgraphs of regular graphs
Vladimir Nikiforov
We give a bound on the spectral radius of subgraphs of regular graphs with given order and diameter. We give a lower bound on the smallest eigenvalue of a nonbipartite regular grap…
An Abstract Regularity Lemma
Bela Bollobas, Vladimir Nikiforov
We extend Szemeredi's Regularity Lemma (SRL) to abstract measure spaces. Our main aim is to find general conditions under which the original proof of Szemeredi still works. To illu…
Regular, pseudo-regular, and almost regular matrices
Vladimir Nikiforov
We give lower bounds on the largest singular value of arbitrary matrices, some of which are asymptotically tight for almost all matrices. To study when these bounds are exact, we i…
Numerical radius and zero pattern of matrices
Vladimir Nikiforov
We give tight upper bounds on the numerical range of square matrices in terms of their Frobenius (Euclidian) norm and a combinatorial parameter similar to the clique number of grap…
Revisiting Schur's bound on the largest singular value
Vladimir Nikiforov
We give upper and lower bounds on the largest singular value of a matrix using analogues to walks in graphs. For nonnegative matrices these bounds are asymptotically tight. In part…
Ramsey Goodness and Beyond
Vladimir Nikiforov, Cecil C. Rousseau
In a seminal paper from 1983, Burr and Erdos started the systematic study of Ramsey numbers of cliques vs. large sparse graphs, raising a number of problems. In this paper we devel…
Graphs with many r-cliques have large complete r-partite subgraphs
Vladimir Nikiforov
We prove that for all 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 $\lfloor c^{r}\log…
The Moore bound for Spectral Radius
Vladimir Nikiforov
We give an upper bound on the largest eigenvalue of a graph of given order, size, and girth.
Chromatic number and spectral radius
Vladimir Nikiforov
Let G be a graph, H be its chromatic number, L be the largest eigenvalue of its Laplacian, and M be the largest eigenvalue of its adjacency matrix. Then, complementing a well-known…