Bounds on the Connected Domination Number of Some Graph Operators

Author : Shaheena Azeez

Abstract : Connected domination extends classical domination by requiring the vertices of a dominating set to induce a connected subgraph. This additional structural condition is relevant to network design, monitoring, and communication systems in which connectivity among selected vertices is essential. This paper establishes bounds on the connected domination number of five graph operators: the line graph L(G), subdivision graph S(G), semi-total point graph R(G), quasi-total point graph Q(G), and total graph T(G). For a finite simple connected graph G, the bounds are expressed in terms of its order n, size m, diameter diam(G), radius rad(G), minimum degree δ(G), and matching number ν(G). For L(G), a diameter-based lower bound and a spanning-tree-based upper bound are obtained. Order based bounds are established for S(G), while bounds involving the matching number and order of G are derived for R(G). The bounds for Q(G) incorporate diameter, radius, and minimum degree. For T(G), an upper bound of n−1 and further bounds involving order, radius, size, and minimum degree are presented. These results provide a unified framework for examining connected domination under graph transformations and clarify how changes in adjacency influence the structure of connected dominating sets.

Keywords : Connected domination number, line graph, subdivision graph, semi-total point graph, quasi-total point graph, total graph.

Conference Name : International Conference on Mathematical Modeling in Physical and Life Sciences (ICMMPLS - 26)

Conference Place : Dubai, UAE

Conference Date : 5th Nov 2026