An inequality that relates the size of a bipartite graph with its order and restrained domination number

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted γr(G), is the smallest cardinality of a restrained dominating set of G. Consider a bipartite graph G of order n≥4, and let k∈{2,3,..,n-2}. In this paper we will show that if γr(G)=k, then m≤((n-k)(n-k+6)+4k-8)/4. We will also show that this bound is best possible.

Original languageEnglish
Pages (from-to)44-51
Number of pages8
JournalJournal of Combinatorial Optimization
Volume31
Issue number1
DOIs
Publication statusPublished - 1 Jan 2016

Keywords

  • Bipartite graph
  • Domination
  • Order
  • Restrained domination
  • Size

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'An inequality that relates the size of a bipartite graph with its order and restrained domination number'. Together they form a unique fingerprint.

Cite this