Domination and independence subdivision numbers of graphs.(English)Zbl 0984.05066

A subset $$S$$ of the vertex set $$V(G)$$ of a graph $$G$$ is called dominating in $$G$$, if each vertex of $$G$$ either is in $$S$$, or is adjacent to a vertex of $$S$$. A set $$S\subseteq V(G)$$ is independent in $$G$$, if no two vertices of $$S$$ are adjacent in $$G$$. The minimum number of vertices of a dominating set in $$G$$ is the domination number $$\gamma(G)$$ of $$G$$, the maximum number of vertices of an independent set in $$G$$ is the independence number $$\beta(G)$$ of $$G$$. Arumugam has introduced the concept of domination subdivision number $$\text{sd}_\gamma(G)$$. This is the minimum number of edges which must be subdivided (everyone only once) in order to increases $$\gamma(G)$$. Analogously the authors introduce the independence subdivision number $$\text{sd}_\beta(G)$$ as the minimum number of edges which must be subdivided (again everyone only once) in order to increase $$\beta(G)$$. In the paper it is proved that, for any connected graph $$G$$ with $$n\geq 3$$ vertices and for any two adjacent vertices $$u$$, $$v$$ in it with degrees at least 2, the inequality $$\text{sd}_\gamma(G)\leq \text{deg}(u)+ \text{deg}(v)- 1$$ holds. This theorem implies two corollaries, for grid graphs and for regular graphs (in general). Further it is proved that $$\text{sd}_\beta(G)= m$$ for $$G$$ being the star with $$m$$ edges and otherwise $$1\leq \text{sd}_\beta(G)\leq 2$$. The graphs $$G$$ with $$\text{sd}_\beta(G)= 2$$ are characterized.

MSC:

 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C75 Structural characterization of families of graphs
Full Text: