The total detour monophonic number of a graph.
DOI:
https://doi.org/10.4067/S071609172017000200209Keywords:
Detour monophonic set, Detour monophonic number, Total detour monophonic set, Total detour monophonic numberAbstract
For a connected graph G = (V, E) of order at least two, a chord of a path P is an edge joining two nonadjacent 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 dm_{t}(G). A total detour monophonic set of cardinality dm_{t}(G) is called a dm_{t}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 dm_{t}(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 dm_{t}(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 dm_{t}(G) = k.
References
BUCKLEY, F. (1990) Distance in Graphs. Redwood City, CA: AddisonWesley.
DOURADO, M. C. (2008) Algorithmic Aspects of Monophonic Convexity. EN: Electronic Notes in Discrete Mathematics, 30. [s.l.: s.n.], 177182.
HARARY, F. (1969) Graph Theory. [s.l.]: AddisonWesley.
SANTHAKUMARAN, A. P. (2011) Monophonic Distance in Graphs. EN: Discrete Mathematics, Algorithms and Applications, 3(2). [s.l.: s.n.], 159169.
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.], 3342.
TITUS, P. (2013) The Detour Monophonic Number of a Graph. EN: J. Combin. Math. Combin. Comput., 84. [s.l.: s.n.], 179188.
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.], 7586.
Published
How to Cite
Issue
Section

Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
 No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.