2-limited broadcast domination in subcubic graphs

Michael A. Henning, Gary MacGillivray, Frank Yang

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

In this paper, we consider a limited version of the well-studied dominating broadcast function of a graph. For a graph G, a function f:V(G)→{0,1,2} is a 2-limited dominating broadcast if for each vertex u in G there exist a vertex v such that f(v)>0 and dG(u,v)≤f(v), where dG(u,v) denotes the distance between u and v in G. The cost of a 2-limited dominating broadcast f is the sum of the function values f(v) summed over all vertices v in G. The 2-limited broadcast domination number of G, denoted by γb,2(G), is the minimum cost of a 2-limited dominating broadcast in G. We observe that γb,2(G)≤γ(G), where γ(G) is the domination number of G. A graph is (C4,C6)-free if it does not contain a 4-cycle or a 6-cycle as an induced subgraph. We prove that if G is a cubic graph of order n that is (C4,C6)-free, then [Formula presented].

Original languageEnglish
Pages (from-to)691-706
Number of pages16
JournalDiscrete Applied Mathematics
Volume285
DOIs
Publication statusPublished - 15 Oct 2020

Keywords

  • 2-limited dominating broadcast function
  • Cubic graphs
  • Dominating set

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of '2-limited broadcast domination in subcubic graphs'. Together they form a unique fingerprint.

Cite this