×

Neighbourly regular strength of a graph. (English) Zbl 1413.05315

Summary: A graph is said to be a neighbourly irregular graph (or simply an \(\mathrm{NI}\) graph) if no two adjacent vertices have the same degree. In this paper we introduce the neighbourly regular strength of a graph. Let \(G\) be a simple graph of order \(n\). Let \(\mathrm{NI}(G)\) denote the set of all \(\mathrm{NI}\) graphs in which \(G\) is an induced subgraph. The neighbourly regular strength of \(G\) is denoted by \(\mathrm{NRS}(G)\) and is defined as the minimum \(k\) for which there is an \(\mathrm{NI}\) graph \(\mathrm{NI}(G)\) of order \(n+k\) in \(\mathrm{NI}(G)\). We prove that the \(\mathrm{NRS}(G)\) is at most \(n-1\), with possible equality only if \(G\) is complete. In addition, we determine the \(\mathrm{NRS}\) for some well known graphs.

MSC:

05C75 Structural characterization of families of graphs
05C07 Vertex degrees