Detour domination in graphs

Gary Chartrand, Teresa W. Haynes, Michael A. Henning, Ping Zhang

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


For distinct vertices u and v of a nontrivial connected graph G, the detour distance D(u, v) between u and v is the length of a longest u-v path in G. For a vertex v ∈ V(G), define D-(v) = min{D(u, v) : u ∈ V(G) - {v}}. A vertex u (≠ v) is called a detour neighbor of v if D(u, v) = D -(v). A vertex u is said to detour dominate a vertex u if u = v or u is a detour neighbor of v. A set S of vertices of G is called a detour dominating set if every vertex of G is detour dominated by some vertex in S. A detour dominating set of G of minimum cardinality is a minimum detour dominating set and this cardinality is the detour domination number γD(G) . We show that if G is a connected graph of order n ≥ 3, then γD(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 γD(G) = k. It is also shown that for each pair a, b of positive integers, there is a connected graph G with domination number γ(G) = a and γD(G) = b.

Original languageEnglish
Pages (from-to)149-160
Number of pages12
JournalArs Combinatoria
Publication statusPublished - Apr 2004
Externally publishedYes


  • Detour distance
  • Detour domination

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'Detour domination in graphs'. Together they form a unique fingerprint.

Cite this