Hamiltonian Domination in Graphs

Document Type

Article

Publication Date

11-1-2004

Description

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.

This document is currently not available here.

Share

COinS