Article in press
Authors:
Mustapha Chellali
Department of Mathematic
University of Blida
B.P. 270, Blida, ALGERIA
email: m_chellali@yahoo.com
Teresa W. Haynes
Department of Mathematics and Statistics, East Tenessee State University
email: haynes@etsu.edu
Nacéra Meddah
LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida
email: meddahn11@yahoo.fr
Title:
Bounds on the $k$-conversion number
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-01-16 , Revised: 2024-07-31 , Accepted: 2024-08-02 , Available online: 2024-09-09 , https://doi.org/10.7151/dmgt.2559
Abstract:
We consider a graphical model of the spread of influence through social
networks, where the goal is to find a set of vertices in the network, such
that if this initial set is ``influenced'', then after the application of a
certain propagation process eventually every vertex in the graph will also be
influenced. In particular, we seek a minimum set of vertices to be initially
influenced and follow an iterative process, where for a fixed integer threshold
$k \ge0$, a vertex outside the influenced set becomes influenced if at least
$k$ of its neighbors are influenced. We determine bounds on the minimum number
of vertices required in such a set for every integer $k\ge0$ and focus our
study on the case for $k= 2$.
Keywords:
domination, irreversible $k$-threshold conversion, influence spread, conversion sets, target set selection process
References:
- X. Baogen, E.J. Cockayne, T.W. Haynes, S.T. Hedetniemi and Z. Shangchao, Extremal graphs for inequalities involving domination parameters, Discrete Math. 216 (2000) 1–10.
https://doi.org/10.1016/S0012-365X(99)00251-4 - E.J. Cockayne, B. Gamble and B. Shepherd, An upper bound for the $k$-domination number of a graph, J. Graph Theory 9 (1985) 533–534.
https://doi.org/10.1002/jgt.3190090414 - N. Chen, On the approximability of influence in social networks, SIAM J. Discrete Math. 23 (2009) 1400–1415.
https://doi.org/10.1137/08073617X - C.-Y. Chiang, L.-H. Huang and H.-G. Yeh, Target set selection problem for honeycomb networks, SIAM J. Discrete Math. 27 (2013) 310–328.
https://doi.org/10.1137/120868864 - C.-Y. Chiang, L.-H. Huang, B.-J. Li, J. Wu and H.-G. Yeh, Some results on the target set selection problem, J. Comb. Optim. 25 (2013) 702–715.
https://doi.org/10.1007/s10878-012-9518-3 - P.A. Dreyer, Applications and Variations of Domination in Graphs, PhD Thesis (Rutgers University, Piscataway, NJ, 2000).
- P.A. Dreyer Jr. and F.S. Roberts, Irreversible $k$-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion, Discrete Appl. Math. 157 (2009) 1615–1627.
https://doi.org/10.1016/j.dam.2008.09.012 - O. Favaron, A. Hansberg and L. Volkmann, On $k$-domination and minimum degree in graphs, J. Graph Theory 57 (2008) 33–40.
https://doi.org/10.1002/jgt.20279 - M.A. Fazli, M. Ghodsi, J. Habibi, P. Jalaly, V. Mirrokni and S. Sadeghian, On non-progressive spread of influence through social networks, Theoret. Comput. Sci. 550 (2014) 36–50.
https://doi.org/10.1016/j.tcs.2014.07.009 - J.F. Fink and M.S. Jacobson, $n$-domination in graphs, in: Graph Theory with Applications to Algorithms and Computer Science, Y. Alavi and A.J. Schwenk (Ed(s)), (Wiley, New York 1985) 282–300.
- J.F. Fink and M.S. Jacobson, On $n$-domination, $n$-dependence and forbidden subgraphs, in: Graph Theory with Applications to Algorithms and Computer Science, Y. Alavi and A.J. Schwenk (Ed(s)), (Wiley, New York 1985) 301–311.
- J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985) 287–293.
https://doi.org/10.1007/BF01848079 - A. Hansberg and L. Volkmann, Multiple domination, in: Topics in Domination in Graphs, T.W. Haynes, S.T. Hedetniemi and M.A. Henning (Ed(s)), Dev. Math. 64, (Springer, Cham, 2020) 151–203.
https://doi.org/10.1007/978-3-030-51117-3_6 - H. Jiang and H. Wan, Target set selection in Cartesian product graphs, Ars Combin. 147 (2019) 361–373.
- D. Kempe, J. Kleinberg and É. Tardos, Maximizing the spread of influence through a social network, in: Proc. 9th ACM SIGKDD Int. Conf., (Washington, D.C. 2003) 137–146.
https://doi.org/10.1145/956750.956769 - D. Kempe, J. Kleinberg and É. Tardos, Influential nodes in a diffusion model for social networks, in: Proc. 32nd Int. Colloq. Automata, Languages, and Programming (ICALP 2005), L. Caires, G.F. Italiano, L. Mateiro, C. Palamidessi and M. Yung (Ed(s)), Lecture Notes in Comput. Sci. 3580, (Springer, Berlin, Heidelberg, 2005) 1127–1138.
https://doi.org/10.1007/11523468_91 - W. McCuaig and B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749–762.
https://doi.org/10.1002/jgt.3190130610 - C.M. Mynhardt and J.L. Wodlinger, The $k$-conversion number of regular graphs, AKCE Int. J. Graphs Comb. 17 (2020) 955–965.
https://doi.org/10.1016/j.akcej.2019.12.016 - O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ. 38 (Providence, RI, 1962).
https://doi.org/10.1090/coll/038 - C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23–32.
https://doi.org/10.1002/jgt.3190060104 - B. Randerath and L. Volkmann, Characterization of graphs with equal domination and covering number, Discrete Math. 191 (1998) 159–169.
https://doi.org/10.1016/S0012-365X(98)00103-4 - B.A. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277–295.
https://doi.org/10.1017/S0963548300002042 - F.S. Roberts, Graph-theoretical problems arising from defending against bioterrorism and controlling the spread of fires, in: Proc. DIMACS/DIMATIA/Renyi Combinatorial Challenges Conf., (Piscataway, NJ 2006).
- C. Stracke and L. Volkmann, A new domination conception, J. Graph Theory 17 (1993) 315–323.
https://doi.org/10.1002/jgt.3190170306
Close