Abstract
A polyhedron Mn which is the convex hull of a set of characteristic vectors for all cubic subgraphs of the complete graph Gn is studied. It is shown that the problem of vertices nonadjacency recognition for this polyhedron is NP-complete and the density of its polyhedral graph is exponential on n. Such a set of properties combines the polyhedron Mn with the known polyhedron of Hamiltonian cycles.
Get full access to this article
View all access options for this article.