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

Mengmeng He (School of Mathematical Sciences, Hebei Normal University, Shijiazhuang, China)

Bo Hou (School of Mathematical Sciences, Hebei Normal University, Shijiazhuang, China)

Wen Liu (School of Mathematical Sciences, Hebei Normal University, Shijiazhuang, China)

Weili Wu (Department of Computer Science, University of Texas at Dallas, Richardson, Tx., U.S.A.)

Ding-Zhu Du (Department of Computer Science, University of Texas at Dallas, Richardson, Tx., U.S.A.)

Suogang Gao (School of Mathematical Sciences, Hebei Normal University, Shijiazhuang, China)

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.

Full Text (PDF format)

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