Upper minus total domination in small-degree regular graphs

Hong Yan, Xiaoqi Yang, Erfang Shan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

14 Citations (Scopus)

Abstract

A function f : V (G) → { - 1, 0, 1 } defined on the vertices of a graph G is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. An MTDF f is minimal if there does not exist an MTDF g : V (G) → { - 1, 0, 1 }, f ≠ g, for which g (v) ≤ f (v) for every v ∈ V (G). The weight of an MTDF is the sum of its function values over all vertices. The minus total domination number of G is the minimum weight of an MTDF on G, while the upper minus domination number of G is the maximum weight of a minimal MTDF on G. In this paper we present upper bounds on the upper minus total domination number of a cubic graph and a 4-regular graph and characterize the regular graphs attaining these upper bounds.
Original languageEnglish
Pages (from-to)2453-2463
Number of pages11
JournalDiscrete Mathematics
Volume307
Issue number21
DOIs
Publication statusPublished - 6 Oct 2007

Keywords

  • Bounds
  • Minus total domination
  • Regular graph

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science

Cite this