Some results on domination number of the graph defined by two levels of the n-cube

2019/09/30 by Pandit, Yeshwant, Sravanthi, S. L., Dara, Suresh +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1910.00007

Abstract

Let [n] \choose k and [n] \choose l ( k > l ) where [n] = \1,2,3,...,n\ denote the family of all k-element subsets and l-element subsets of [n] respectively. Define a bipartite graph G_k,l = ([n] \choose k,[n] \choose l,E) such that two vertices S ε [n] \choose k and T ε [n] \choose l are adjacent if and only if T ⊂ S. In this paper, we give an upper bound for the domination number of graph G_k,2 for k > \lceil (n)/(2) \rceil and exact value for k=n-1.

Related

• The domination number of the graph defined by two levels of the n-cube, II
• On the equality of domination number and 2 -domination number
• Bipartite graphs with close domination and k-domination numbers
• A note on bipartite graphs whose [1, k]-domination number equal to their number of vertices
• Bounds on the 2-domination number