THE CONNECTED DETOUR MONOPHONIC NUMBER OF A GRAPH

Abstract

For a connected graph G = V, E of order at least two, a chord of a path P is an edge joining two non-adjacent vertices of P. A path P is called a monophonic path if it is a chordless path. A longest x − y monophonic path is called an x − y detour monophonic path. A set S of vertices of G is a detour monophonic set of G if each vertex v of G lies on an x − y detour monophonic path, for some x and y in S. The minimum cardinality of a detour monophonic set of G is the detour monophonic number of G and is denoted by dm G . A connected detour monophonic set of G is a detour monophonic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected detour monophonic set of G is the connected detour monophonic number of G and is denoted by dmc G . We determine bounds for dmc G and characterize graphs which realize these bounds. It is shown that for positive integers r, d and k ≥ 6 with r