On strongly \(k\)-extendable graphs
type: Item
instance of: scholarly article
zbMATH Open document ID: 0983.05068
publication date: 2002-04-21T00:00:00Z
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1657293
zbMATH Keywords: perfect matching
zbMATH Keywords: strongly \(k\)-extendable
author: N. Ananchuen
MaRDI profile type: Publication
Recommended article: On minimum degree of strongly \(k\)-extendable graphs
Recommended article: Q4855964
Recommended article: Q5300303
Recommended article: Q4033687
Recommended article: On the extending ofk-regular graphs and their strong defining spectrum
Recommended article: Q4304325
Recommended article: Extension of strongly regular graphs
Recommended article: Q4460554
Recommended article: Q5393538
Recommended article: On the strong product of a \(k\)-extendable and an \(l\)-extendable graph
title: On strongly \(k\)-extendable graphs
published in: JCMCC. The Journal of Combinatorial Mathematics and Combinatorial Computing
review text: It is known that a matching \(M\) in a graph \(G= G(V,E)\) is a subset of \(E(G)\) in which no two edges have a vertex in common. A vertex \(v\) is saturated by \(M\) if some edge of \(M\) is incident to \(v\) and a matching is called to be perfect if it saturates every vertex of the graph. Let \(G\) be a simple connected graph on \(2n\) vertices with a perfect matching. For a given positive integer \(k\), \(1\leq k\leq n-1\), the graph \(G\) is \(k\)-extendable if for every matching \(M\) of size \(k\) in \(G\), there exists a perfect matching in \(G\) containing all the edges of \(M\). For an integer \(k\), \(0\leq k\leq n-2\), \(G\) is said to be strongly \(k\)-extendable or simply \(k^*\)-extendable if for every pair of vertices \(u\) and \(v\) of \(G\), \(G-\{u, v\}\) is \(k\)-extendable.NEWLINENEWLINENEWLINEIn the present paper these graphs are characterized for any \(k\). At first known results on \(k\)-extendable graphs useful for the investigation of \(k^*\)-extendable graphs are summarized. Then basic properties are proved, among other things also two theorems which yield a necessary and sufficient condition for graphs to be \(k^*\)-extendable, for example, Theorem 3.6: If \(G\) is a graph on \(2n\) vertices and if \(0\leq k\leq n-2\), then \(G\) is \(k^*\)-extendable iff for every matching \(M\) in \(G\) of size \(t\) with \(0\leq t\leq k\), \(G- V(M)\) is \((k-t)^*\)-extendable.NEWLINENEWLINENEWLINEIn the last section of the paper a number of sufficient conditions are established and with the help of these results the author gets his main result: If \(G\) is a \((k+2)\)-extendable non-bipartite graph on \(2n\) vertices and if \(0\leq k\leq n-3\), then \(G\) is \(k^*\)-extendable. A converse of this theorem is not true.
reviewed by: Heinz-Joachim Presia
description: scientific article; zbMATH DE number 1657293