On biclique coverings

Sergei Bezrukov; Dalibor Fronček; Steven J. Rosenberg; Petr Kovář

doi:10.1016/j.disc.2006.11.045

On biclique coverings

Sergei Bezrukov
, Dalibor Fronček
, Steven J. Rosenberg
, Petr Kovář

Mathematics & Statistics

Research output: Contribution to journal › Article › peer-review

15 Scopus citations

Abstract

It was proved by Fronček, Jerebic, Klavžar, and Kovář that if a complete bipartite graph K_{n, n} with a perfect matching removed can be covered by k bicliques, then n ≤ fenced(frac(k, ⌊ frac(k, 2) ⌋)). We give a slightly simplified proof and we show that the result is tight. Moreover, we use the result to prove analogous bounds for coverings of some other classes of graphs by bicliques.

Original language	English (US)
Pages (from-to)	319-323
Number of pages	5
Journal	Discrete Mathematics
Volume	308
Issue number	2-3
DOIs	https://doi.org/10.1016/j.disc.2006.11.045
State	Published - Feb 6 2008

Keywords

Bicliques
Graph composition
Graph coverings
Lexicographic product
Sperner's Theorem

Publisher link

10.1016/j.disc.2006.11.045

Find It

Find It at U of M Libraries

Cite this

@article{18b809dc6da743ad93a7b278238aa5e9,

title = "On biclique coverings",

abstract = "It was proved by Fron{\v c}ek, Jerebic, Klav{\v z}ar, and Kov{\'a}{\v r} that if a complete bipartite graph Kn, n with a perfect matching removed can be covered by k bicliques, then n ≤ fenced(frac(k, ⌊ frac(k, 2) ⌋)). We give a slightly simplified proof and we show that the result is tight. Moreover, we use the result to prove analogous bounds for coverings of some other classes of graphs by bicliques.",

keywords = "Bicliques, Graph composition, Graph coverings, Lexicographic product, Sperner's Theorem",

author = "Sergei Bezrukov and Dalibor Fron{\v c}ek and Rosenberg, \{Steven J.\} and Petr Kov{\'a}{\v r}",

year = "2008",

month = feb,

day = "6",

doi = "10.1016/j.disc.2006.11.045",

language = "English (US)",

volume = "308",

pages = "319--323",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "2-3",

}

TY - JOUR

T1 - On biclique coverings

AU - Bezrukov, Sergei

AU - Fronček, Dalibor

AU - Rosenberg, Steven J.

AU - Kovář, Petr

PY - 2008/2/6

Y1 - 2008/2/6

N2 - It was proved by Fronček, Jerebic, Klavžar, and Kovář that if a complete bipartite graph Kn, n with a perfect matching removed can be covered by k bicliques, then n ≤ fenced(frac(k, ⌊ frac(k, 2) ⌋)). We give a slightly simplified proof and we show that the result is tight. Moreover, we use the result to prove analogous bounds for coverings of some other classes of graphs by bicliques.

AB - It was proved by Fronček, Jerebic, Klavžar, and Kovář that if a complete bipartite graph Kn, n with a perfect matching removed can be covered by k bicliques, then n ≤ fenced(frac(k, ⌊ frac(k, 2) ⌋)). We give a slightly simplified proof and we show that the result is tight. Moreover, we use the result to prove analogous bounds for coverings of some other classes of graphs by bicliques.

KW - Bicliques

KW - Graph composition

KW - Graph coverings

KW - Lexicographic product

KW - Sperner's Theorem

UR - https://www.scopus.com/pages/publications/36248977676

UR - https://www.scopus.com/pages/publications/36248977676#tab=citedBy

U2 - 10.1016/j.disc.2006.11.045

DO - 10.1016/j.disc.2006.11.045

M3 - Article

AN - SCOPUS:36248977676

SN - 0012-365X

VL - 308

SP - 319

EP - 323

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2-3

ER -

On biclique coverings

Abstract

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this