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

Guizhen Liu; Qinglin Yu

paper

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

arXiv:math/0609755

Abstract

Let $G$ be a graph with vertex set $V (G)$ . Let $n$ and $k$ be non-negative integers such that $n + 2 k \leq ∣ 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) - e x t e n d ab l e g r a p h . I n t hi s p a p er w e p r ese n t se v er a l r es u l t s ab o u t$ (n, k) $- e x t e n d ab l e g r a p h s an d i t ss u b g r a p h s . I n p a r t i c u l a r, w e p r o v e d t ha t i f$ G - V(e) $i s$ (n, k) $- e x t e n d ab l e g r a p h f or e a c h$ e \in F $(w h er e$ F $i s a f i x e d 1 - f a c t or in$ G $), t h e n$ G $i s$ (n, k)$-extendable graph.

8 pages