Article ID Journal Published Year Pages File Type
4647158 Discrete Mathematics 2015 8 Pages PDF
Abstract

A connected graph ΓΓ of even order is ℓℓ-extendable   if it is of order at least 2ℓ+22ℓ+2, contains a matching of size ℓℓ, and if every such matching is contained in a perfect matching of ΓΓ. A connected regular graph ΓΓ is a Deza graph  , if there exist integers λλ and μμ such that any two distinct vertices of ΓΓ have either λλ or μμ common neighbours. In this paper we study extendability of regular graphs of even order and diameter 2. In particular, we show that every such graph is 1-extendable and we classify 2-extendable Deza graphs of even order and diameter 2.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,