Abstract to characterize the nature of neighbourhood

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             


I'm Mary!

Would you like to get a custom essay? How about receiving a customized one?

Check it out