Premium
Matching extension in the powers of n ‐connected graphs
Author(s) -
Walcher Kara Lee
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199612)23:4<355::aid-jgt4>3.0.co;2-q
Subject(s) - combinatorics , mathematics , integer (computer science) , extension (predicate logic) , matching (statistics) , graph , set (abstract data type) , discrete mathematics , computer science , statistics , programming language
Let G be a graph on p vertices. Then for a positive integer n 1 G is said to be n ‐extendible if (i) n < p /2, (ii) G has a set of n independent edges, and (iii) every such set is contained in a perfect matching of G . In this paper we will show that if p is even and G is n ‐connected, then G k is $(\lceil{{kn}\over 2}\rceil -1)$ ‐extendible for every integer k ≥ 2 such that $\lceil{{kn}\over 2}\rceil -1 < p/2 $ . © 1996 John Wiley & Sons, Inc.