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

Abstract

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

Keywords

• geodetic
• total geodetic
• total restrained geodetic number
• forcing total restrained geodetic number