AbstractRelationships among graph invariants such as the number of vertices, diameter, connectivity, maximum and minimum degrees, and regularity are being studied recently, motivated by their usefulness in the design of fault‐tolerant and low‐cost communication and interconnection networks. A graph is called a (d,c,r) graph if it has diameterd, connectivityc, and regularityr. The minimum number of vertices in (d, 1,3), (d,2,3), (d,3,3), and (d,c,c) graphs have been reported in the literature. In this paper, the minimum number of vertices in a (d,c,r) graph withr>cis determined, thereby exhausting all the possible choices of values ford,c, andr. Our proof is constructive and hence we get a collection of optimal (d,c,r) gra