On maximizing private neighbors in graphs

Articles in Press

Document Type : Special issue of CCO to honor Odile Favaron

Authors

1 Emeritus Professor of Computer Science, Clemson University, Clemson, SC, USA

2 Emeritus Professor of Mathematics, Furman University, Greenville, SC, USA

Abstract

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.

Keywords

Main Subjects

References

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´as 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
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 17 June 2026

Files

Share

How to cite

Statistics