





















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。