An overview of $(\kappa ,\tau )$-regular sets and their applications

Abstract

A ($\kappa$,$\tau$)-regular set is a vertex subset S inducing a $\kappa$-regular subgraph such that every vertex out of S has $\tau$ neighbors in S. This article is an expository overview of the main results obtained for graphs with ($\kappa$,$\tau$)-regular sets. The graphs with classical combinatorial structures, like perfect matchings, Hamilton cycles, efficient dominating sets, etc, are characterized by ($\kappa$,$\tau$)-regular sets whose determination is equivalent to the determination of those classical combinatorial structures. The characterization of graphs with these combinatorial structures are presented. The determination of ($\kappa$,$\tau$)-regular sets in a finite number of steps is deduced and the main spectral properties of these sets are described.

13 pages, 4 figures