Geodesic
On biclique covering number of the Cartesian product of graphs
Trudy Instituta matematiki, Tome 21 (2013) no. 1, pp. 78-87.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper is dealt with the biclique cover number (i.e. minimal number of complete bipartite subgraphs of a graph needed to cover the edge set of the graph) of the Cartesian product of two graphs. It is obtained upper bounds on the biclique cover number for the Cartesian product of graphs. It is given the formula for exact value of the biclique cover number for the Cartesian product of $P_n$ and $K_2$, $C_n$ and $K_2$, $P_n$ and $P_n$. 
@article{TIMB_2013_21_1_a9,
     author = {V. V. Lepin and O. I. Duginov},
     title = {On biclique covering number of the {Cartesian} product of graphs},
     journal = {Trudy Instituta matematiki},
     pages = {78--87},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2013_21_1_a9/}
}
TY  - JOUR
AU  - V. V. Lepin
AU  - O. I. Duginov
TI  - On biclique covering number of the Cartesian product of graphs
JO  - Trudy Instituta matematiki
PY  - 2013
SP  - 78
EP  - 87
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMB_2013_21_1_a9/
LA  - ru
ID  - TIMB_2013_21_1_a9
ER  - 
%0 Journal Article
%A V. V. Lepin
%A O. I. Duginov
%T On biclique covering number of the Cartesian product of graphs
%J Trudy Instituta matematiki
%D 2013
%P 78-87
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMB_2013_21_1_a9/
%G ru
%F TIMB_2013_21_1_a9
V. V. Lepin; O. I. Duginov. On biclique covering number of the Cartesian product of graphs. Trudy Instituta matematiki, Tome 21 (2013) no. 1, pp. 78-87. http://geodesic.mathdoc.fr/item/TIMB_2013_21_1_a9/

[1] Nau D. S., Markowsky G., Woodbury M. A., Amos D. B., “A mathematical analysis of human leukocyte antigen serology”, Math. Biosci., 40 (1978), 243–270 | DOI | MR | Zbl

[2] Amilhastre J., Vilarem M. C., Janssen P., “Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs”, Disc. App. Math., 86 (1998), 125–144 | DOI | MR | Zbl

[3] Kushilevitz E., Nisan N., Communication Complexity, Cambridge University Press, 2006 | MR

[4] Orlin J., “Containment in Graph Theory: covering graphs with cliques”, Nederl. Akad. Wetensch. Indag. Math., 39 (1977), 211–218 | MR

[5] Müller H., “On the perfectness and classes of bipartite graphs”, Discrete Math., 149 (1996), 159–187 | DOI | MR | Zbl

[6] Lepin V. V., “Lineinyi algoritm dlya vychisleniya chisla biklikovogo pokrytiya posledovatelno-parallelnogo grafa”, Tr. In-ta matematiki, 16:2 (2008), 63–75 | MR

[7] Lepin V. V., Duginov O. I., “Algoritmy dlya nakhozhdeniya pokrytii biklikami grafa s ogranichennoi putevoi shirinoi”, Tr. In-ta matematiki, 19:2 (2011), 69–81

[8] Fishburn P. C., Hammer P. L., “Bipartite dimensions and bipartite degrees of graphs”, Discrete Math., 160 (1996), 127–148 | DOI | MR | Zbl

[9] Quadras S., Vasanthica Q., “Biclique Cover of Complete Graph $K_n$ and Honeycomb Network $HC(n)$”, Proceedings ICIEIS 2011 (Kuala Lumpur, Malaysia, November 14–16, 2011), 151–158

[10] Jukna S., Kulikov A., “On covering graphs by complete bipartite subgraphs”, Discr. Math., 309 (2009), 3399–3403 | DOI | MR | Zbl

[11] Watts V., Covers and partitions of graphs by complete bipartite subgraphs, Phd Thesis, Queen's University, Kingston, Ontario, Canada, 2001

[12] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Knizhnyi dom “Librokom”, M., 2009

[13] Lepin V. V., Duginov O. I., “O biklikovom razbienii korony i soedineniya grafov”, Dokl. NAN Belarusi, 56:3 (2012), 10–15 | Zbl