Changing and unchanging of the domination number of a graph: path addition numbers

DOI10.7151/DMGT.2189MaRDI QIDQ2227098zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 10 February 2021

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://arxiv.org/abs/1801.04965

zbMATH Keywords

domination numberpath addition

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Given a graph $G=(V,E)$ and two its distinct vertices $u$ and $v$. The $(u,v)$-$P_k$-{em 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,\mathrm{..},x_{k-1}$, $kgeq2$, by identifying the vertices $u$ and $x_0$, and identifying the vertices $v$ and $x_{k-1}$. We prove that (a) $gamma(G)-1leqgamma(G_{u,v,k})$ for all $kgeq1$, and (b) $gamma(G_{u,v,k})>gamma(G)$ when $kgeq5$. We also provide necessary and sufficient conditions for the equality $gamma(G_{u,v,k})=gamma(G)$ to be valid for each pair $u,vinV(G)$. pair $u,vinV(G)$.

Review text

Let \(G\) be a graph and \(u\) and \(v\) two distinct vertices of \(G\). By \(G_{u,v,k-2}\) one denotes a graph obtained from \(G\) by adding a path \(ux_1x_2\dots x_{k-2}v\) of length \(k\) between \(u\) and \(v\). Set \(D\subseteq V(G)\) is a dominating set of \(G\) if every vertex from \(V(G)-D\) has a neighbor in \(D\). The domination number \(\gamma(G)\) is the minimum cardinality of a dominating set of \(G\). The present work is a study of the relation between \(\gamma(G)\) and \(\gamma(G_{u,v,k})\) for different \(k\). The minimum and maximum number \(k\) for which \(\gamma(G)<\gamma(G_{u,v,k})\) for arbitrary (adjacent or nonadjacent) \(u\) and \(v\) is also considered.

Recommendations

• scientific article; zbMATH DE number 26480
• Changing of the number of minimum dominating sets after edge addition: critical edges
• Changing and unchanging of the domination number of a graph
• On the domination number of some graphs
• Changing of the number of minimum dominating sets after edge addition: non critical edges

Cites work

• Bounds on the bondage number of a graph
• Common extremal graphs for three inequalities involving domination parameters
• Domination critical graphs
• Effect of edge-subdivision on vertex-domination in a graph
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1744072 (Why is no real title available?)
• Independent domination in graphs: A survey and recent results
• Maximal 3--vertex-critical graphs
• Strong equality of domination parameters in trees
• Vertex domination-critical graphs

Cited in

(4)

• Changing and unchanging of the domination number of a graph
• scientific article; zbMATH DE number 26480 (Why is no real title available?)
• Changing and unchanging of the connected domination number of a graph
• Changing of the number of minimum dominating sets after edge addition: critical edges

This page was built for publication: Changing and unchanging of the domination number of a graph: path addition numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227098)