- Tytuł:
- Changing and Unchanging of the Domination Number of a Graph: Path Addition Numbers
- Autorzy:
- Samodivkin, Vladimir
- Powiązania:
- https://bibliotekanauki.pl/articles/32083856.pdf
- Data publikacji:
- 2021-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
domination number
path addition - Opis:
- Given a graph $G=(V, E)$ and two its distinct vertices $u$ and $v$, the $(u, v)$-$P_k$-addition graph of $G$ is the graph $G_{u,v,k−2}$ obtained from disjoint union of $G$ and a path $P_k : x_0, x_1,...,x_{k−1}, k ≥ 2$, by identifying the vertices $u$ and $x_0$, and identifying the vertices $v$ and $x_{k−1}$. We prove that $\gamma(G) − 1 ≤ \gamma(G_{u,v,k})$ for all $k ≥ 1$, and $\gamma(G_{u,v,k})>\gamma(G)$ when $k ≥ 5$. We also provide necessary and sufficient conditions for the equality $\gamma(G_{u,v,k})=\gamma(G)$ to be valid for each pair $u, v ∈ V(G)$. In addition, we establish sharp upper and lower bounds for the minimum, respectively maximum, $k$ in a graph $G$ over all pairs of vertices $u$ and $v$ in $G$ such that the $(u, v)$-$P_k$-addition graph of $G$ has a larger domination number than $G$, which we consider separately for adjacent and non-adjacent pairs of vertices.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2021, 41, 2; 365-379
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł