Printer Friendly

Neighborhood symmetric n-sigraphs.

[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 self-loops.

Let n [greater than or equal to] 1 be an integer. An n-tuple ([a.sub.1], [a.sub.2], ..., [a.sub.n]) is symmetric, if [a.sub.k] = [a.sub.n-k+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.n-k+1], 1 [less than or equal to] k [less than or equal to] n} be the set of all symmetric n-tuples. 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 n-sigraph (symmetric n-marked 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 n-tuple/n-sigraph/n-marked graph we always mean a symmetric n-tuple/symmetric n-sigraph/symmetric n-marked graph.

An n-tuple ([a.sub.1], [a.sub.2], ..., [a.sub.n]) is the identity n-tuple, if [a.sub.k] = +, for 1 [less than or equal to] k [less than or equal to] n, otherwise it is a non-identity n-tuple. In an n-sigraph [S.sub.n] = (G, [sigma]) an edge labelled with the identity n-tuple is called an identity edge, otherwise it is a non-identity edge.

Further, in an n-sigraph [S.sub.n] = (G, [sigma]), for any [subset or equal to] E (G) the n-tuple [sigma](A) is the product of the n-tuples on the edges of A.

In [11], the authors defined two notions of balance in n-sigraph [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 n-sigraph. Then,

(i) [S.sub.n] is identity balanced (or i-balanced), if product of n-tuples on each cycle of [S.sub.n] is the identity n-tuple, and

(ii) [S.sub.n] is balanced, if every cycle in [S.sub.n] contains an even number of non-identity edges. Note. An i-balanced n-sigraph need not be balanced and conversely.

The following characterization of i-balanced n-sigraphs is obtained in [11].

Proposition 1.1. [11] An n-sigraph [S.sub.n] = (G, [sigma]) is i-balanced if, and only if, it is possible to assign n-tuples to its vertices such that the n-tuple of each edge uv is equal to the product of the n-tuples of u and v.

Let [S.sub.n] = (G, [sigma]) be an n-sigraph. Consider the n-marking [mu] on vertices of [S.sub.n] defined as follows: each vertex v [member of] V, [mu](v) is the n-tuple which is the product of the n-tuples on the edges incident with v. Complement of [S.sub.n] is an n-sigraph [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 n-sigraph due to Proposition 1.1. [13]

In [11], the authors also have defined switching and cycle isomorphism of an n-sigraph [S.sub.n] = (G,[sigma]) as follows: (See [7,9,10,13-16]).

Let [S.sub.n] = (G, [sigma]) and [S'.sub.n] = (G', [sigma]'), be two n-sigraphs. 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 n-marking [mu] of an n-sigraph [S.sub.n] = (G, [sigma]), switching [S.sub.n] with respect to [mu] is the operation of changing the n-tuple of every edge uv of [S.sub.n] by [mu](u)[sigma](uv)[mu](v). The n-sigraph obtained in this way is denoted by [S.sub.[mu]]([S.sub.n]) and is called the [mu]-switched n-sigraph or just switched n-sigraph.

Further, an n-sigraph [S.sub.n] switches to n-sigraph [S'.sub.n] (or that they are switching equivalent to each other), written as [S.sub.n] ~ [S'.sub.n], whenever there exists an n-marking of [S.sub.n] such that [S.sub.[mu]]([S.sub.n]) [congruent to] [S'.sub.n].

Two n-sigraphs [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 n-tuple [sigma](C) of every cycle C in [S.sub.n] equals to the n-tuple [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 n-sigraphs with G as underlying graph are switching equivalent if, and only if, they are cycle isomorphic.

[section]2. Neighborhood n-sigraphs

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 2-path 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 n-path graphs as follows: For any integer n, the n-path 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 2-path graphs are nothing but neighborhood graph.

Motivated by the existing definition of complement of an n-sigraph, we extend the notion of neighborhood graphs to n-sigraphs as follows: The neighborhood n-sigraph N([S.sub.n]) of an n-sigraph [S.sub.n] = (G, [sigma]) is an n-sigraph whose underlying graph is N(G) and the n-tuple of any edge uv in N([S.sub.n]) is [mu](u)[mu](v), where [mu] is the canonical n-marking of [S.sub.n]. Further, an n-sigraph [S.sub.n] = (G, [sigma]) is called neighborhood n-sigraph, if [S.sub.n] [congruent to] N([S'sub.n]) for some n-sigraph [S'.sub.n]. The following result indicates the limitations of the notion of neighborhood n-sigraph as introduced above, since the entire class of i-unbalanced n-sigraphs is forbidden to neighborhood n-sigraphs.

Proposition 2.1. For any n-sigraph [S.sub.n] = (G, [sigma]), its neighborhood n-sigraph N([S.sub.n]) is i-balanced.

Proof. Since the n-tuple of any edge uv in N([S.sub.n]) is [mu](u)/[mu](v), where [mu] is the canonical n-marking of [S.sub.n], by Proposition 1.1, N([S.sub.n]) is i-balanced.

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 n-sigraph [S.sub.n] = (G, [sigma]) is a neighborhood n-sigraph. Then [S.sub.n] is i-balanced and G is a neighborhood graph.

Proof. Suppose that [S.sub.n] is a neighborhood n-sigraph. That is there exists an n-sigraph [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 n-sigraph of any n-sigraph is i-balanced, it follows that N([S'.sub.n]) = [S.sub.n] is i-balanced.

Problem 2.4. Characterize neighborhood n-sigraphs.

Proposition 2.5. For any two n-sigraphs [S.sub.n] and [S'.sub.n] with the same underlying graph, their neighborhood n-sigraphs 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.k-1](G)).

Proposition 2.8. For any graph G and any integer k [greater than or equal to] 1, the kth-iterated 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 n-sigraphs satisfies [S.sub.n] ~ N([S.sub.n]).

Proposition 2.9. A connected n-sigraph [S.sub.n] = (G, a) satisfies [S.sub.n] = N([S.sub.n]) if, and only if, [S.sub.n] is i-balanced 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 n-sigraph with underlying graph is complete or is an odd cycle, Proposition 3 implies that N([S.sub.n]) is i-balanced and hence if [S.sub.n] is i-unbalanced and its neighborhood n-sigraph N([S.sub.n]) being i-balanced can not be switching equivalent to [S.sub.n] in accordance with Proposition 1.2. Therefore, [S.sub.n] must be i-balanced.

Conversely, suppose that [S.sub.n] i-balanced n-sigraph on a complete graph or an odd cycle. Then, since N([S.sub.n]) is i-balanced 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 n-sigraph [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 n-sigraph [S.sub.n], the result follows by Proposition 1.2 again.

[section]3. Switching equivalence of neighborhood n-sigraphs and line n-sigraphs

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 n-sigraph of an n-sigraph [S.sub.n] = (G, [sigma]) is an n-sigraph 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 n-sigraph [S.sub.n] = (G,[sigma]), its line n-sigraph L([S.sub.n]) is i-balanced.

For any positive integer k, the kth iterated line n-sigraph, [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.k-1]([S.sub.n])).

Corollary 3.2. For any n-sigraph [S.sub.n] = (G, [sigma]) and for any positive integer k, [L.sup.k]([S.sub.n]) is i-balanced.

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 n-sigraphs whose neighborhood n-sgraphs are switching equivalent to their line n-sigraphs.

Proposition 3.4. For any n-sigraph [S.sub.n] = (G, a), N([S.sub.n]) = L([S.sub.n]) if, and only if, [S.sub.n] is an i-balanced n-sigraph and satisfies conditions (i) to (iv) of Proposition 3.3.

[section]4. Switching equivalence of neighborhood n-sigraphs and jump n-sigraphs

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 n-sigraph of an n-sigraph [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 n-sigraph [S.sub.n] = (G, [sigma]), its jump n-sigraph J([S.sub.n]) is i-balanced.

For any positive integer k, the kth iterated jump n-sigraph, [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.k-1]([S.sub.n])).

Corollary 4.3. For any n-sigraph [S.sub.n] = (G, [sigma]) and for any positive integer k, [J.sup.k] ([S.sub.n]) is i-balanced.

We now give a characterization of n-sigraphs whose jump n-sigraphs are switching equivalent to their neighborhood n-sigraphs.

Proposition 4.4. A connected n-sigraph [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 n-sigraph 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 n-sigraph on [C.sub.5]. Then by Proposition 4.1, N(G) [congruent to] J(G). Since for any n-sigraph [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), 75-85.

[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 n-path connected graphs and of graphs having n-th root, J. Combin. Th, Ser. B, 16(1974), No. 3, 282-289.

[6] F. Harary, Graph Theory, Addison-Wesley Publishing Co, 1969.

[7] V. Lokesha, P. Siva Kota Reddy and S. Vijay, The triangular line n-sigraph of a symmetric n-sigraph, Advn. Stud. Contemp. Math., 19(2009), No. 1, 123-129.

[8] R. Rangarajan and P. Siva Kota Reddy, Notions of balance in symmetric n-sigraphs, Proceedings of the Jangjeon Math. Soc, 11(2008), No. 2, 145-151.

[9] R. Rangarajan, P. Siva Kota Reddy and M. S. Subramanya, Switching Equivalence in Symmetric n-Sigraphs, Adv. Stud. Comtemp. Math, 18(2009), No. 1, 79-85.

[10] R. Rangarajan, P. Siva Kota Reddy and N. D. Soner, Switching equivalence in symmetric n-sigraphs-II, J. Orissa Math. Sco, 28(2009), 1-12.

[11] E. Sampathkumar, P. Siva Kota Reddy, and M. S. Subramanya, Jump symmetric n-sigraph, Proceedings of the Jangjeon Math. Soc, 11(2008), No. 1, 89-95.

[12] E. Sampathkumar, P. Siva Kota Reddy, and M. S. Subramanya, The Line n-sigraph of a symmetric n-sigraph, Southeast Asian Bull. Math, 34(2010), No. 5, 953-958.

[13] P. Siva Kota Reddy and B. Prashanth, Switching equivalence in symmetric n-sigraphs-I, Advances and Applications in Discrete Mathematics, 4(2009), No. 1, 25-32.

[14] P. Siva Kota Reddy, S. Vijay and B. Prashanth, The edge C4 n-sigraph of a symmetric n-sigraph, Int. Journal of Math. Sci. & Engg. Appls., 3(2009), No. 2, 21-27.

[15] P. Siva Kota Reddy, V. Lokesha and Gurunath Rao Vaidya, The Line n-sigraph of a symmetric n-sigraph-II, Proceedings of the Jangjeon Math. Soc, 13(2010), No. 3, 305-312.

[16] P. Siva Kota Reddy, V. Lokesha and Gurunath Rao Vaidya, Switching equivalence in symmetric n-sigraphs-III, Int. Journal of Math. Sci. & Engg. Appls, 5(2011), No. 1, 95-101.

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

E-mail: pskreddy@acharya.ac.in gurunathgvaidya@yahoo.co.in askr1985@gmail.com
COPYRIGHT 2011 American Research Press
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

 Reader Opinion

Title:

Comment:



 

Article Details
Printer friendly Cite/link Email Feedback
Author:Reddy, P. Siva Kota; Vaidya, Gurunath Rao; Reddy, A. Sashi Kanth
Publication:Scientia Magna
Article Type:Report
Date:Jun 1, 2011
Words:3564
Previous Article:Counterexamples to a theorem concerning solution of certain quadratic Diophantine equation.
Next Article:The influence of SCAP and S-supplemented subgroups on the p-nilpotency of finite groups.

Terms of use | Copyright © 2014 Farlex, Inc. | Feedback | For webmasters