Premium
A result on extendibility in the powers of graphs
Author(s) -
Shavo Kara Walcher
Publication year - 2007
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/jgt.20242
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , bound graph , discrete mathematics , integer (computer science) , graph power , line graph , computer science , programming language
Let G be a graph on p vertices. Then for a positive integer n , 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 . The purpose of this article is to show that if G 2 k is n ‐extendible, for some k ∈ ℕ, then so is G 2 k +1 , where G q is the graph with the same vertex set as G and in which two vertices u and v are adjacent if and only if d G ( u , v ) ≤ q . We will also show that if G k is 1‐extendible then so is G k +1 . © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 1–22, 2007