2023/01/13 by Ghurumuruhan Ganesan, Ganesan, Ghurumuruhan
Computer Science · Economics, Econometrics and Finance · Mathematics · #Advanced Graph Theory Research #Artificial intelligence #Chromatic scale #Combinatorics #Computer science #Discrete mathematics #Enhanced Data Rates for GSM Evolution #FOS: Mathematics #Game Theory and Voting Systems #Generalization #Graph #Independent and identically distributed random variables #Mathematics #Probabilistic logic #Probability (math.PR) #Random graph #Random variable #Statistics
paper · pdf · doi:10.48550/arxiv.2301.05385
openalex publication_date 2023/01/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.