The Connected Restrained Edge Monophonic Number of a Graph

Abstract

For a connected graph G = (V,E) of order at least two, a connected restrained edge monophonic set of a graph G is a restrained edge monophonic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected restrained edge monophonic set of G is the connected restrained edge monophonic number of G and is denoted by em_cr(G). We determine bounds for it and some general properties satisfied by this parameter are studied. For every pair a, b of positive integers with 4 ≤ a ≤ b, there is a connected graph G such that em_r(G) = a and em_cr(G) = b, where em_r(G) is the restrained edge monophonic number of G. Also, if n, d and k are positive integers such that 4 ≤ d ≤ n − 2, k ≥ 4 and n − d − k + 2 ≥ 0, then there exists a connected graph G of order n, monophonic diameter d and em_cr(G) = k.

Key words and phrases. restrained edge monophonic set, restrained edge monophonic number, connected restrained edge monophonic set, connected restrained edge monophonic number.

2000 Mathematics Subject Classification. 05C12