A tree whose complement is not eigensharp

DOI10.1016/S0024-3795(99)00253-0MaRDI QIDQ1971045zbMATH OpenFDO

Authors Valerie L. Watts

Publication date 15 September 2000

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0024-3795(99)00253-0

zbMATH Keywords

biclique decompositioneigensharp graph

Mathematics Subject Classification ID

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• On eigensharp and almost eigensharp graphs
• The biclique partition number of some important graphs
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
• On eigensharpness and almost eigensharpness of lexicographic products of some graphs
• Multicolored forests in bipartite decompositions of graphs

Cites work

• Biclique decompositions and Hermitian rank
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
• Eigenvalue inequalities and equalities
• Graph theory
• scientific article; zbMATH DE number 790476 (Why is no real title available?)
• On biclique decompositions of complete \(t\)-partite graphs
• On the Addressing Problem for Loop Switching
• On the decomposition ofkn into complete bipartite graphs

Cited in

(7)

• Inertia and biclique decompositions of joins of graphs
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
• On eigensharpness and almost eigensharpness of lexicographic products of some graphs
• The biclique partition number of some important graphs
• Eigensharp property of some certain graphs and their complements
• Some eigensharp and almost eigensharp graphs
• On eigensharp and almost eigensharp graphs

This page was built for publication: A tree whose complement is not eigensharp

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1971045)