A new recursive theorem on \(n\)-extendibility (Q675894)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new recursive theorem on \(n\)-extendibility |
scientific article |
Statements
A new recursive theorem on \(n\)-extendibility (English)
0 references
11 March 1997
0 references
A graph \(G\) having a 1-factor is called \(n\)-extendible if every matching of size \(n\) extends to a 1-factor. A graph \(G\) is called \(\langle r,n\rangle\)-extendible if \(G-S\) is \(n\)-extendible for every connected subset \(S\) of order \(2r\) for which \(G-S\) is connected. Let \(p\), \(r\) and \(n\) be integers with \(r>0\) and \(p-r>n>0\). It is shown that every 2-connected \(\langle r,n\rangle\)-extendible graph of order \(2p\) is \(\langle r-1,n\rangle\)-extendible. This result is used to show that if \(G\) is a 2-connected graph of order \(2p\) and if \(r\geq 0\) and \(n>0\) are integers such that \(p-r\geq n+1\), and if \(G-S\) is \(n\)-extendible for every connected subgraph \(S\) of order \(2r\) for which \(G-S\) is connected, then \(G\) is \(n\)-extendible.
0 references
\(n\)-extendibility
0 references
matching
0 references
1-factor
0 references