Exact Biclique Partition number of Split Graphs
This provides a theoretical result for graph theorists, extending a known theorem to split graphs, but it is incremental as it builds directly on prior work.
The paper tackles the problem of determining the biclique partition number for split graphs, showing that it equals the number of maximal cliques in the complement minus one, which extends the Graham-Pollak theorem to a broader class of graphs.
The biclique partition number of a graph \(G\), denoted \( \operatorname{bp}(G)\), is the minimum number of biclique subgraphs that partition the edge set of \(G\). The Graham-Pollak theorem states that the complete graph on \( n \) vertices cannot be partitioned into fewer than \( n-1 \) bicliques. In this note, we show that for any split graph \( G \), the biclique partition number satisfies \( \operatorname{bp}(G) = \operatorname{mc}(G^c) - 1 \), where \( \operatorname{mc}(G^c) \) denotes the number of maximal cliques in the complement of \( G \). This extends the celebrated Graham-Pollak theorem to a broader class of graphs.