On the (M,D) number of a graph.

Keywords: Monophonic number, Domination number, Monophonic domination number, Geodetic domination number


For a connected graph G = (V, E), a monophonic set of G is a set M ⊆ V (G) such that every vertex of G is contained in a monophonic path joining some pair of vertices in M. A subset D of vertices in G is called dominating set if every vertex not in D has at least one neighbour in D. A monophonic dominating set M is both a monophonic and a dominating set. The monophonic, dominating, monophonic domination number m(G), γ(G), γm(G) respectively are the minimum cardinality of the respective sets in G. Monophonic domination number of certain classes of graphs are determined. Connected graph of order p with monophonic domination number p− 1 or p is characterised. It is shown that for every two intigers a, b ≥ 2 with 2 ≤ a ≤ b, there is a connected graph G such that γm(G) = a and γg(G) = b, where γg(G) is the geodetic domination number of a graph.

Author Biographies

J. John, Government College of Engineering, Tirunelveli.
Department of Mathematics.
P. Arul Paul Sudhahar, Rani Anna Government College for Women.
Department of Mathematics.
D. Stalin, Bharathiar University.
Research and Development Center.


F. Buckley and F. Harary, Distance in Graph, Addition-Wesley, Redwood City, CA (1990).

E. J. Cockayne, S. Goodman and S. T. Hedetniemi, A linear algorithm for the domination number of a tree, Inform press.Lett, 4, pp. 41-44, (1975).

Y. Caro and R. Yuster, Dominating a family of graphs with small connected graphs, Combin.Probab.Comput, 9, pp. 309-313, (2000).

Carmen Hernando, Tao Jiang, Merce Mora, Ignacio. M. Pelayo and Carlos Seara, On the Steiner, geodetic and hull number of graphs Discrete Mathematics, 293, pp. 139-154, (2005).

Esamel M. Paluga, Sergio R. Canoy, Jr., Monophonic numbers of the join and Composition of connected graphs Discrete Mathematics, 307, pp. 1146-1154, (2007).

Mitre C. Dourado, Fabio protti and Jayme. L. Szwarcfiter, Algorithmic Aspects of Monophonic Convexity,Electronic Notes in Discrete Mathematics, 30, pp. 177-182, (2008).

F. Harary, E. Loukakis, C. Tsouros, The geodetic number of a graph Math. Comput Modeling, 11, pp. 89-95, (1993).

A. Hansberg, L. Volkmann, On the Geodetic and Geodetic domination number of a graph, Discrete Mathematics 310, pp. 2140-2146, (2010).

J. John, S. Panchali, The upper monophonic number of a graph, International Journal of J. Math. Combin. 4, pp. 46-52, (2010).

How to Cite
J. John, P. A. P. Sudhahar, and D. Stalin, “On the (M,D) number of a graph.”, Proyecciones (Antofagasta, On line), vol. 38, no. 2, pp. 255-266, May 2019.