Domination parameters of a graph with added vertex
Maciej Zwierzchowski
Abstract
Maciej Zwierzchowski
Abstract
Let \(G=(V,E)\) be a graph. A subset \(D\subseteq V\) is a total dominating set of \(G\) if for every vertex \(y\in V\) there is a vertex \(x\in D\) with \(xy\in E\). A subset \(D\subseteq V\) is a strong dominating set of \(G\) if for every vertex \(y\in V-D\) there is a vertex \(x\in D\) with \(xy\in E\) and \(\deg _{G}(x)\geq\deg _{G}(y)\). The total domination number \(\gamma _{t}(G)\) (the strong domination number \(\gamma_{S}(G)\)) is defined as the minimum cardinality of a total dominating set (a strong dominating set) of \(G\). The concept of total domination was first defined by Cockayne, Dawes and Hedetniemi in 1980 [Cockayne E. J., Dawes R. M., Hedetniemi S. T.: Total domination in graphs. Networks 10 (1980), 211–219], while the strong domination was introduced by Sampathkumar and Pushpa Latha in 1996 [Pushpa Latha L., Sampathkumar E.: Strong weak domination and domination balance in a graph. Discrete Mathematics 161 (1996), 235–242]. By a subdivision of an edge \(uv\in E\) we mean removing edge \(uv\), adding a new vertex \(x\), and adding edges \(ux\) and \(vx\). A graph obtained from \(G\) by subdivision an edge \(uv\in E\) is denoted by \(G\oplus u_{x}v_{x}\). The behaviour of the total domination number and the strong domination number of a graph \(G\oplus u_{x}v_{x}\) is developed.
A significance statement is not available in the OpenAlex record.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
Let \(G=(V,E)\) be a graph. A subset \(D\subseteq V\) is a total dominating set of \(G\) if for every vertex \(y\in V\) there is a vertex \(x\in D\) with \(xy\in E\). A subset \(D\subseteq V\) is a strong dominating set of \(G\) if for every vertex \(y\in V-D\) there is a vertex \(x\in D\) with \(xy\in E\) and \(\deg _{G}(x)\geq\deg _{G}(y)\). The total domination number \(\gamma _{t}(G)\) (the strong domination number \(\gamma_{S}(G)\)) is defined as the minimum cardinality of a total dominating set (a strong dominating set) of \(G\). The concept of total domination was first defined by Cockayne, Dawes and Hedetniemi in 1980 [Cockayne E. J., Dawes R. M., Hedetniemi S. T.: Total domination in graphs. Networks 10 (1980), 211–219], while the strong domination was introduced by Sampathkumar and Pushpa Latha in 1996 [Pushpa Latha L., Sampathkumar E.: Strong weak domination and domination balance in a graph. Discrete Mathematics 161 (1996), 235–242]. By a subdivision of an edge \(uv\in E\) we mean removing edge \(uv\), adding a new vertex \(x\), and adding edges \(ux\) and \(vx\). A graph obtained from \(G\) by subdivision an edge \(uv\in E\) is denoted by \(G\oplus u_{x}v_{x}\). The behaviour of the total domination number and the strong domination number of a graph \(G\oplus u_{x}v_{x}\) is developed.
Key concepts: Mathematics, Vertex (graph theory), Combinatorics, Graph, Discrete mathematics