2015/07/11 by Tapas Kumar Mishra, Mishra, Tapas Kumar, Sudebkumar Prasant Pal +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1507.03160
openalex publication_date 2015/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce the notion of the \it strong (r,p) cover number χc(G,k,r,p) for k-uniform hypergraphs G(V,E), where χc(G,k,r,p) denotes the minimum number of r-colorings of vertices in V such that each hyperedge in E contains at least min(p,k) vertices of distinct colors in at least one of the χc(G,k,r,p) r-colorings. We derive the exact values of χc(Knk,k,r,p) for small values of n, k, r and p, where Knk denotes the complete k-uniform hypergraph of n vertices. We study the variation of χc(G,k,r,p) with respect to changes in k, r, p and n; we show that χc(G,k,r,p) is at least (i) χc(G,k,r-1,p-1), and, (ii) χc(G',k-1,r,p-1), where G' is any (n-1)-vertex induced sub-hypergraph of G. We establish a general upper bound for χc(Knk,k,r,p) for complete k-uniform hypergraphs using a divide-and-conquer strategy for arbitrary values of k, r and p. We also relate χc(G,k,r,p) to the number |E| of hyperedges, and the maximum \it hyperedge degree (dependency) d(G), as follows. We show that χc(G,k,r,p)≤ x for integer x>0, if |E|≤ (1)/(2)(\fracrk(t-1)k \binomrt-1)x , for any k-uniform hypergraph. We prove that a \it strong (r,p) cover of size x can be computed in randomized polynomial time if d(G)≤ (1)/(e)(\fracrk(p-1)k \binomrp-1)x-1.