A. I. Antonov, V. A. Bondarenko, “Polyhedral Graphs of GRAPH PARTITIONING and COMPLETE BIPARTITE SUBGRAPH Problems”, Model. Anal. Inform. Sist., 2012, Volume 19, Number 6,Pages <nobr>101

Polyhedral Graphs of GRAPH PARTITIONING and COMPLETE BIPARTITE SUBGRAPH Problems

A. I. Antonov, V. A. Bondarenko

P. G. Demidov Yaroslavl State University

Abstract: We provide an effective description of graphs of polyhedra for GRAPH PARTITIONING and COMPLETE BIPARTITE SUBGRAPH problems. We establish the fact, that the clique number for each of this problems increases exponentially with the dimension of the space.

Keywords: polyhedra of combinatorial problems, adjacency of vertices, clique number of graph of polyhedron.

UDC: 519.1

Received: 17.09.2012