Distance Majorization Sets in Graphs

Distance Majorization Sets in Graphs

R.Sundareswaran, V.Swaminathan

[PDF]

Abstract

Let G =(V,E) be a simple graph. A subset D of V (G) is said to be a distance majorization set (or dm -set) if for every vertex u ∈ V − D, there exists a vertex v ∈ D such that d(u, v) ≥ deg(u)+ deg(v). The minimum cardinality of a dm -set is called the distance majorization number of G (or dm -number of G) and is denoted by dm(G), Since the vertex set of G is a dm -set, the existence of a dm -set in any graph is guaranteed. In this paper, we find the dm -number of standard graphs like Kn,K1,n,Km,n,Cn,Pn, compute bounds on dm− number and dm-number of self complementary graphs and mycielskian of graphs.

 

Keywords

Distance, Diameter, Degree