Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647158 | Discrete Mathematics | 2015 | 8 Pages |
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
Štefko Miklavič, Primož Šparl,