1 Computer Science, Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU2 Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU3 unknown4 Computer Science, Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU
We show that for a fixed r, the number of maximal r-regular induced subgraphs in any graph with n vertices is upper bounded by O(c(n)), where c is a positive constant strictly less than 2. This bound generalizes the well-known result of Moon and Moser, who showed an upper bound of 3(n/3) on the number of maximal independent sets of a graph on n vertices. We complement this upper bound result by obtaining an almost tight lower bound on the number of (possible) maximal r-regular induced subgraphs possible in a graph on n vertices. Our upper bound results are algorithmic. That is, we can enumerate all the maximal r-regular induced subgraphs in time O(c(n)n(O(1))). A related question is that of finding a maximum-sized r-regular induced subgraph. Given a graph G = (V, E) on n vertices, the Maximum r-Regular Induced Subgraph (M-r-RIS) problem asks for a maximum-sized subset of vertices, R subset of V, such that the induced subgraph on R is r-regular. As a by-product of the enumeration algorithm, we get a O(c(n)) time algorithm for this problem for any fixed constant r, where c is a positive constant strictly less than 2. Furthermore, we use the techniques and results obtained in the paper to obtain improved exact algorithms for a special case of the Induced Subgraph Isomorphism problem, namely, the Induced r-Regular Subgraph Isomorphism problem, where r is a constant, the delta-Separating Maximum Matching problem and the Efficient Edge Dominating Set problem.
S I a M Journal on Discrete Mathematics, 2012, Vol 26, Issue 4, p. 1758-1780