Minimal restrained monophonic sets in graphs

Abstract

For a connected graph G = (V, E) of order at least two, a restrained monophonic set S of a graph G is a monophonic set such that either S = V or the subgraph induced by V ?S has no isolated vertices. The minimum cardinality of a restrained monophonic set of G is the restrained monophonic number of G and is denoted by mr(G). A restrained monophonic set S of G is called a minimal restrained monophonic set if no proper subset of S is a restrained monophonic set of G. The upper restrained monophonic number of G, denoted by m+r (G), is defined as the maximum cardinality of a minimal restrained monophonic set of G. We determine bounds for it and find the upper restrained monophonic number of certain classes of graphs. It is shown that for any two positive integers a, b with 2 ? a ? b, there is a connected graph G with mr(G) = a and m+r (G) = b. Also, for any three positive integers a, b and n with 2 ? a ? n ? b, there is a connected graph G with mr(G) = a, m+r (G) = b and a minimal restrained monophonic set of cardinality n. If p, d and k are positive integers such that 2 ? d ? p ? 2, k ? 3, k 6= p ? 1 and p ? d ? k ? 0, then there exists a connected graph G of order p, monophonic diameter d and m+r (G) = k.