×

The connected total restrained geodetic domination number of a graph. (English) Zbl 1467.05199

Let \(G = (V, E)\) be a graph. A dominating set of a graph \(G\) is a subset \(S\) of \(V\) such that every vertex in \(V\setminus S\) is adjacent to a vertex of \(S\). The domination number of \(G\) is denoted by \(\gamma(G)\). A \(u-v\) path of length \(d(u,v)\) is called a \(u-v\) geodesic. A geodetic set of \(G\) is a set \(S \subseteq V\) such that every vertex of \(G\) is contained in a geodesic joining some pair of vertices of \(S\). The geodetic number \(g(G)\) of \(G\) is the minimum order of a geodetic set. A geodetic dominating set of \(G\) is a subset of \(V(G)\) which is both geodetic and dominating set of \(G\). The geodetic domination number of \(G\) is denoted by \(\gamma_g(G)\). A set \(S\) of vertices of a connected graph \(G\) is a restrained geodetic dominating set if \(S=V(G)\) or \(S\) is a geodetic dominating set and the subgraph \(G[V-S]\) induced by \(V-S\) has no isolated vertices. The restrained geodetic domination number of \(G\) is denoted by \(\gamma_{gr}(G)\). A set \(S\) of vertices of a connected graph \(G\) is a total restrained geodetic dominating set if either \(S=V(G)\) or \(S\) is a restrained geodetic dominating set and the subgraph \(G[S]\) induced by \(S\) has no isolated vertices. The total restrained geodetic domination number of \(G\) is denoted by \(\gamma_{grt}(G)\). A set \(S\) of vertices of a connected graph \(G\) is a connected total restrained geodetic dominating set if either \(S=V(G)\) or \(S\) is a total restrained geodetic dominating set and the subgraph \(G[S]\) induced by \(S\) is connected. The connected total restrained geodetic domination number of \(G\) is denoted by \(\gamma_{grtc}(G)\).
A vertex \(v\) is an extreme vertex in \(G\) if the subgraph induced by its neighbor is complete. A vertex \(v\) is a semi extreme vertex in \(G\) if the subgraph induced by its neighbor has full degree vertex in \(N(v)\).
The main results of the paper are:
1.) Each semi extreme vertex of a connected graph \(G\) belongs to every connected total restrained geodetic dominating set of \(G\). In particular if the set \(S\) of all semi extreme vertices is a connected total restrained geodetic dominating set, then \(S\) is the unique minimum connected total restrained geodetic dominating set of \(G\).
2.) Let \(G\) be a connected graph with cut vertices and let \(S\) be a connected total restrained geodetic dominating set of \(G\). If \(v\) is a cut vertex of \(G\), then every component of \(G-v\) contains an element of \(S\).
3.) For any non trivial tree \(T\), the set of all end vertices and support vertices of \(T\) is the unique minimum connected total restrained geodetic dominating set of \(T\).
4.) For a connected graph \(G\), \(\gamma_{grtc}(G)=2\) if and only if \(G=K_2\).
5.) For a connected graph \(G\), \(\gamma_{grtc}(G)=3\) if and only if \(\gamma_{grt}(G)=3\).
6.) If a connected graph \(G\) of order \(p\) has exactly one vertex of degree \(p-1\), then \(\gamma_{grtc}(G)=p\).
7.) For a pair \(a\), \(b\) of integers \(3<a<b\), there exists a connected graph \(G\) of order \(p\) such that \(\gamma_{grt}(G)=a\) and \(\gamma_{grtc}(G)=b\).
4.) For a connected graph \(G\), \(\gamma_{grtc}(G)=2\) if and only if \(G=K_2\).
5.) For a connected graph \(G\), \(\gamma_{grtc}(G)=3\) if and only if \(\gamma_{grt}(G)=3\).
6.) If a connected graph \(G\) of order \(p\) has exactly one vertex of degree \(p-1\), then \(\gamma_{grtc}(G)=p\).
7.) For a pair \(a\), \(b\) of integers \(3<a<b\), there exists a connected graph \(G\) of order \(p\) such that \(\gamma_{grt}(G)=a\) and \(\gamma_{grtc}(G)=b\).
8.) For any integer \(p\) with \(3\le p\), there exists a connected graph \(G\) of order \(p\), such that \(\gamma_{grt}(G)=\gamma_{grtc}(G)=p\). For any integer \(p\) with \(3\le p\), there exists a connected graph \(G\) of order \(p\), such that \(\gamma_{grt}(G)=\gamma_{grtc}(G)=p\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
90C35 Programming involving graphs or networks