On (n, k)-extendable graphs and induced subgraphs

Original · EN

Let G be a graph with vertex set V(G). Let n and k be non-negative integers such that n + 2k ≤ |V(G)| - 2 and |V(G)| - n is even. If when deleting any n vertices of G the remaining subgraph contains a matching of k edges and every k-matching can be extended to a 1-factor, then G is called an (n, k)-extendable graph. In this paper we present several results about (n, k)-extendable graphs and its subgraphs. In particular, we proved that if G - V(e) is (n, k)-extendable graph for each e ∈ F (where F is a fixed 1-factor in G), then G is (n, k)-extendable graph.