MINIMAL RESTRAINED MONOPHONIC SETS IN GRAPHS

MINIMAL RESTRAINED MONOPHONIC SETS IN GRAPHS

A. P. Santhakumaran, T. Venkata raghu, K. Ganesamoorthy

[PDF]

Abstract

For a connected graph G = (V;E) of order at least two, a restrained mono- phonic 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 mono- phonic 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 mono- phonic number of G, denoted by m+r (G), is dened as the maximum cardinality of a minimal restrained monophonic set of G. We determine bounds for it and nd 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 mono- phonic 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.

Keywords

restrained monophonic set, restrained monophonic number, minimal re- strained monophonic set, upper restrained monophonic number.