Neighborhood symmetric nsigraphs.[section]1. Introduction Unless mentioned or defined otherwise, for all terminology and notion in graph theory the reader is refer to [6]. We consider only finite, simple graphs free from selfloops. Let n [greater than or equal to] 1 be an integer. An ntuple ([a.sub.1], [a.sub.2], ..., [a.sub.n]) is symmetric, if [a.sub.k] = [a.sub.nk+1], 1 [less than or equal to] k [less than or equal to] n. Let [H.sub.n] = {([a.sub.1], [a.sub.2], ..., [a.sub.n]) : [a.sub.k] [member of] {+, }, [a.sub.k] = [a.sub.nk+1], 1 [less than or equal to] k [less than or equal to] n} be the set of all symmetric ntuples. Note that [H.sub.n] is a group under coordinate wise multiplication, and the order of [H.sub.n] is [2.sub.m], where m = [??]n/2[??]. A symmetric nsigraph (symmetric nmarked graph) is an ordered pair [S.sub.n] = (G, [sigma]) ([S.sub.n] = (G, [mu])), where G = (V, E) is a graph called the underlying graph of [S.sub.n] and [sigma] : E [right arrow] [H.sub.n] ([mu] : V [right arrow] [H.sub.n]) is a function. In this paper by an ntuple/nsigraph/nmarked graph we always mean a symmetric ntuple/symmetric nsigraph/symmetric nmarked graph. An ntuple ([a.sub.1], [a.sub.2], ..., [a.sub.n]) is the identity ntuple, if [a.sub.k] = +, for 1 [less than or equal to] k [less than or equal to] n, otherwise it is a nonidentity ntuple. In an nsigraph [S.sub.n] = (G, [sigma]) an edge labelled with the identity ntuple is called an identity edge, otherwise it is a nonidentity edge. Further, in an nsigraph [S.sub.n] = (G, [sigma]), for any [subset or equal to] E (G) the ntuple [sigma](A) is the product of the ntuples on the edges of A. In [11], the authors defined two notions of balance in nsigraph [S.sub.n] = (G, [sigma]) as follows (See also R. Rangarajan and P. S. K. Reddy t8l): Definition. Let [S.sub.n] = (G, [sigma]) be an nsigraph. Then, (i) [S.sub.n] is identity balanced (or ibalanced), if product of ntuples on each cycle of [S.sub.n] is the identity ntuple, and (ii) [S.sub.n] is balanced, if every cycle in [S.sub.n] contains an even number of nonidentity edges. Note. An ibalanced nsigraph need not be balanced and conversely. The following characterization of ibalanced nsigraphs is obtained in [11]. Proposition 1.1. [11] An nsigraph [S.sub.n] = (G, [sigma]) is ibalanced if, and only if, it is possible to assign ntuples to its vertices such that the ntuple of each edge uv is equal to the product of the ntuples of u and v. Let [S.sub.n] = (G, [sigma]) be an nsigraph. Consider the nmarking [mu] on vertices of [S.sub.n] defined as follows: each vertex v [member of] V, [mu](v) is the ntuple which is the product of the ntuples on the edges incident with v. Complement of [S.sub.n] is an nsigraph [bar.[S.sub.n]] = ([bar.G], [[sigma].supc]), where for any edge e = uv [member of] [bar.G], [[sigma].sup.c](uv) = [mu](u)/[mu](v). Clearly, [bar.[S.sub.n]] as defined here is an i balanced nsigraph due to Proposition 1.1. [13] In [11], the authors also have defined switching and cycle isomorphism of an nsigraph [S.sub.n] = (G,[sigma]) as follows: (See [7,9,10,1316]). Let [S.sub.n] = (G, [sigma]) and [S'.sub.n] = (G', [sigma]'), be two nsigraphs. Then [S.sub.n] and [S'.sub.n] are said to be isomorphic, if there exists an isomorphism [phi] : G [right arrow] G' such that if uv is an edge in [S.sub.n] with label ([a.sub.1], [a.sub.2], ..., [a.sub.n]) then [phi](u)[phi](v) is an edge in [S'.sub.n] with label ([a.sub.1], [a.sub.2], ..., [a.sub.n]). Given an nmarking [mu] of an nsigraph [S.sub.n] = (G, [sigma]), switching [S.sub.n] with respect to [mu] is the operation of changing the ntuple of every edge uv of [S.sub.n] by [mu](u)[sigma](uv)[mu](v). The nsigraph obtained in this way is denoted by [S.sub.[mu]]([S.sub.n]) and is called the [mu]switched nsigraph or just switched nsigraph. Further, an nsigraph [S.sub.n] switches to nsigraph [S'.sub.n] (or that they are switching equivalent to each other), written as [S.sub.n] ~ [S'.sub.n], whenever there exists an nmarking of [S.sub.n] such that [S.sub.[mu]]([S.sub.n]) [congruent to] [S'.sub.n]. Two nsigraphs [S.sub.n] = (G, [sigma]) and [S'.sub.n] = (G', [sigma]') are said to be cycle isomorphic, if there exists an isomorphism [phi] : G [right arrow] G' such that the ntuple [sigma](C) of every cycle C in [S.sub.n] equals to the ntuple [sigma]([phi])(C)) in [S'.sub.n]. We make use of the following known result. Proposition 1.2. [11] Given a graph G, any two nsigraphs with G as underlying graph are switching equivalent if, and only if, they are cycle isomorphic. [section]2. Neighborhood nsigraphs For any graph G, neighborhood graph N(G) of G is a graph on the same vertex set V(G), with two vertices are adjacent if, and only if, they have a common neighbor. Neighborhood graphs are also known as 2path graphs (See [1]). Further, a graph G is said to be neighborhood graph if G [congruent to] N(H). The neighborhood of a vertex v is the set of all vertices adjacent to v. Clearly, N(G) is the intersection graph of neighborhoods of G. Neighborhood graphs was first introduced by C. R. Cook M as [H.sub.2]graph of a graph. B. D. Acharya [2] introduced the notion as open neighborhood graph of a given graph as intersection graph of neighbors of vertices of G. Later F. Escalante et al. [5] introduced the notion of npath graphs as follows: For any integer n, the npath graph [(G).sub.n] of a graph G, as a graph on the same vertex set and two vertices are adjacent if, and only if, there exists a path of length n in G. Thus 2path graphs are nothing but neighborhood graph. Motivated by the existing definition of complement of an nsigraph, we extend the notion of neighborhood graphs to nsigraphs as follows: The neighborhood nsigraph N([S.sub.n]) of an nsigraph [S.sub.n] = (G, [sigma]) is an nsigraph whose underlying graph is N(G) and the ntuple of any edge uv in N([S.sub.n]) is [mu](u)[mu](v), where [mu] is the canonical nmarking of [S.sub.n]. Further, an nsigraph [S.sub.n] = (G, [sigma]) is called neighborhood nsigraph, if [S.sub.n] [congruent to] N([S'sub.n]) for some nsigraph [S'.sub.n]. The following result indicates the limitations of the notion of neighborhood nsigraph as introduced above, since the entire class of iunbalanced nsigraphs is forbidden to neighborhood nsigraphs. Proposition 2.1. For any nsigraph [S.sub.n] = (G, [sigma]), its neighborhood nsigraph N([S.sub.n]) is ibalanced. Proof. Since the ntuple of any edge uv in N([S.sub.n]) is [mu](u)/[mu](v), where [mu] is the canonical nmarking of [S.sub.n], by Proposition 1.1, N([S.sub.n]) is ibalanced. The following result is due to B. D. Acharya and M. N. Vartak [2] which gives a characterization of neighborhood graphs: Proposition 2.2. A graph G = (V, E), where V = {[v.sub.1], [v.sub.2], ..., [v.sub.p]} is a neighborhood graph if, and only if edges of G can be included in p complete subgraphs [H.sub.1], [H.sub.2], [H.sub.p], where the subgraphs can be indexed so that (i) [v.sub.i] [member of] [H.sub.i] and; (ii) [v.sub.i] [member of] [H.sub.j] if, and only if [v.sub.j] [member of] [H.sub.i]. Proposition 2.3. Suppose an nsigraph [S.sub.n] = (G, [sigma]) is a neighborhood nsigraph. Then [S.sub.n] is ibalanced and G is a neighborhood graph. Proof. Suppose that [S.sub.n] is a neighborhood nsigraph. That is there exists an nsigraph [S'.sub.n] = (G', [sigma]') such that N([S'.sub.n]) = [S.sub.n] and hence N(G') [congruent to] G. That is G is a neighborhood graph. Also, by Proposition 2.1, the neighborhood nsigraph of any nsigraph is ibalanced, it follows that N([S'.sub.n]) = [S.sub.n] is ibalanced. Problem 2.4. Characterize neighborhood nsigraphs. Proposition 2.5. For any two nsigraphs [S.sub.n] and [S'.sub.n] with the same underlying graph, their neighborhood nsigraphs are switching equivalent. The following results are due to R. C. Brigham and R. D. Dutton [3] which gives characterization of graphs for which N(G) [congruent to] G and N(G) [congruent to] G. Proposition 2.6. For a connected graph G, N(G) [congruent to] G if, and only if, G is either a complete graph or an odd cycle of order [greater than or equal to] 3. Proposition 2.7. For a graph G = (V, E), the following are equivalent: (i) N(G) [congruent to] [bar.G]; (ii) There is a permutation f of the vertex set V such that uv is an edge in G if, and only if, f (u) and f (v) have no common neighbor. For any positive integer k, the iterated neighborhood graph of G is defined as follows: [N.sup.0](G) = G,[N.sup.k] (G) = N ([N.sup.k1](G)). Proposition 2.8. For any graph G and any integer k [greater than or equal to] 1, the kthiterated neighborhood graph [N.sup.k](G) [congruent to] G if, and only if, N(G) [congruent to] G. The following result characterizes the family of nsigraphs satisfies [S.sub.n] ~ N([S.sub.n]). Proposition 2.9. A connected nsigraph [S.sub.n] = (G, a) satisfies [S.sub.n] = N([S.sub.n]) if, and only if, [S.sub.n] is ibalanced and G is either an odd cycle or a complete graph. Proof. Suppose [S.sub.n] ~ N([S.sub.n]). This implies, G [congruent to] N(G) and hence by Proposition 2.6, we see that the graph G is either an odd cycle or a complete graph. Now, if [S.sub.n] is any nsigraph with underlying graph is complete or is an odd cycle, Proposition 3 implies that N([S.sub.n]) is ibalanced and hence if [S.sub.n] is iunbalanced and its neighborhood nsigraph N([S.sub.n]) being ibalanced can not be switching equivalent to [S.sub.n] in accordance with Proposition 1.2. Therefore, [S.sub.n] must be ibalanced. Conversely, suppose that [S.sub.n] ibalanced nsigraph on a complete graph or an odd cycle. Then, since N([S.sub.n]) is ibalanced as per Proposition 2.1 and since G [congruent to] N(G) by Proposition 2.6, the result follows from Proposition 2.1 again. Proposition 2.10. For an nsigraph [S.sub.n] = (G, [sigma]), the following are equivalent: (i) N([S.sub.n]) = [S.sup.c.sub.n]; (ii) There is a permutation f of the vertex set V such that uv is an edge in G if, and only if, f(u) and f(v) have no common neighbor. Proof. Suppose that N([S.sub.n]) ~ [S.sup.c.sub.n]. Then clearly we have N(G) [congruent to] [bar.G]. Hence by Proposition 2.7, there is a permutation f of the vertex set V such that uv is an edge in G if, and only if, f(u) and f(v) have no common neighbor. Conversely, suppose that there is a permutation f of the vertex set V such that uv is an edge in G if, and only if, f(u) and f(v) have no common neighbor. Then again by Proposition 2.7, N(G) [congruent to] [bar.G]. Since both N([S.sub.n]) and [S.sup.c.sub.n] are balanced for any nsigraph [S.sub.n], the result follows by Proposition 1.2 again. [section]3. Switching equivalence of neighborhood nsigraphs and line nsigraphs The line graph L(G) of graph G has the edges of G as the vertices and two vertices of L(G) are adjacent if the corresponding edges of G are adjacent. The line nsigraph of an nsigraph [S.sub.n] = (G, [sigma]) is an nsigraph L([S.sub.n]) = (L(G), [sigma]'), where for any edge ee' in L([S.sub.n]), [sigma]'(ee') = [sigma](e)[sigma](e'). This concept was introduced by E. Sampatkumar et al. [12] Proposition 3.1. (E. Sampathkumar et al. [12]) For any nsigraph [S.sub.n] = (G,[sigma]), its line nsigraph L([S.sub.n]) is ibalanced. For any positive integer k, the kth iterated line nsigraph, [L.sup.k] ([S.sub.n]) of [S.sub.n] is defined as follows: [L.sup.0]([S.sub.n]) = [S.sub.n], [L.sup.k] ([S.sub.n]) = L([L.sup.k1]([S.sub.n])). Corollary 3.2. For any nsigraph [S.sub.n] = (G, [sigma]) and for any positive integer k, [L.sup.k]([S.sub.n]) is ibalanced. The following result due to B. D. Acharya [1] gives a characterization of graphs for which L(G) [congruent to] N(G). Proposition 3.3. (B. D. Acharya [1]) For a connected graph G = (V, E), L(G) = N(G) if and only if G satisfies the following conditions: (i) G is unicyclic and the cycle C of G is of odd length m=2n+1, n [greater than or equal to] 1. (ii) If G contains a vertex v not on the cycle then, d(v, C) [less than or equal to] 2. (iii) If there exists at least one vertex v not on the cycle C, with d(v, C) = 2, then C = [C.sub.3]. Further, all such vertices not on the cycle C and at a distance 2 from C have degree 1 and are adjacent to a unique point, say v, which is adjacent to exactly one vertex of C. (iv) If degrees of all the vertices are distinct, then C = [C.sub.3] and any vertex not on the cycle C, is at a distance 1 from C. (v) If the cycle C is of length more than 3 say C = [C.sub.m] with m=2n+1 then, there exists vertices [v.sub.i] and [v.sub.j] of C (not necessarily distinct) such that at least one of the two systems [S.sub.1] and [S.sub.2] given below, among the degrees [d.sub.k] of vertices [v.sub.k] [member of] C holds: S1: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. S2: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The following result gives a characterization of those nsigraphs whose neighborhood nsgraphs are switching equivalent to their line nsigraphs. Proposition 3.4. For any nsigraph [S.sub.n] = (G, a), N([S.sub.n]) = L([S.sub.n]) if, and only if, [S.sub.n] is an ibalanced nsigraph and satisfies conditions (i) to (iv) of Proposition 3.3. [section]4. Switching equivalence of neighborhood nsigraphs and jump nsigraphs The jump graph J(G) of a graph G = (V, E) is [bar.L(G)], the complement of the line graph L(G) of G (see [6]). We now give a characterization of graphs for which N(G) [congruent to] J(G). Proposition 4.1. The jump graph J(G) of a connected graph G is isomorphic to N(G), the neighborhood graph of G if, and only if, G is [C.sub.5]. Proof. Suppose G is a connected graph such that N(G) [congruent to] J(G). Hence number of vertices and number of edges are equal and so G must be unicyclic. Since J([C.sub.n]) is a cycle if, and only if, n = 5 and N([C.sub.n]) is either [C.sub.n] or two copies of [C.sub.n/2] according as n is odd or even, it follows that the cycle in G is [C.sub.5]. Now suppose that there exists a vertex in C5 of degree [greater than or equal to] 3, then the edge not on the cycle is adjacent to 3 vertices in J(G), where as the vertex in N(G) is adjacent two vertices of the cycle. Hence G [congruent to] [C.sub.5]. The converse part is obvious. The jump nsigraph of an nsigraph [S.sub.n] = (G, [sigma]) is an signed graph J(S) = (J(G), [sigma]'), where for any edge ee' in J([S.sub.n]), [sigma]'(ee') = [sigma](e)[sigma](e'). This concept was introduced by E. Sampathkumar et al.[11] Proposition 4.2. (E. Sampathkumar et al.[11]) For any nsigraph [S.sub.n] = (G, [sigma]), its jump nsigraph J([S.sub.n]) is ibalanced. For any positive integer k, the kth iterated jump nsigraph, [J.sup.k]([S.sub.n]) of [S.sub.n] is defined as follows: [J.sup.0]([S.sub.n]) = [S.sub.n], [J.sup.k]([S.sub.n]) = J([J.sup.k1]([S.sub.n])). Corollary 4.3. For any nsigraph [S.sub.n] = (G, [sigma]) and for any positive integer k, [J.sup.k] ([S.sub.n]) is ibalanced. We now give a characterization of nsigraphs whose jump nsigraphs are switching equivalent to their neighborhood nsigraphs. Proposition 4.4. A connected nsigraph [S.sub.n] = (G, [sigma]) satisfies N([S.sub.n]) [congruent to] J([S.sub.n]) if and only if [S.sub.n] is an nsigraph on [C.sub.5], cycle on 5 vertices. Proof. Suppose that N([S.sub.n]) ~ J([S.sub.n]). Then clearly N(G) [congruent to] J(G). Hence by Proposition 4.1, G must be [C.sub.5]. Conversely, suppose that [S.sub.n] is an nsigraph on [C.sub.5]. Then by Proposition 4.1, N(G) [congruent to] J(G). Since for any nsigraph [S.sub.n], both N([S.sub.n]) and J([S.sub.n]) are balanced, the result follows by Proposition 1.2. Acknowledgement The authors would like to acknowledge and extend their heartfelt gratitude to Sri. B. Premnath Reddy, Chairman, Acharya Institutes, for his vital encouragement and support. References [1] B. D. Acharya, Some contributions to the theorey of hypergraphs, graphioidal coveres and graphs, Ph. D. thesis, The Indian Institute of Technology, Bombay, 1975. [2] B. D. Acharya and M. N. Vartak, Open neighbourhood graphs, Research Report, 7(1973), Indian Institute of Technology, Bombay, India. [3] R. C. Brigham and R. D. Dutton, On neighborhood graphs, J. Combinatorics, Information & System Science, 12(1987), 7585. [4] C. R. Cook, Graphs associated with (0,1)arrays, The Univ. Iowa Themis Project Tech. Rep, 28(1970). [5] F. Escalante, L. Montejano and T. Rojno, A characterization of npath connected graphs and of graphs having nth root, J. Combin. Th, Ser. B, 16(1974), No. 3, 282289. [6] F. Harary, Graph Theory, AddisonWesley Publishing Co, 1969. [7] V. Lokesha, P. Siva Kota Reddy and S. Vijay, The triangular line nsigraph of a symmetric nsigraph, Advn. Stud. Contemp. Math., 19(2009), No. 1, 123129. [8] R. Rangarajan and P. Siva Kota Reddy, Notions of balance in symmetric nsigraphs, Proceedings of the Jangjeon Math. Soc, 11(2008), No. 2, 145151. [9] R. Rangarajan, P. Siva Kota Reddy and M. S. Subramanya, Switching Equivalence in Symmetric nSigraphs, Adv. Stud. Comtemp. Math, 18(2009), No. 1, 7985. [10] R. Rangarajan, P. Siva Kota Reddy and N. D. Soner, Switching equivalence in symmetric nsigraphsII, J. Orissa Math. Sco, 28(2009), 112. [11] E. Sampathkumar, P. Siva Kota Reddy, and M. S. Subramanya, Jump symmetric nsigraph, Proceedings of the Jangjeon Math. Soc, 11(2008), No. 1, 8995. [12] E. Sampathkumar, P. Siva Kota Reddy, and M. S. Subramanya, The Line nsigraph of a symmetric nsigraph, Southeast Asian Bull. Math, 34(2010), No. 5, 953958. [13] P. Siva Kota Reddy and B. Prashanth, Switching equivalence in symmetric nsigraphsI, Advances and Applications in Discrete Mathematics, 4(2009), No. 1, 2532. [14] P. Siva Kota Reddy, S. Vijay and B. Prashanth, The edge C4 nsigraph of a symmetric nsigraph, Int. Journal of Math. Sci. & Engg. Appls., 3(2009), No. 2, 2127. [15] P. Siva Kota Reddy, V. Lokesha and Gurunath Rao Vaidya, The Line nsigraph of a symmetric nsigraphII, Proceedings of the Jangjeon Math. Soc, 13(2010), No. 3, 305312. [16] P. Siva Kota Reddy, V. Lokesha and Gurunath Rao Vaidya, Switching equivalence in symmetric nsigraphsIII, Int. Journal of Math. Sci. & Engg. Appls, 5(2011), No. 1, 95101. P. Siva Kota Reddy ([dagger]), Gurunath Rao Vaidya ([double dagger]) and A. Sashi Kanth Reddy # ([dagger]) Department of Mathematics, Acharya Institute of Technology, Bangalore, 560090, India ([double dagger]) Department of Mathematics, Acharya Institute of Graduate Studies, Bangalore, 560090, India # Department of MCA, Acharya Institute of Technology, Bangalore, 560090, India Email: pskreddy@acharya.ac.in gurunathgvaidya@yahoo.co.in askr1985@gmail.com 

Reader Opinion