Regularizing irregular graphs (Q1310226)

A connected graph is highly irregular if the neighbours of every vertex all have distinct degrees. It is known that for each positive integer \(k\) there exists a unique unicyclic highly irregular graph \(U_ k\) of girth \(4k\) and order \(6k\) and maximum degree 3. The author shows that for each \(k\) there is an embedding of \(U_ k\) as an induced subgraph of a cubic self-centered graph \(H\) having connectivity and edge-connectivity 3. Moreover, the graph \(H\) that is constructed is such that its diameter is 4 if \(k=2\) and \(k+1\) otherwise. It is known that there exists a unique highly irregular \(d\times d\) bipartite graph \(B_ d\) with maximum degree \(d\). The author shows that for each \(d \geq 2\), the highly irregular graph \(B_ d\) can be embedded as induced subgraph in a \(d\)-regular self- centered graph with diameter 2 and connectivity and edge-connectivity both equal to \(d\).