On the complexity of construction of complete and complete bipartite graphs

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.