首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号