On the \(p\)-factor-criticality of the Klein bottle (Q1886362)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the \(p\)-factor-criticality of the Klein bottle |
scientific article |
Statements
On the \(p\)-factor-criticality of the Klein bottle (English)
0 references
18 November 2004
0 references
If \(G\) is a graph on \(n\) vertices and \(p\) an integer such that \(n- p\) is even and \(0< n- p\leq n\), then \(G\) is called \(p\)-factor-critical if and only if the removal of any \(p\) vertices results in a graph with a perfect matching. The factor-criticality \(p(\Sigma)\) of a surface \(\Sigma\) is the smallest integer \(p\) such that no graph which embeds into \(\Sigma\) is \(p\)-factor-critical. The authors prove that \(p(\Sigma)= 6\) if \(\Sigma\) is the Klein bottle, thus completing results (which are not yet published) of H. Su and H. Zhang concerning factor-criticality; those results yield \(p(\Sigma)< 6\) while this paper presents 5-factor-critical triangulations of the Klein bottle thus showing \(p(\Sigma)\geq 6\).
0 references
perfect matching
0 references
factor-criticality
0 references
extendability of matchings
0 references
graphs on surfaces
0 references
Klein bottle
0 references
\(p\)-factor-criticality
0 references