The total detour monophonic number of a graph.
DOI:
https://doi.org/10.4067/S0716-09172017000200209Keywords:
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 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.
Downloads
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.
Downloads
Published
Issue
Section
License
-
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.