A new recursive theorem on n-extendibility
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.
- Two recursive theorems on \(n\)-extendibility
- Publication:4488558
- An extension of the nondiamond theorem in classical and α-recursion theory
- scientific article; zbMATH DE number 3845570
- scientific article; zbMATH DE number 734454
- Extending properly n - REA sets1
- GENERALIZATIONS OF THE RECURSION THEOREM
- An Extension of Muchnik's Theorem
- Some Theorems on Classes of Recursively Enumerable Sets
- An Extension of Panjer's Recursion
- Two recursive theorems on \(n\)-extendibility
- An extension of the nondiamond theorem in classical and α-recursion theory
- A recursion-theoretic characterization of instances of $ΒΣ_n$ provable in $П_{n+1}(N)$
- scientific article; zbMATH DE number 734454 (Why is no real title available?)
- scientific article; zbMATH DE number 1471063 (Why is no real title available?)
This page was built for publication: A new recursive theorem on \(n\)-extendibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q675894)
