Distance Majorization Sets in Graphs

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

References

1. Chartrand, G. and Lesniak, L., (2004), Graphs and Digraphs (4th ed.), CRC Press, ISBN 978-1-58488- 390-6.
2. Buckley, F. and Harary, F.. (1990), Distance in Graphs, Addision-Wesley, Redwood City, CA.
3. West, D. W., (2001), Introduction to Graph Theory - Second edition, Prentice Hall.
4. Farrugia, A., (1999), Self-complementary graphs and generalisations: A comprehensive reference man- ual, University of Malta.
5. Harary, F. and Robinson, R. W., (1985), The Diameter of a Graph and its Complement, The American Mathematical Monthly, Vol. 92, No. 3, pp. 211-212.
6. Fisher, D. C., McKenna and Boyer, E. D., (1998), Hamiltonicity, diameter, domination, packing and biclique partitions of Mycielski’s graphs, Discrete Applied Mathematics, 84, pp. 93-105.