Strong Total Monophonic Problems in Product Graphs, Networks, and Its Computational Complexity. (8th September 2022) - Varghese, Eddith Sarah; Xavier, D. Antony; Alsinai, Ammar; Mathew, Deepa; Amirtha Raja, S. Arul; Ahmed, Hanan
Abstract : Let G be a graph with vertex set as V G and edge set as E G which is simple as well as connected. The problem of strong total monophonic set is to find the set of vertices T ⊆ V G, which contains no isolated vertices, and all the vertices in V G T lie on a fixed unique chordless path between the pair of vertices in T . The cardinality of strong total monophonic set which is minimum is defined as strong total monophonic number, denoted by s m t G . We proved the NP-completeness of strong total monophonic set for general graphs. The strong total monophonic number of certain graphs and networks is derived. If l, m, n are positive integers with 5 ≤ l ≤ m ≤ n and m ≤ 2 l − 1, then we can construct a connected graph G with strong monophonic number l and strong total monophonic number m .