The total detour monophonic number of a graph
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 s...
Guardado en:
| Autores principales: | , , |
|---|---|
| Lenguaje: | English |
| Publicado: |
Universidad Católica del Norte, Departamento de Matemáticas
2017
|
| Materias: | |
| Acceso en línea: | http://www.scielo.cl/scielo.php?script=sci_arttext&pid=S0716-09172017000200209 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | 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 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. |
|---|