The forcing total restrained geodetic number and the total restrained geodetic number of a graph: Realizability and complexity

Abstract

Given two vertices u and v of a nontrivial connected graph G, the set I[u,v] consists all vertices lying on some u−v geodesic in G, including u and v. For S⊆V(G), the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S⊆V(G) is a total restrained geodetic set of G if I[S]=V(G) and the subgraphs induced by S and V(G)−S have no isolated vertex. The minimum cardinality of a total restrained geodetic set of G is the total restrained geodetic number gtr(G) of G and a total restrained geodetic set of G whose cardinality equals gtr(G) is a minimum total restrained geodetic set of G. A subset T of a minimum total restrained geodetic set S is a forcing subset for S if S is the unique minimum total restrained geodetic set of G containing T. The forcing total restrained geodetic number ftr(S) of S is the minimum cardinality of a forcing subset of S and the forcing total restrained geodetic number ftr(G) of G is the minimum forcing total restrained geodetic number among all minimum total restrained geodetic sets of G. In this article we determine all pairs a,b of integers such that ftr(G)=a and gtr(G)=b for some nontrivial connected graph G. Moreover, we show that the decision problem regarding that the total restrained geodetic number of a graph will be less than some positive integer r is NP-complete even when restricted to chordal graph.