Target set selection in plane graphs

Haining Jiang; Haiyun Wan; Haining Jiang; Haiyun Wan

doi:10.3934/math.2026327

AIMS Mathematics

2026, Volume 11, Issue 3: 7934-7944. doi: 10.3934/math.2026327

Previous Article Next Article

Research article

Target set selection in plane graphs

Haining Jiang ^{1
,
,},
Haiyun Wan ²

1.
School of Mathematics and Statistics, Heze University, Heze 274015, China
2.
Department of Public Education, Heze Medical College, Heze 274015, China

Received: 03 December 2025 Revised: 02 March 2026 Accepted: 23 March 2026 Published: 25 March 2026
MSC : 05C10, 05C82

The target set selection (TSS) problem was initially proposed to study the spread of information, ideas, or influence in social networks. It has been used to model many problems arising in various practical applications. In this paper, we study the TSS problem for plane graphs. We provide a characterization of plane graphs $ G $ for which $ \min_3(G) = 3 $. Consequently, we show that the minimum degree of such plane graphs is at most 4.
- target set selection,
- plane graph
Citation: Haining Jiang, Haiyun Wan. Target set selection in plane graphs[J]. AIMS Mathematics, 2026, 11(3): 7934-7944. doi: 10.3934/math.2026327

Related Papers:

Abstract

The target set selection (TSS) problem was initially proposed to study the spread of information, ideas, or influence in social networks. It has been used to model many problems arising in various practical applications. In this paper, we study the TSS problem for plane graphs. We provide a characterization of plane graphs $ G $ for which $ \min_3(G) = 3 $. Consequently, we show that the minimum degree of such plane graphs is at most 4.

References

[1]	D. Kempe, J. Kleinberg, E. Tardos, Maximizing the spread of influence through a social network, In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003,137–146. https://doi.org/10.1145/956750.956769
[2]	O. Ben-Zwi, D. Hermelin, D. Lokshtanov, An exact almost optimal algorithm for target set selection in social networks, In: Proceedings of the 10th ACM Conference on Electronic Commerce, 2009,355–362. https://doi.org/10.1145/1566374.1566424
[3]	N. Chen, On the approximability of influence in social networks, SIAM J. Discr. Math., 23 (2009), 1400–1415. https://doi.org/10.1137/08073617X doi: 10.1137/08073617X
[4]	P. Domingos, M. Richardson, Mining the network value of customers, In: Proceedings of the Seventh International Conference on Knowledge Discovery and Data Mining, 2001, 57–66. https://doi.org/10.1145/502512.502525
[5]	M. S. Rahman, M. S. Ahsan, C. W. Chen, V. Varadarajan, A census-based genetic algorithm for target set selection problem in social networks, Neural Comput. Applic., 37 (2025), 23155–23183. https://doi.org/10.1007/s00521-025-11480-3 doi: 10.1007/s00521-025-11480-3
[6]	M. Dvoak, D. Knop, I. Schierreich, On the complexity of target set selection in simple geometric networks, Discr. Math. Theoret. Comput. Sci., 26 (2024), 200–226. https://doi.org/10.46298/dmtcs.11591 doi: 10.46298/dmtcs.11591
[7]	L. Guo, W. Ning, Connectivity and super connectivity of enhanced folded hypercube-like networks, Discr. Appl. Math., 369 (2025), 14–19. https://doi.org/10.1016/j.dam.2025.02.034 doi: 10.1016/j.dam.2025.02.034
[8]	L. Guo, X. Kong, Component edge connectivity of folded hypercube-likenetworks, Discr. Appl. Math., 378 (2026), 162–170. https://doi.org/10.1016/j.dam.2025.07.011 doi: 10.1016/j.dam.2025.07.011
[9]	E. Ackerman, O. Ben-Zwi, G. Wolfovitz, Combinatorial model and bounds for target set selection, Theoret. Comput. Sci., 411 (2010), 4017–4022. https://doi.org/10.1016/j.tcs.2010.08.021 doi: 10.1016/j.tcs.2010.08.021
[10]	Y. Gao, K. Cui, D. Orlando, C. Zhang, G. Liao, L. Zuo, Outlier detection enhancement in heterogeneous environments through a novel training set selection framework, IEEE Trans. Radar Syst., 2 (2024), 1160–1173. https://doi.org/10.1109/TRS.2024.3491795 doi: 10.1109/TRS.2024.3491795
[11]	T. Suzuki, K. Kimura, A. Suzuki, Y. Tamura, X. Zhou, Parameterized complexity of weighted target set selection, Theoret. Comput. Sci., 2025, 1051.
[12]	P. Flocchini, R. Královič, P. Ruzicka, N. Santoro, On time versus size for monotone dynamic monopolies in regular topologies, J. Discr. Algor., 2 (2003), 129–150. https://doi.org/10.1016/S1570-8667(03)00022-4 doi: 10.1016/S1570-8667(03)00022-4
[13]	E. Berger, Dynamic monopolies of constant size, J. Combin. Theory Ser. B, 83 (2001), 191–200. https://doi.org/10.1006/jctb.2001.2045 doi: 10.1006/jctb.2001.2045
[14]	M. Zaker, On dynamic monopolies of graphs with general thresholds, Discr. Math., 312 (2012), 1136–1143. https://doi.org/10.1016/j.disc.2011.11.038 doi: 10.1016/j.disc.2011.11.038
[15]	P. A. Dreyer, F. S. Roberts, Irreversible $k$-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion, Discr. Appl. Math., 157 (2009), 1615–1627. https://doi.org/10.1016/j.dam.2008.09.012 doi: 10.1016/j.dam.2008.09.012
[16]	K. Khoshkhah, H. Soltani, M. Zaker, On dynamic monopolies of graphs: the average and strict majority thresholds, Discr. Optim., 9 (2012), 77–83. https://doi.org/10.1016/j.disopt.2012.02.001 doi: 10.1016/j.disopt.2012.02.001
[17]	C. Y. Chiang, L. H. Huang, H. G. Yeh, Target set selection problem for honeycomb networks, SIAM J. Discr. Math., 27 (2013), 310–328. https://doi.org/10.1137/120868864 doi: 10.1137/120868864
[18]	S. S. Adams, Z. Brass, C. Stokes, D. S. Troxell, Irreversible $k$-threshold and majority conversion processes on complete multipartite graphs and graph products, Austr. J. Combin., 56 (2013), 47–60.
[19]	S. S. Adams, D. S. Troxell, S. L. Zinnen, Dynamic monopolies and feedback vertex sets in hexagonal grids, Comput. Math. Appl., 62 (2011), 4049–4057. https://doi.org/10.1016/j.camwa.2011.09.047 doi: 10.1016/j.camwa.2011.09.047
[20]	D. Peleg, Local majorities, coalitions and monopolies in graphs: A review, Theoret. Comput. Sci., 282 (2002), 231–257.
[21]	M. Chopin, A. Nichterlein, R. Niedermeier, M. Weller, Constant thresholds can make target set selection tractable, Theory Comput. Syst., 55 (2014), 61–83. https://doi.org/10.1007/s00224-013-9499-3 doi: 10.1007/s00224-013-9499-3
[22]	L. Keiler, C. V. G. C. Lima, A. K. Maia, R. Sampaio, Target set selection with maximum activation time, Discr. Appl. Math., 338 (2023), 199–217. https://doi.org/10.1016/j.dam.2023.06.004 doi: 10.1016/j.dam.2023.06.004
[23]	C. Y. Chiang, L. H. Huang, B. J. Li, J. Wu, H. G. Yeh, Some results on the target set selection problem, J. Comb. Optim., 25 (2011), 702–715. https://doi.org/10.1007/s10878-012-9518-3 doi: 10.1007/s10878-012-9518-3
[24]	P. Flocchini, E. Lodi, F. Luccio, L. Pagli, N. Santoro, Dynamic monopolies in tori, Discr. Appl. Math., 137 (2004), 197–212. https://doi.org/10.1016/S0166-218X(03)00261-0

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)