A tree whose complement is not eigensharp
type: Item
instance of: scholarly article
title: A tree whose complement is not eigensharp
zbMATH Open document ID: 0944.05078
DOI: 10.1016/S0024-3795(99)00253-0
author: Valerie L. Watts
published in: Linear Algebra and its Applications
publication date: 2000-09-15T00:00:00Z
review text: 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.
reviewed by: Martin Knor
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1421393
zbMATH Keywords: biclique decomposition
zbMATH Keywords: eigensharp graph
MaRDI profile type: Publication
cites work: Q5422499
cites work: On biclique decompositions of complete \(t\)-partite graphs
cites work: On the Addressing Problem for Loop Switching
cites work: Biclique decompositions and Hermitian rank
cites work: Eigenvalue inequalities and equalities
cites work: Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
cites work: Q4846548
cites work: On the decomposition ofkn into complete bipartite graphs
description: scientific article; zbMATH DE number 1421393