A tree whose complement is not eigensharp (Q1971045)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A tree whose complement is not eigensharp |
scientific article |
Statements
A tree whose complement is not eigensharp (English)
0 references
15 September 2000
0 references
The biclique decomposition number, \(b(G)\), is the minimum number of complete bipartite subgraphs needed to partition the edges of a graph \(G\). It is known that \(b(G)\) is at least the maximum of the number of positive and negative eigenvalues of the adjacency matrix \(A\) of \(G\); that is \(b(G)\geq\max\{ n_+(A),n_-(A)\}\). When equality is attained, \(G\) is said to be eigensharp. In the paper it is shown that there is a tree on 14 vertices whose complement is not eigensharp. It is also shown that \(G\) is eigensharp when \(G\) is the complement of a forest where each component is a path.
0 references
biclique decomposition
0 references
eigensharp graph
0 references