The maximum spectral radius of C4-free graphs of given order and size
By Vladimir Nikiforov. 2007
103 citations recorded by the source corpus.
Suppose that G is a graph with n vertices and m edges, and let μ be the spectral radius of its adjacency matrix. Recently we showed that if G has no 4-cycle, then μ2-μ⩽n-1, with equality if and only if G is the friendship graph. Here we prove that if m⩾9 and G has no 4-cycle, then μ2⩽m, with equality if G is a star. For 4⩽m⩽8 this assertion fails.
Subfields: Computational Theory and Mathematics, Electrical and Electronic Engineering, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/094800356ccd210ffdec663bbcbe59797c958de3
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Yongtao Li
- Lihua Feng
- Weijun Liu
- Vladimir Nikiforov
- L. Lov'asz
- Peter Rowlinson
- Christian Reiher
- Xiaodong Zhang
In Electrical and Electronic Engineering
In Geometry and Topology
- Yongtao Li
- Lihua Feng
- Weijun Liu
- Vladimir Nikiforov
- L. Lov'asz
- Peter Rowlinson
- Christian Reiher
- Xiaodong Zhang
Citations in the corpus
- Some new results in extremal graph theory (2011, background): “Here is a considerably more involved bound on the spectral radius of a C4-free graph of given size, given in [77].”
- A survey on spectral conditions for some extremal graph problems (2021, background): “In 2009, Nikiforov [152] proved an interesting result, which gives an upper bound on the spectral radius for C4-free graph with given number of edges.”