Partial domination in supercubic graphs

Csilla Bujtás, Michael A. Henning, Sandi Klavžar

Research output: Contribution to journalArticlepeer-review

Abstract

For some α with 0<α≤1, a subset X of vertices in a graph G of order n is an α-partial dominating set of G if the set X dominates at least α×n vertices in G. The α-partial domination number pdα(G) of G is the minimum cardinality of an α-partial dominating set of G. In this paper partial domination of graphs with minimum degree at least 3 is studied. It is proved that if G is a graph of order n and with δ(G)≥3, then [Formula presented]. If in addition n≥60, then [Formula presented], and if G is a connected cubic graph of order n≥28, then [Formula presented]. Along the way it is shown that there are exactly four connected cubic graphs of order 14 with domination number 5.

Original languageEnglish
Article number113669
JournalDiscrete Mathematics
Volume347
Issue number1
DOIs
Publication statusPublished - Jan 2024

Keywords

  • Cubic graph
  • Domination
  • Partial domination
  • Supercubic graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

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

Cite this