Geodesic
On the complexity of construction of complete and complete bipartite graphs
Diskretnaya Matematika, Tome 20 (2008) no. 2, pp. 82-99.

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

We investigate the complexity of circuits constructing complete and complete bipartite graphs with the use of two operations of glueing vertices. These operations are the operations of identification of a pair of vertices with removal of loops and multiple edges. The first operation is applied to pairs of vertices in one graph, the second operation is applied to pairs of vertices in two graphs which have no common elements. The initial graph of the construction is the simplest graph consisting of two vertices connected by an edge. The number of operations performed on graphs is considered as the complexity of such a construction. Upper bounds for the complexity of construction of complete and complete bipartite graphs have been obtained previously. In this paper, we obtain lower bounds which give a possibility to find the order of the asymptotics of the complexity. 
@article{DM_2008_20_2_a6,
     author = {D. V. Zaitsev},
     title = {On the complexity of construction of complete and complete bipartite graphs},
     journal = {Diskretnaya Matematika},
     pages = {82--99},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2008_20_2_a6/}
}
TY  - JOUR
AU  - D. V. Zaitsev
TI  - On the complexity of construction of complete and complete bipartite graphs
JO  - Diskretnaya Matematika
PY  - 2008
SP  - 82
EP  - 99
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2008_20_2_a6/
LA  - ru
ID  - DM_2008_20_2_a6
ER  - 
%0 Journal Article
%A D. V. Zaitsev
%T On the complexity of construction of complete and complete bipartite graphs
%J Diskretnaya Matematika
%D 2008
%P 82-99
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2008_20_2_a6/
%G ru
%F DM_2008_20_2_a6
D. V. Zaitsev. On the complexity of construction of complete and complete bipartite graphs. Diskretnaya Matematika, Tome 20 (2008) no. 2, pp. 82-99. http://geodesic.mathdoc.fr/item/DM_2008_20_2_a6/

[1] Yablonskii C. V., Vvedenie v diskretnuyu matematiku, Vysshaya shkola, Moskva, 2002

[2] Zaitsev D. V., “O slozhnosti sborki grafov”, Intellektualnye sistemy, 9:1–4 (2005), 381–395