On the complexity of construction of complete and complete bipartite graphs
D. V. Zaitsev
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.
PDF file (200 kB)
Discrete Mathematics and Applications, 2008, 18:3, 251–269
D. V. Zaitsev, “On the complexity of construction of complete and complete bipartite graphs”, Diskr. Mat., 20:2 (2008), 82–99; Discrete Math. Appl., 18:3 (2008), 251–269
Citation in format AMSBIB
\paper On the complexity of construction of complete and complete bipartite graphs
\jour Diskr. Mat.
\jour Discrete Math. Appl.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|