On maximizing private neighbors in graphs

Hedetniemi, Stephen T.; Rall, Douglas

doi:10.22049/cco.2026.31182.2771

تعداد نشریات	6
تعداد شماره‌ها	130
تعداد مقالات	1,624
تعداد مشاهده مقاله	1,871,761
تعداد دریافت فایل اصل مقاله	1,732,133

	On maximizing private neighbors in graphs
Communications in Combinatorics and Optimization
مقاله 17، دوره 11، شماره 4، اسفند 2026، صفحه 1265-1279 اصل مقاله (454.52 K)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2026.31182.2771
نویسندگان
Stephen T. Hedetniemi¹؛ Douglas Rall^* ²
¹Emeritus Professor of Computer Science, Clemson University, Clemson, SC, USA
²Emeritus Professor of Mathematics, Furman University, Greenville, SC, USA
چکیده
Given a set $U \subset V$ of vertices in a graph $G = (V, E)$, a {\it private neighbor with respect to the set $U$} is any vertex $w \in V$ having precisely one neighbor, say $v$, in $U$. If $w \in V - U$, then $w$ is called an {\it external private neighbor} of $v$ with respect to $U$. If $w \in U$ then $w$ is called an {\it internal private neighbor} of $v$ with respect to $U$. We also add one special case: if $w \in U$ and $N(w) \cap U = \emptyset$, then we say that $w$ is a {\it self private neighbor} with respect to $U$. By definition, a self private neighbor with respect to $U$ is an isolated vertex in the subgraph of $G$ induced by $U$. In this paper we consider the general problems of trying to find sets of vertices which maximize the number of private neighbors of specific types in a graph. In the process of doing this we define several new maximization parameters of graphs which generalize some known and well-studied parameters of graphs relating to vertex and edge independence, domination and irredundance in graphs.
کلیدواژه‌ها
private neighbor؛ irredundance؛ domination

مراجع
1] P.J. Bernhard, S.T. Hedetniemi, and D.P. Jacobs, Efficient sets in graphs, Discrete Appl. Math. 44 (1993), no. 1-3, 99–108. https://doi.org/10.1016/0166-218X(93)90225-D [2] B. Bollobás and E.J. Cockayne, Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory 3 (1979), no. 3, 241–249. https://doi.org/10.1002/jgt.3190030306 [3] K. Cameron, Induced matchings, Discrete Appl. Math. 24 (1989), no. 1-3, 97–102. https://doi.org/10.1016/0166-218X(92)90275-F [4] E.J. Cockayne, Generalized irredundance in graphs: hereditary properties and Ramsey numbers, J. Combin. Math. Combin. Comput. 31 (1999), 15–32. [5] E.J. Cockayne, B.L. Hartnell, S.T. Hedetniemi, and R.C. Laskar, Perfect domination in graphs, J. Combin. Inform. System Sci. 18 (1993), 136–148. [6] E.J. Cockayne, S.T. Hedetniemi, and D.J. Miller, Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull. 21 (1978), no. 4, 461–468. https://doi.org/10.4153/CMB-1978-079-5. [7] J.E. Dunbar, F.C. Harris Jr, S.M. Hedetniemi, S.T. Hedetniemi, A.A. McRae, and R.C. Laskar, Nearly perfect sets in graphs, Discrete Math. 138 (1995), no. 1-3, 229–246. https://doi.org/10.1016/0012-365X(94)00205-W 8] A.M. Farley and N. Schacham, Senders in broadcast networks: Open irredundancy in graphs, Congr. Numer. 38 (1983), 47–57. [9] M. Fellows, G. Fricke, S. Hedetniemi, and D. Jacobs, The private neighbor cube, SIAM J. Discrete Math. 7 (1994), no. 1, 41–47. https://doi.org/10.1137/S0895480191199026 [10] S. Finbow, Generalisations of irredundance in graphs, Ph.D. thesis, University of Victoria, Canada, 3800 Finnerty Rd, Victoria, BC V8P 5C2, Canada, 2003. [11] J.F. Fink and M.S. Jacobson, $n$-domination in graphs, Graph theory with applications to algorithms and computer science (New York), John Wiley and Sons, 1985, pp. 283–300. [12] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in Graphs: Core Concepts, Springer, 2023. [13] J.T. Hedetniemi, K.D. Hedetniemi, S.M. Hedetniemi, and S.T. Hedetniemi, 1, 2-efficiency in grid graphs, Utilitas Math. 124 (2025), 171–187. https://doi.org/10.61091/um124-11 [14] S.M. Hedetniemi, S.T. Hedetniemi, and D.P. Jacobs, Private domination: Theory and algorithms, Congr. Numer. 79 (1990), no. 147-157, 3–3. [15] S.T. Hedetniemi, A.A. McRae, and R. Mohan, The private neighbor concept, Structures of Domination in Graphs, vol. 66, Springer, 2012, pp. 183–218. https://doi.org/10.1007/978-3-030-58892-2_7 [16] W.F. Klostermeyer and J.L. Goldwasser, Total perfect codes in grid graphs, Bull. Inst. Comb. Appl. 46 (2006), 61–68. [17] C.M. Mynhardt and A. Roux, Irredundance, Structures of domination in graphs, vol. 66, Springer, 2020, pp. 135–181. https://doi.org/10.1007/978-3-030-58892-2_6
آمار تعداد مشاهده مقاله: 318 تعداد دریافت فایل اصل مقاله: 239

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

آمار

On maximizing private neighbors in graphs