Neighbourly irregular graphs (Q1766370)

A connected graph \(G\) is said to be neighbourly irregular if no two adjacent vertices of \(G\) have the same degree. The authors state some elementary facts about neighbourly irregular graphs. Especially they note that any connected graph of order \(n\) can be made to be an induced subgraph of a neighbourly irregular graph of order at most \(\binom{n+1}{2}\). Let \(n \geq 3\) be any integer and \((n_1,n_2,\dots,n_k)\) be a partition of \(n\) with distinct parts \(n_j\). Then the complete \(k\)-partite graph \(K(n_1,n_2,\dots,n_k)\) is a neighbourly irregular graph of order \(n\), denoted by NI\(_{(n_1,n_2,\dots,n_k)}\). For any given \(n\), NI\(_{(n_1,n_2,\dots,n_k)}\) with the maximun size is characterized. For any \(G=\text{NI}_{(n_1,n_2,\dots,n_k)}\), the graphoidal covering number \(\gamma(G)\), the ply number \(p(G)\), the cardinality of a minimal covering edge family of \(G\) and the clique graph of \(G\) are determined explicitly. Remark: The assertion of Lemma 2.2 is incorrect.