Abstract—Given an undirected graph G = (V,E), with |V| = n, we consider an integer linear description of the polytope P_T(G) of p−vertex spanning subtrees. A p−vertex spanning subtree is a subtree that spans p < n vertices of G. The linear description of the polytope P_T(G) is mainly based on well known partition inequalities. The purpose of this paper is to study the facetness of partition inequalities of the polytope P_T(G). In a different approach as what is usually done, we first address constructive algorithms generating p−vertex spanning subtrees that incidence vectors are affinely independent. After, we apply such algorithms to show the facetness of these partition inequalities of P_T(G).

Key words—Graph, algorithm, valid inequality, facet, polytope

Belko Soumana Boubacar, Mamane Souleye Ibrahim are with Department of Mathematics and Computer Science, University Abdou Moumouni, Niamey, Niger.

Cite:Belko Soumana Boubacar, Mamane Souleye Ibrahim, "Facetness of Partition Inequalities of the p−vertex Spanning Subtree Polytope of a Graph ," International Journal of Applied Physics and Mathematics vol. 13, no. 3, pp. 24-33, 2023.

Copyright © 2023 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).