Antiwebs are rank-perfect
type: Item
instance of: scholarly article
title: Antiwebs are rank-perfect
zbMATH Open document ID: 1112.05082
author: Annegret K. Wagler
published in: 4OR
publication date: 2004-10-28T00:00:00Z
review text: For positive integers \(m\) and \(k\), \(W^k_n\) denotes the graph with vertex set \(\{1, \ldots, n\}\) and edge set \(\{ij: 0< | i-j| \leq k\mod n\}\). A web is a \(W^k_n\) for some \(n\) and \(k\), and an antiweb is the complement of a web. While not any web is rank-perfect, the author points out that it is implied by a result due to \textit{F. B. Shepherd} [``Applying Lehman's theorem to packing problems'', Math. Program. 71, No. 3(A), 353--367 (1995; Zbl 0863.05052)], that all antiwebs are rank-perfect, i.e., the stable set polytope of such a graph \(G\) is completely given by the nonnegativity constraints, \(\forall i\in\{1, \ldots, n\}, x_i\geq 0\), and the rank-constraints, \(\forall I\subseteq\{1, \ldots, n\}, \sum_{i\in I} x_i \leq \alpha(I)\). Where \(\alpha(I)\) is the independence number (the largest number of pairwise nonadjacent vertices) of the subgraph of \(G\) induced by \(I\).
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 2111550
zbMATH Keywords: stable set polytope
zbMATH Keywords: rank constraints
zbMATH Keywords: antiwebs
MaRDI profile type: Publication
full work available at URL: s10288-003-0032-4
OpenAlex ID: W2036645770
DOI: 10.1007/S10288-003-0032-4
Recommended article: Almost all webs are not rank-perfect
Recommended article: On the Chvàtal-rank of antiwebs
Recommended article: On webs of maximum rank
Recommended article: Q4329155
Recommended article: Correction to: On webs of maximum rank
Recommended article: Q5289231
Recommended article: Rank of ordinary webs in codimension one an effective method
Recommended article: A lower bound on the Chvátal-rank of antiwebs
Recommended article: Construction for antimagic generalized web graphs
Recommended article: Q5289158
description: scientific article; zbMATH DE number 2111550