An inequality that relates the size of a bipartite graph with its order and restrained domination number |
| |
Authors: | Ernst J Joubert |
| |
Institution: | 1. Department of Mathematics, University of Johannesburg, Auckland Park, Johannesburg?, 2006, South Africa
|
| |
Abstract: | Let \(G=(V,E)\) be a graph. A set \(S\subseteq 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 \(\gamma _{r}(G)\), is the smallest cardinality of a restrained dominating set of \(G\). Consider a bipartite graph \(G\) of order \(n\ge 4,\) and let \(k\in \{2,3,...,n-2\}.\) In this paper we will show that if \(\gamma _{r}(G)=k\), then \(m\le ((n-k)(n-k+6)+4k-8)/4\). We will also show that this bound is best possible. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|