On the maximal index of graphs with a prescribed number of edges (Q1116954): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0024-3795(83)90131-3 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2005637448 / rank | |||
Normal rank | |||
Revision as of 02:02, 20 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the maximal index of graphs with a prescribed number of edges |
scientific article |
Statements
On the maximal index of graphs with a prescribed number of edges (English)
0 references
1988
0 references
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}\).
0 references
eigenvalue
0 references
index of a graph
0 references
adjacency matrix
0 references
maximal index
0 references
