Distance and Convexity Related Parameters in Graphs

Abstract

For a connected graph G of order n, a set S of vertices of G is called a double monophonic set of G if for each pair of vertices x; y in G there exist vertices u; v in S such that x; y lie on a u and#1048576; v monophonic path. The double monophonic number dm(G) of G is the minimum cardinality of a double monophonic set. Few general properties fulfilled by double monophonic sets have been studied.The double monophonic numbers of some standard graphs are evaluated. It has been proved that for every pair k; n of integers with 2 k n, there exists a connected graph G of order n such that dm(G) = k. A double monophonic set S in a connected graph G is called a minimal double monophonic set if no proper subset of S is a double monophonic set of G. The upper double monophonic number of G is the maximum cardinality of a minimal double monophonic set of G, and is denoted by dm+(G). The generalproperties satisfied by upper double monophonic sets have been studied. The upper double monophonic numbers of some standard graphs are evaluated. It is shown that for a connected graph G of order n, dm(G) = n if and only if dm+(G) = n. It is also shown that dm(G) = nand#1048576;1 if and only if dm+(G) = nand#1048576;1 for a non-complete graph G of order n with a vertex of degree n and#1048576; 1. For any two positive integers a; b with 2 a b, there exists a connected graph G such that dm(G) = a and dm+(G) = b. A double monophonic set S in a connected graph G is said to be connected if the subgraph G[S] induced by S is connected. The minimum cardinality of a connected double monophonic set of G is the connected double monophonic number of G, and is denoted by dmc(G). Some general properties fulfilled by connected double monophonic sets have been studied and the connected double monophonic numbers of some standard graphs are evaluated. It is shown that for a connected graph G of order n 2 the dmc(G) = 2 if and only if G = K2; and dmc(G) = n if and only if every vertex of G is either a cut-vertex or an extreme vertex.