Autor: Samodivkin, Vladimir - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: The bondage number of graphs: good and bad vertices
Autorzy:: Samodivkin, Vladimir
Powiązania:: https://bibliotekanauki.pl/articles/743054.pdf
Data publikacji:: 2008
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: bondage number
γ-bad/good vertex
Opis:: The domination number γ(G) of a graph G is the minimum number of vertices in a set D such that every vertex of the graph is either in D or is adjacent to a member of D. Any dominating set D of a graph G with |D| = γ(G) is called a γ-set of G. A vertex x of a graph G is called: (i) γ-good if x belongs to some γ-set and (ii) γ-bad if x belongs to no γ-set. The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater then γ(G). In this paper we present new sharp upper bounds for b(G) in terms of γ-good and γ-bad vertices of G.
Źródło:: Discussiones Mathematicae Graph Theory; 2008, 28, 3; 453-462
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

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ł

Informacja