Abstract We study minimum degree conditions that guarantee that an ‐vertex graph is rigid in . For small values of , we obtain a tight bound: For , every ‐vertex graph with minimum degree at least is rigid in . For larger values of , we achieve an approximate result: For , every ‐vertex graph with minimum degree at least is rigid in . This bound is tight up to a factor of two in the coefficient of . As a byproduct of our proof, we also obtain the following result, which may be of independent interest: For , every ‐vertex graph with minimum degree at least has pseudoachromatic number at least ; namely, the vertex set of such a graph can be partitioned into subsets such that there is at least one edge between each pair of subsets. This is tight.
Krivelevich et al. (Thu,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: