Weighted Domination and Colouring in Random Graphs

arXiv2301.05385MaRDI QIDQ6423280FDOQ6423280

Publication date: 12 January 2023

Abstract: In the first part of this paper, we consider weighted domination in the case where the vertices of the complete graph on~(n) vertices are equipped with independent and identically distributed (i.i.d.) weights. We use the probabilistic iteration to determine sufficient conditions for maximizing the weighted domination probability. In the second part, we study a weighted generalization of the chromatic number and estimate the minimum number of colours needed to satisfy the constraints when the weights themselves are random. We show that the "extra" cost incurred for weighted colouring is small if the weights have sufficiently large moments. We also consider inhomogenous random graphs where the edge probabilities are not necessarily all same and obtain bounds for the chromatic number in terms of its averaged edge probabilities.

This page was built for publication: Weighted Domination and Colouring in Random Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6423280)