## Abstract

For distinct vertices u and ν of a nontrivial connected graph G, the detour distance D(u, ν) between u and ν is the length of a longest u-ν path in C. For a vertex ν in G, define D+(ν) = max{D(u, ν) : u ∈ V(G) - {ν}}. A vertex u is called a hamiltonian neighbor of ν if D(u, ν) -D^{+}(ν). A vertex v is said to hamiltonian dominate a vertex u if u = ν or u is a hamiltonian neighbor of ν. A set 5 of vertices of G is called a hamiltonian dominating set if every vertex of G is hamiltonian dominated by some vertex in S. A hamiltonian dominating set of minimum cardinality is a minimum hamiltonian dominating set and this cardinality is the hamiltonian domination number γ_{H}(G) of G. It is shown that if T is a tree of order n ≥ 3 and p is the order of the periphery of T, then γ_{H}(T) = n - p. It is also shown that if G is a connected graph of order n ≥ 3, then γ_{H}(G) ≤ n - 2. Moreover, for every pair k, n of integers with 1 ≤ k ≤ n - 2, there exists a connected graph G of order n such that γ_{H}(G) = k. For a vertex ν in G, define D^{-} (ν) -min{D(u, ν) : u ∈ V(G) -{ν}}. A vertex u is called a detour neighbor of ν if D(u, ν) = D^{-} (ν). The detour domination number γ_{D}(G) of G is defined analogously to γ_{H}(G)- It is shown that every pair a, b of positive integers is realizable as the domination number and hamiltonian domination number, respectively, of some graph. For integers a, b ≥ 2, the corresponding result is shown for the detour domination number and hamiltonian domination number. The problem of determining those rational numbers r and s with 0 < r, s < 1 for which there exists a graph G of order n such that γ_{D}(G)/n = r and γ_{H}/(G)/n = s is discussed.

Original language | English |
---|---|

Pages (from-to) | 33-45 |

Number of pages | 13 |

Journal | Utilitas Mathematica |

Volume | 66 |

Publication status | Published - Nov 2004 |

Externally published | Yes |

## Keywords

- Detour distance
- Hamiltonian domination

## ASJC Scopus subject areas

- Statistics and Probability
- Statistics, Probability and Uncertainty
- Applied Mathematics