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

摘要

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 g t r ( G ) of G and a total restrained geodetic set of G whose cardinality equals g t r ( 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 f t r ( S ) of S is the minimum cardinality of a forcing subset of S and the forcing total restrained geodetic number f t r ( 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 f t r ( G ) = a and g t r ( 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.