Standard

On covering graphs by complete bipartite subgraphs. / Jukna, S.; Kulikov, A. S.

In: Discrete Mathematics, Vol. 309, No. 10, 28.05.2009, p. 3399-3403.

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

Harvard

Jukna, S & Kulikov, AS 2009, 'On covering graphs by complete bipartite subgraphs', Discrete Mathematics, vol. 309, no. 10, pp. 3399-3403. https://doi.org/10.1016/j.disc.2008.09.036

APA

Jukna, S., & Kulikov, A. S. (2009). On covering graphs by complete bipartite subgraphs. Discrete Mathematics, 309(10), 3399-3403. https://doi.org/10.1016/j.disc.2008.09.036

Vancouver

Jukna S, Kulikov AS. On covering graphs by complete bipartite subgraphs. Discrete Mathematics. 2009 May 28;309(10):3399-3403. https://doi.org/10.1016/j.disc.2008.09.036

Author

Jukna, S. ; Kulikov, A. S. / On covering graphs by complete bipartite subgraphs. In: Discrete Mathematics. 2009 ; Vol. 309, No. 10. pp. 3399-3403.

BibTeX

@article{8a8f4eb466bc46a2a89739b45cc21bd6,
title = "On covering graphs by complete bipartite subgraphs",
abstract = "We prove that, if a graph with e edges contains m vertex-disjoint edges, then m2 / e complete bipartite subgraphs are necessary to cover all its edges. Similar lower bounds are also proved for fractional covers. For sparse graphs, this improves the well-known fooling set lower bound in communication complexity. We also formulate several open problems about covering problems for graphs whose solution would have important consequences in the complexity theory of boolean functions.",
keywords = "Biclique, Boolean functions, Communication complexity, Edge clique covering number, Fractional covers",
author = "S. Jukna and Kulikov, {A. S.}",
year = "2009",
month = may,
day = "28",
doi = "10.1016/j.disc.2008.09.036",
language = "English",
volume = "309",
pages = "3399--3403",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "10",

}

RIS

TY - JOUR

T1 - On covering graphs by complete bipartite subgraphs

AU - Jukna, S.

AU - Kulikov, A. S.

PY - 2009/5/28

Y1 - 2009/5/28

N2 - We prove that, if a graph with e edges contains m vertex-disjoint edges, then m2 / e complete bipartite subgraphs are necessary to cover all its edges. Similar lower bounds are also proved for fractional covers. For sparse graphs, this improves the well-known fooling set lower bound in communication complexity. We also formulate several open problems about covering problems for graphs whose solution would have important consequences in the complexity theory of boolean functions.

AB - We prove that, if a graph with e edges contains m vertex-disjoint edges, then m2 / e complete bipartite subgraphs are necessary to cover all its edges. Similar lower bounds are also proved for fractional covers. For sparse graphs, this improves the well-known fooling set lower bound in communication complexity. We also formulate several open problems about covering problems for graphs whose solution would have important consequences in the complexity theory of boolean functions.

KW - Biclique

KW - Boolean functions

KW - Communication complexity

KW - Edge clique covering number

KW - Fractional covers

UR - http://www.scopus.com/inward/record.url?scp=67349147376&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2008.09.036

DO - 10.1016/j.disc.2008.09.036

M3 - Article

AN - SCOPUS:67349147376

VL - 309

SP - 3399

EP - 3403

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 10

ER -

ID: 49825246