Neighbourly Regular Strength of a Graph

Selvam Avadayappan1, M. Muthuchelyam2
1Department of Mathematics, V.H.N.S.N.College, Virudhunagar — 626 001, India,
2Department of Mathematics, K.S.R.College of Engineering, Tiruchengode – 637 215, India.

Abstract

A graph is said to be a neighbourly irregular graph (or simply an 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 \(NI(G)\) denote the set of all NI graphs in which \(G\) is an induced subgraph. The neighbourly regular strength of \(G\) is denoted by \(NRS(G)\) and is defined as the minimum \(k\) for which there is an NI graph \(NI(G)\) of order \(n+k\) in \(NI(G)\). We prove that the \(NRS(G)\) is at most \(n-1\), with possible equality only if \(G\) is complete. In addition, we determine the \(NRS\) for some well-known graphs.