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
    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
    0 references
    biclique decomposition
    0 references
    eigensharp graph
    0 references

    Identifiers