pith. sign in

arxiv: math/0609755 · v1 · submitted 2006-09-27 · 🧮 math.CO

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

classification 🧮 math.CO
keywords extendablegraphfactorgraphsmatchingsubgraphsthencalled
0
0 comments X
read the original abstract

Let $G$ be a graph with vertex set $V(G)$. Let $n$ and $k$ be non-negative integers such that $n + 2k \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)-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 \in F$ (where $F$ is a fixed 1-factor in $G$), then $G$ is $(n, k)$-extendable graph.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.