A note on domination and minus domination numbers in cubic graphs

Yaojun Chen, Edwin Tai Chiu Cheng, Chi To Ng, Erfang Shan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)

Abstract

Let G=(V,E) be a graph. A subset S of V is called a dominating set if each vertex of V-S has at least one neighbor in S. The domination number γ(G) equals the minimum cardinality of a dominating set in G. A minus dominating function on G is a function f:V→{-1,0,1} such that f(N[v])=∑u∈N[v] f(u)<1 for each v∈V, where N[v] is the closed neighborhood of v. The minus domination number of G is γ-(G)=min{∑v∈Vf(v)|f is a minus dominating function on G}. It was incorrectly shown in [X. Yang, Q. Hou, X. Huang, H. Xuan, The difference between the domination number and minus domination number of a cubic graph, Applied Mathematics Letters 16 (2003) 1089-1093] that there is an infinite family of cubic graphs in which the difference γ-γ- can be made arbitrary large. This note corrects the mistakes in the proof and poses a new problem on the upper bound for γ-γ- in cubic graphs.
Original languageEnglish
Pages (from-to)1062-1067
Number of pages6
JournalApplied Mathematics Letters
Volume18
Issue number9
DOIs
Publication statusPublished - 1 Sep 2005

Keywords

  • Cubic graphs
  • Domination number
  • Minus domination number

ASJC Scopus subject areas

  • Computational Mechanics
  • Control and Systems Engineering
  • Applied Mathematics
  • Numerical Analysis

Cite this