The local density of triangle-free graphs (Q1382812): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:09, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The local density of triangle-free graphs |
scientific article |
Statements
The local density of triangle-free graphs (English)
0 references
14 September 1998
0 references
The objective of the paper is to determine for real numbers \(a\) \((0\leq a\leq 1)\) the smallest real number \(b(a)\) with the property that every triangle-free graph of order \(n\) has subsets of \(\lfloor an\rfloor\) vertices which span at most \(b(a)n^2\) edges. It is shown that the minimum number of edges which need to be deleted to make a regular graph of order \(n\) bipartite is at least \((c_1+ c_n)n/4\), where \(c_1\geq c_2\geq \cdots\geq c_n\) are the eigenvalues of the adjacency matrix of the graph. Finally, a conjecture about the spectrum of regular triangle-free graphs is raised.
0 references
density
0 references
eigenvalues
0 references
adjacency matrix
0 references
triangle-free graphs
0 references