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 pathP is an edge joining two non-adjacent vertices of P . A path P is called a monophonicpath if it is a chordless path. A longest x- y monophonic path is called an x - y detourmonophonic path. A set S of vertices of G is a detour monophonic set of G if each vertexv of G lies on an x- y detour monophonic path, for some x and y in S. The minimumcardinality of a detour monophonic set of G is the detour monophonic number of G andis denoted by dm(G). A connected detour monophonic set of G is a detour monophonicset S such that the subgraph G[S] induced by S is connected. The minimum cardinalityof a connected detour monophonic set of G is the connected detour monophonic numberof G and is denoted by dmc(G). We determine bounds for dmc(G) and characterizegraphs which realize these bounds. It is shown that for positive integers r, d and k>= 6with r < d, there exists a connected graph G with monophonic radius r, monophonicdiameter d and dmc(G) = k. For each triple a, b, p of integers with 3<= a <= b <= p - 2,there is a connected graph G of order p, dm(G) = a and dmc(G) = b. Also, for every paira, b of positive integers with 3<= a <= b, there is a connected graph G with mc(G) = aand dmc(G) = b, where mc(G) is the connected monophonic number of G.