On the maximal index of graphs with a prescribed number of edges
type: Item
instance of: scholarly article
title: On the maximal index of graphs with a prescribed number of edges
zbMATH Open document ID: 0666.05043
DOI: 10.1016/0024-3795(83)90131-3
author: P. Rowlinson
published in: Linear Algebra and its Applications
publication date: 1988-01-01T00:00:00Z
review text: The index of a finite simple graph is the largest eigenvalue of its (0,1)-adjacency matrix. In the paper the author answers in the affirmative a conjecture of Brualdi and Hoffman, namely he shows that the maximal index among all graphs with n edges is attained by the graph obtained from the complete graph on d vertices, \({d\choose 2}<n<{d+1\choose 2}\), by adding one new vertex of degree \(n-{d\choose 2}\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 4089587
zbMATH Keywords: eigenvalue
zbMATH Keywords: index of a graph
zbMATH Keywords: adjacency matrix
zbMATH Keywords: maximal index
reviewed by: Peter Horák
MaRDI profile type: Publication
full work available at URL: 0024-3795(83)90131-3
OpenAlex ID: W2005637448
cites work: On the spectral radius of (0,1)-matrices
cites work: The maximal eigenvalue of 0-1 matrices with prescribed number of ones
cites work: Bounds on the spectral radius of graphs with e edges
cites work: Q3254327
cites work: A bound on the spectral radius of graphs with \(e\) edges
Recommended article: On the maximal index of connected graphs
Recommended article: Q3577555
Recommended article: Q3809825
Recommended article: On maximum Estrada indices of graphs with given parameters
Recommended article: On the number of edges in maximally linkless graphs
Recommended article: Q5165199
Recommended article: On the maximum Laplacian Estrada index of graphs
Recommended article: Graphs of fixed order and size with maximal \(A_\alpha\)-index
Recommended article: Q3974327
Recommended article: Maximum values of Szeged index and edge-Szeged index of graphs
description: scientific article; zbMATH DE number 4089587