Contents Online

# Pure and Applied Mathematics Quarterly

## Volume 18 (2022)

### Number 6

### Special issue in honor of Fan Chung

Guest editors: Paul Horn, Yong Lin, and Linyuan Lu

### A greedy algorithm for the connected positive influence dominating set in $k$-regular graphs

Pages: 2461 – 2478

DOI: https://dx.doi.org/10.4310/PAMQ.2022.v18.n6.a6

#### Authors

#### Abstract

For a graph $G=(V,E)$, a vertex subset $C \subseteq V$ is a connected positive influence dominating set of $G$ if every node $v$ in $V \setminus C$ has at least a fraction $\rho (0 \lt \rho \lt 1)$ of its neighbors in $C$ and the subgraph of $G$ induced by $C$ is connected. In this paper, let $G$ be a regular graph with degree $k$. We present a greedy algorithm to compute a connected positive influence dominating set in $G$, and it is proved that the approximation ratio of the algorithm is $2 + \ln (k^2 + 2k)$.

#### Keywords

connected positive influence dominating set, greedy algorithm, potential function

#### 2010 Mathematics Subject Classification

Primary 05C69. Secondary 68W25, 68W40.

This work was supported by the NSF of China (No. 11971146), by the NSF of Hebei Province (Nos. A2017403010, A2019205089 and A2019205092), and by the Graduate Innovation Grant Program of Hebei Normal University (No. CXZZSS2021045).

Received 25 June 2021

Received revised 28 March 2022

Accepted 5 April 2022

Published 29 March 2023