AbstractBinaryoperations on graphs are studied widely in graph theory ever since each ofthese operations has been introduced.The neighbourhood polynomial plays a vitalrole in describing the neighbourhood characteristics of the vertices of agraph. In this study neighbourhoodpolynomial of graphs arising from the operations like conjunctionand join ofcertain classes of graphs are calculated and tried to characterize the natureof neighbourhood polynomial.

Key words:Conjunction, Join, Neighbourhood PolynomialIntroductionTheneighbourhood polynomials of the graphs resulting from Cartesian product havebeen studied and some properties have been established in 3. 1.1. Theoperations on graphs in this studyTheoperation of conjunction ( ) on graphs was introduced by Weichsel in1963. For any two graphs and , it is denoted as and is defined as , two vertices are adjacent if adjacent to in and adjacent to in . Join of two graphs and isdenoted as . In join, , edge set consists of edges of and together with all edges joining every vertexof toevery vertices of .

Fornotations and terminology we follow 2.1.2. Neighbourhoodcomplex and polynomialA complex on a finite set isa collection ofsubsets of , closed under certain predefinedrestriction. Each set in iscalled the face of the complex.

In the neighbourhood complex ofa graph , , and faces are subsets of vertices thathave a common neighbour. In 1the neighbourhood polynomial of a graph , is defined as . For example consider with vertices . The neighbourhood complex of is Since the empty set trivially has acommon neighbour, each of the single vertices has a neighbour, the sets has two common neighbours (one is sufficient),but no three vertices have a common neighbour. The associated neighbourhoodpolynomial of is . Similarly, the neighbourhood polynomials of certain standardgraphs are as follows:1. – .

2. – .3. – .Inthis paper, neighbourhood polynomials for the graphs resulting from the binaryoperations of conjunction, join, and symmetric difference are calculated. Alsotried to characterize some properties of the neighbourhood polynomial of thegraph soformed.2.

Main Results 2.1 Conjunction of twographs and their Neighbourhood PolynomialsLemma2.1.1The neighbourhood polynomial of meshgraph is .

Proof.Considerthe mesh graph . In there are vertices. The empty set trivially has aneighbour and each of the single vertices has a neighbour.

Nowconsider the figure 1, Figure 1 Thetwo element subsets ; ; and ; have at least one common neighbour. Thethree element subsets having at least one common neighbour are and are the four element subsets having atleast one common neighbour.Thusfor , the neighbourhood polynomial is .Generally,for , .Corollary 2.

1.2The neighbourhood polynomial of is .Proof.We have, .

When we get, .Lemma 2.1.3Theneighbourhood polynomial of is, .Proof.Consider, .

From the definition of conjunction, forevery , we have . That is, there corresponds neighbours to every vertex of To find set of vertices having at leastone common neighbour, say , we compute, , of the four neighbouring vertices of . Since in there are vertices, in the neighbourhood complex of we have null set, single vertices, , two element subsets, three element subsets and four element subsets.On considering , for different and , it is verified that there are only distinct two element subsets of verticeshaving at least a common neighbour.Hence, .

Corollary 2.1.4Theneighbourhood polynomial of is, .

Proof.Let . Each of the vertices has neighbours. When , the neighbours of first vertices is same as that of later vertices. That is, we have to consider theneighbours of only , vertices are only needed to be considered(since, we are finding the distinct set of vertices having common neighbours).Following the same argument as in lemma 2.1.3, we get .

Remark.Theneighbourhood polynomial of is .Consider, Figure 2 Here,the each vertex of the set have same set of neighbours as that of and vice versa. Also for the vertices { and .Theneighbourhood polynomial is is .Lemma 2.1.

5Theneighbourhood polynomial of is Proof.Let . has vertices, vertices of isof degree and vertices of , and vertices of are of degree 2. Hence in , vertices are of degree , and vertices are of degree . The neighbourhood complex of consists of null vertex along with single vertices. The number of two elementsimplexes are , the three element simplexes count to and there are four element simplexes.

Also there is no setof five more vertices having a common neighbour in . Hencethe neighbourhood polynomial of is, .Corollary 2.1.6Theneighbourhood polynomial of is, .Proof.Let .

Then has vertices, of which vertices are of degree and vertices are of degree In , there are , two element subsets of vertices havingat least a common neighbour. When , first subset of two element vertices coincides with later two element subsets of vertices and subsets with two elements coincides with subsets of vertices. Thus we have, , two simplexes.

Also when , the neighbours of first set of vertices are same as that of later set of vertices. Hence the number of three andfour element subsets are and respectively. Thus for , .Theorem 2.1.

7If , then , .Proof.Let and . For any vertex , in , , which follows from the definition of is maximum, only if Consider the neighbourhood complex of .

The , vertices adjacent to , forms complexes with one element, twoelements, three elements, …, elements (since, these vertices have at least a common neighbour ) and also no vertices can have asa common neighbour. Thus in , there exists a maximal face withrespect to a vertex with maximum degree.Also we have, , which implies, , is the maximum cardinality of the facein the neighbourhood complex. Thus if , with , .

2.2Join of two graphs and their Neighbourhood Polynomials.Lemma 2.2.1Theneighbourhood polynomial of fan graph is .

Proof. The fan graph . consists of , along with edges joining every vertex of , to the single vertex of . Thus has vertices. Theneighbourhood complex , of is, .Fromthe neighbourhood complex of weget, .ExampleConsider , Figure 3 Fromthe definition of neighbourhood polynomial we have . Hence .

Lemma2.2.2The neighbourhood polynomial of is Proof.We have .

Let and . In , one vertex of the vertices, has neighbours and others has three neighbourseach.The neighbourhood complex of is, . That is, the neighbourhood complexconsists of empty set, which trivially having a common neighbour and subsets ofvertices with element, elements, elements, etc. up to elements, with cardinalities , respectively.Hence, the neighbourhood polynomial of is, Example Consider , Figure 4 . .Lemma 2.

2.3Let bea graph and bea graph of orders and respectively. Then isregular if and only if, .Proof.Assume isregular.

Let and . In , each vertex of isjoined to every vertex of of , in addition to the edges of and . Also since and are and respectively, every vertex and of are of degree and , respectively. Since isregular .Converselyassume, . , since is and is . .Theorem2.

2.4Let and be any two graphs of order and respectively. If isa graph, then, .

Proof.Since, and are any two graphs of order and respectively, in , there are vertices, such that every vertex of isjoined to every vertex of through an edge, in addition to the edges of and . Thus for every , has more neighbours in addition to that which has in and for every , has more neighbours in addition to that which has in .Bydefinition the neighbourhood complex of consists of the null set, single vertices, since each has a neighbour.

Also since , any two vertices either in orin has a common neighbour, also any combinationof and has a common neighbour. Thus the number of twoelement simplexes are .Onconsidering the number of simplexes with three elements, any vertices of both and has a common neighbour, any vertices of and any vertex of has a common neighbour. Similarly any vertex of and any vertices of has a common neighbour.

Thus there exists .Similarly,the number of four simplexes are , since any vertices of both and has a common neighbour, any vertices of either or and any vertex of either or has a common neighbour any two vertices of any two vertices of also have a common neighbour, for isa regular graph.Theargument continues for all simplexes of length .Hencethe neighbourhood polynomial of is, Theorem 2.2.

5The neighbourhood polynomial of isof degree .Proof.Let . In , every vertex is of degree and that in is . Also these vertices of are joined to every vertices of .

Hence in the degree of each vertex belonging to is and that belonging to is . Thus is regular graph of order . Thus the neighbourhood complex of consists of the simplexes as described in thetheorem 2.19, and since the maximum degree of is , no set of vertices have a common neighbour, the maximalsimplex is .

Hence the ) is .RemarkItfollows from the observations and theorems that, if where and are any two graphs of order and respectively, .3.Conclusion andfurther scopeThe neighbourhood polynomials ondifferent binary operations on graphs are obtained and neighbourhood polynomials of other binaryoperations on graphs are still to be obtained Reference1 JasonI. Brown, Richard J. Nowakowski, “The neighbourhood polynomial of a graph”,Australian journal of Combinatorics, Volume 42(2008), Pages 55-68. 2 G.SureshSingh, “Graph Theory”, PHI Learning Private Limited, New Delhi, 2010.

3 G.Suresh Singh, Sreedevi S.L.

‘Cartesian product and Neighbourhood Polynomial ofa Graph, International Journal of Mathematics Trends and Technology (IJMTT) –Volume 49 Number 3 September 2017