The total detour monophonic number of a graph.

Authors

  • A. P. Santhakumaran Hindustan University.
  • P. Titus University College of Engineering Nagercoil.
  • K. Ganesamoorthy Anna University.

DOI:

https://doi.org/10.4067/S0716-09172017000200209

Keywords:

Detour monophonic set, Detour monophonic number, Total detour monophonic set, Total detour monophonic number

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 total detour monophonic set of a graph G is a detour monophonic set S such that the subgraph induced by S has no isolated vertices. The minimum cardinality of a total detour monophonic set of G is the total detour monophonic number of G and is denoted by dmt(G). A total detour monophonic set of cardinality dmt(G) is called a dmt-set of G. We determine bounds for it and characterize graphs which realize the lower bound. 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 dmt(G) = k. For positive integers a, b such that 4 ≤ a ≤ b with b ≤ 2a, there exists a connected graph G such that dm(G) = a and dmt(G) = b. Also, if p, d and k are positive integers such that 2 ≤ d ≤ p - 2, 3 ≤ k ≤ p and p – d – k + 3 ≥ 0, there exists a connected graph G of order p, monophonic diameter d and dmt(G) = k.

Author Biographies

A. P. Santhakumaran, Hindustan University.

Department of Mathematics.

P. Titus, University College of Engineering Nagercoil.

Department of Mathematics.

K. Ganesamoorthy, Anna University.

Department of Mathematics, Coimbatore Institute of Technology. Government Aided Autonomous Institution Coimbatore.

References

BUCKLEY, F. (1990) Distance in Graphs. Redwood City, CA: Addison-Wesley.

DOURADO, M. C. (2008) Algorithmic Aspects of Monophonic Convexity. EN: Electronic Notes in Discrete Mathematics, 30. [s.l.: s.n.], 177-182.

HARARY, F. (1969) Graph Theory. [s.l.]: Addison-Wesley.

SANTHAKUMARAN, A. P. (2011) Monophonic Distance in Graphs. EN: Discrete Mathematics, Algorithms and Applications, 3(2). [s.l.: s.n.], 159-169.

SANTHAKUMARAN, A. P. (2012) A Note on “Monophonic Distance in Graphs”. EN: Discrete Mathematics, Algorithms and Applications, 4(2). [s.l.: s.n.].

TITUS, P. (2016) On the Detour Monophonic Number of a Graph. EN: Ars Combinatoria, 129. [s.l.: s.n.], 33-42.

TITUS, P. (2013) The Detour Monophonic Number of a Graph. EN: J. Combin. Math. Combin. Comput., 84. [s.l.: s.n.], 179-188.

TITUS, P. (2016) The Connected Detour Monophonic Number of a Graph. EN: TWMS Journal of Applied and Engineering Mathematics, 6(1). [s.l.: s.n.], 75-86.

Published

2017-06-02

How to Cite

[1]
A. P. Santhakumaran, P. Titus, and K. Ganesamoorthy, “The total detour monophonic number of a graph.”, Proyecciones (Antofagasta, On line), vol. 36, no. 2, pp. 209-224, Jun. 2017.

Issue

Section

Artículos

Most read articles by the same author(s)

1 2 > >>