2012/09/09 by K. Choudhary, Keerti Choudhary, Choudhary, K. +6
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1209.1842
arxiv created 2012/09/09 · arxiv updated 2012/09/11
Given a graph G, a dominating set D is a set of vertices such that any vertex in G has at least one neighbor (or possibly itself) in D. A k-dominating multiset Dk is a multiset of vertices such that any vertex in G has at least k vertices from its closed neighborhood in Dk when counted with multiplicity. In this paper, we utilize the approach developed by Clark and Suen (2000) and properties of binary matrices to prove a "Vizing-like" inequality on minimum k-dominating multisets of graphs G,H and the Cartesian product graph G \Box H. Specifically, denoting the size of a minimum k-dominating multiset as γk(G), we demonstrate that γk(G) γk(H) ≤ 2k γk(G \Box H).