On maximizing private neighbors in graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911258009141248 |
|---|---|
| author | Hedetniemi, Stephen T. Rall, Douglas F. |
| author_facet | Hedetniemi, Stephen T. Rall, Douglas F. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_07248 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On maximizing private neighbors in graphs Hedetniemi, Stephen T. Rall, Douglas F. Combinatorics 05C69 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. |
| title | On maximizing private neighbors in graphs |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/2511.07248 |