Premium
On the Linear Description of the k ‐cycle Polytope
Author(s) -
Nguyen V. H.,
Maurras J.F.
Publication year - 2001
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/1475-3995.t01-1-00331
Subject(s) - combinatorics , polytope , undirected graph , convex hull , mathematics , graph , regular polygon , convex polytope , integer (computer science) , facet (psychology) , discrete mathematics , geometry , computer science , convex set , convex optimization , psychology , social psychology , personality , big five personality traits , programming language
We study a linear description of PC k n the convex hull of incidence vectors of all the cycles consisting of exactly k edges ( k ≥4) in K n , the complete undirected graph with n vertices. First, we describe some properties of PC k n . Second, we discuss relations between PC k n and PC k ′ n ′ with k ′> k and n ′> n . Then we give three lifting algorithms that transform a facet of PC k n into facets of PC k n ′ with n ′> n . Finally, we provide an integer formulation and a partial linear description of PC k n .