Almost balanced ordered biclique covering of graphs

Anand Babu, Ervin Ranjan, Maddipati Deshith Sai, Jatla Naga Sidhartha, Anagh Indu Suresh, Sreedhara Vishwas

arXivarxiv/2606.08506Jun 7, 2026math.COscore 0

Let $f(n,k)$ be the minimum size of a collection of bicliques such that (i) every edge of the complete graph $K_n$ is covered by at least one and at most $k$ bicliques in the collection, and (ii) for each edge $\{u,v\}$, the number of bicliques in which $u$ appears in the first class and $v$ in the second class differs by at most one from the number of bicliques in which $u$ appears in the second class and $v$ in the first class. For $k=1$, $f(n,k)$ reduces to the biclique partition number of $K_n$, and the Graham-Pollak theorem gives $f(n,1)=n-1$. For $k=2$, $f(n,k)$ is the ordered biclique…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2606.08506
curl -X POST /api/v1/records/arxiv/2606.08506/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.08506/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'