THE CONNECTED DETOUR MONOPHONIC NUMBER OF A GRAPH

Year 2016, Volume: 6 Issue: 1, 75 - 86, 01.06.2016

P. Titus A. P. Santhakumaran K. Ganesamoorthy

Abstract

For a connected graph G = V, E of order at least two, a chord of a path P is an edge joining two non-adjacent vertices of P. A path P is called a monophonic path if it is a chordless path. A longest x − y monophonic path is called an x − y detour monophonic path. A set S of vertices of G is a detour monophonic set of G if each vertex v of G lies on an x − y detour monophonic path, for some x and y in S. The minimum cardinality of a detour monophonic set of G is the detour monophonic number of G and is denoted by dm G . A connected detour monophonic set of G is a detour monophonic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected detour monophonic set of G is the connected detour monophonic number of G and is denoted by dmc G . We determine bounds for dmc G and characterize graphs which realize these bounds. It is shown that for positive integers r, d and k ≥ 6 with r < d, there exists a connected graph G with monophonic radius r, monophonic diameter d and dmc G = k. For each triple a, b, p of integers with 3 ≤ a ≤ b ≤ p − 2, there is a connected graph G of order p, dm G = a and dmc G = b. Also, for every pair a, b of positive integers with 3 ≤ a ≤ b, there is a connected graph G with mc G = a and dmc G = b, where mc G is the connected monophonic number of G.

Keywords

detour monophonic set, detour monophonic number, connected detour monophonic set, connected detour monophonic number

References

• Buckley, F. and Harary. F., (1990), Distance in Graphs, Addison-Wesley, Redwood City, CA.
• Chartrand, G., Escuadro, H. and Zhang, P., (2005), Detour Distance in Graphs, J. Combin. Math. Combin. Comput., 53, pp. 75-94.
• Chartrand, G., Johns, G.L. and Zhang, P., (2003), The Detour Number of a Graph, Utilitas Mathe- matica 64, pp. 97-113.
• Chartrand, G., Johns, G.L. and Zhang, P., (2004), On the Detour Number and Geodetic Number of a Graph, Ars Combinatoria, 72, pp. 3-15.
• Harary, F., (1969), Graph Theory, Addison-Wesley.
• Harary, F., Loukakis, E. and Tsouros, C., (1993), The Geodetic Number of a Graph, Math. Comput. Modeling, 17 (11), pp. 87-95.
• Santhakumaran, A.P. and Titus, P., (2011), Monophonic distance in graphs, Discrete Mathematics, Algorithms and Applications, Vol. 3, No. 2, pp. 159-169.
• Santhakumaran, A.P. and Titus, P., (2012),A Note on “Monophonic Distance in Graphs”, Discrete Mathematics, Algorithms and Applications, Vol. 4, No. 2, DOI: 10.1142/S1793830912500188.
• Santhakumaran, A.P. and Titus, P. and Ganesamoorthy, K., (2014), On the Monophonic Number of a Graph, J. Appl. Math. & Informatics Vol. 32, No. 1 - 2, pp. 255 - 266.
• Titus, P. and Ganesamoorthy, K., (2014), The Connected Monophonic Number of a Graph, Graphs and Combinatorics, 30, pp. 237245.
• Titus, P. and Ganesamoorthy, K., On the Detour Monophonic Number of a Graph, Ars Combinatoria, to appear.
• Titus, P., Ganesamoorthy, K. and Balakrishnan, P., (2013), The Detour Monophonic Number of a Graph, J. Combin. Math. Combin. Comput., 84, pp. 179-188.