157-160 R.N. Yadav R C O S T N R.N. Yadav / BIBECHANA 11(1) (2014) 157-160: (Online Publication: March, 2014) p.157 BIBECHANA A Multidisciplinary Journal of Science, Technology and Mathematics ISSN 2091-0762 (online) Journal homepage: http://nepjol.info/index.php/BIBECHANA Signed graphs connected with the root lattice R.N. Yadav Department of Mathematics M.M.A.M. Campus, T.U., Biratnagar, Nepal E-mail: rajnarayanyadav29@yahoo.com Accepted for publication: February 12, 2014 Abstract For any base of the root lattice (An) we can construct a signed graph. A signed graph is one whose edges are signed by +1 or -1. A signed graph is balanced if and only if its vertex set can be divided into two sets-either of which may be empty–so that each edge between the sets is negative and each edge within a set is positive. For a given signed graph Tsaranov, Siedel and Cameron constructed the corresponding root lattice. In the present work we have dealt with signed graphs corresponding to the root lattice An. A connected graph is called a Fushimi tree if its all blocks are complete subgraphs. A Fushimi tree is said to be simple when by deleting any cut vertex we have always two connected components. A signed Fushimi tree is called a Fushimi tree with standard sign if it can be transformed into a signed Fushimi tree whose all edges are signed by +1 by switching. Here we have proved that any signed graph corresponding to An is a simple Fushimi tree with standard sign. Our main result is that s simple Fushimi tree with standard sign is contained in the cluster given by a line. © 2014 RCOST: All rights reserved. Keywords: Signed graph; Root lattice; Fushimi tree. 1. Introduction A signed graph is a graph in which each edge has a positive or negative sign. A signed graph is balanced if and only if its vertex set can be divided into two sets (either of which may be empty) X and Y, So that each edge between the sets is negative and each edge within a set is positive. This is the first theorem of signed graphs (Harary, 1953) A given signed graph, Tsaranov, seidel and Cameron instruct the corresponding root lattice. We treated with signed graphs corresponding to the root lattice An. A connected graph is called a Fushimi tree if its all blocks are complete subgraphs. A Fushimi, tree is said to be simple when by deleting any cut vertex, We have always two its connected components. Switching and local switching of signed graphs are also Introduced by Cameron, seidel and Tsaranov. A signed Fushimi tree is said to be a Fushimi tree with standard sign if it can be transformed to a signed Fushimi tree whose all edges are signed by +1. by a switching we prove that any signed graph corresponding to An is a simple Fushimi tree with standard sign. 2. Some definitions (i) Posets : Let P be any set in which the partial order relation ≤ holds i.e. This relation is a. Reflexive : ,xx ≤ ∀ Px ∈ R.N. Yadav / BIBECHANA 11(1) (2014) 157-160: (Online Publication: March, 2014) p.158 b. Anti-symmetric : yx ≤ and ,yxxy =⇒≤ ∀ Pyx ∈, c. Transitive : yx ≤ and ,zxzy ≤⇒≤ ∀ Pzyx ∈,, For Example: The se of Natural number N={1,2,3,………..w} with maximal elements W is a poset with the usual ordering ≤ . (ii) Lattice : A poset (P, ≤) in which every pair of elements has a supremum (V) or Join and infimum (Λ) or meet is called a lattice. It is noted by L. For Example: It is a lattice, for avb = a or b ∈ N, according as ba ≤ or ab ≤ Nboraba ∈=∧ , according as ba ≤ or ab ≤ (iii) The lattice An and signed Fushimi trees A connected graph G = (V, E) is called Fushimi tree if each block of G is a perfect graph. A Fushimi tree G is said to be Fushimi tree if G is divided exactly two connected components when each cut verdex in G is deleted. A signed simple Fushimi tree is called a special Fushimi tree with standard sign if we switch all signs of edges in to +1. The lattice An is spanned by vectors ji ee − , ,1+≤≠≤ njil where }.........,{ 12,1 +neee is the orthonormal base of the Euclidean (n+1) space 1+nR There is the one - to - one correspondence between orderd root bases of An and connected signed graphs associated with An. (iv) Local switching : Let S be subset of vertices of a graph G then the graph H formed by vertices of S is called local switching of G generated by S. 3. Theorem Any connected signed graph is a signed graph associated with nA if and only if it is a simple Fushimi tree with Standard sign. Proof. Let G be a singed graph corresponding to a ordered base },...,,{ 21 naaa . If we replace ia by - ia , then the sign of G is switched with respect to {ia }. Hence there is no problem whether we take ia or – ia . There is no cycle in G whose length is more than 3. In fact, if 3,,...,, 21 >maaa miii make a cycle, then we can assume that , 2211 jjji eeea =−= , 32 ji ea = ,,..., 1433 jjijji eeaeea mm −=−= But this implies that miii aaa ,...,, 21 are not linearly independent. If 321 ,, iii aaa make a cycle, then we can assume that , 11 jji eea −= ., 3322 jjijji eeaeea −=−= We have cycles of this type only in G. Now take a block B of G consisting of vertices miii aaa ,..., 21 . Two vertices all 1i a and 2i a must be on a cycle in B. We may R.N. Yadav / BIBECHANA 11(1) (2014) 157-160: (Online Publication: March, 2014) p.159 assume that 321 ,, iii aaa make a cycle, then we can put 332211 ,, jjijjijji eeaeeaeea −=−=−= . The vertices 1i a and 4i a are also on a cycle in B, which may be 541 ,, iii aaa . Then we can put 44 jji eea −= , 55 jji eea −= or 515414 , jjijji eeaeea −=−= , where jJ ≠4 . Assume that 515414 , jjijji eeaeea −=−= . Two vertices 2a and 4a are also on a cycle in .B Then we have ,24 jj = a contradiction. Hence, we get 5544 , jjijji eeaeea −=−= . By this way, we get kk jji eea −= , .1 mk ≤≤ Hence any block of G is a perfect graph whose edges have sign+1. Suppose that 11 jji eea −= of a block B is a cut vertex. If two vertex kj aa , which are not in B are adjacent with 1i a , then we can put 1111 , kjjkjjj eeaeea −=−= . Hence kj iii aaa ,, 1 are contained in another block of G. Hence we show that G- 1i a has two connected components. Thus G is a simple Fushimi tree with standard sign. Conversely: Let G be a special Fushimi tree with standard sign. Assume that G has m blocks. If m = 1, it is evident that G is a connected signed graph associated with nA . Now suppose that the result is true for simple signed Fushimi trees with m blocks. Let G be a simple signed Fushimi tree with m + 1 blocks. Let G' be a simple Fushimi tree with standard sign which is made from G by deleting one block B of G. Then G' is a connected signed graph associated with nA and corresponding to a ordered base },....,,{ 21 naaa . Now assume that all l vertices of B are adjacement with a vertex 21 jji eea −= and that 2j e is not used in any other 2j a is not used in any otherja . Then we can consider that the block B consists of ++++ −−− lnjnjni eeeeee 222 ,...,, 32 and 1a . Hence we regard G as a connected signed graph associated with lnA + . 3.1. Local switching of simple Fushimi trees Let G be a simple Fushimi tree with standard sign. Take a block B of G. In the present work, G is said to be ( )kkn ,+ -type with respect to B if the order of B is n+k and the number of cut vertices in B is k. Let a be a cut vertex in a block B. G/{a} has the two connected components. One is the component containing B/{a}. We call the other the branch with respect to (B, a). All such components are called branches with respect to B. A block of a simple Fushimi tree is said to be pendant if it has only one cut vertex. We call a simple Fushimi tree line-like if it has only one block or it has exactly two pendant blocks. A branch aB with respect to (B, a) is called line - like if }{ aUBa I line-like. A simple Fushimi tree is said to be a line Fushimi tree if the order of its every block is 2. 3.2. Lemma Let G be a simple Fushimi tree of (n+k, k) -type with respect to a block B. We can transform G into a simple Fushimi tree of (k, k)-type, by a sequence of local switching. Proof. Let the block B consist of vertices knnn aaaaa ++ ....,,,....,, ,121 where knn aa ++ ,....,1 are cut vertices. set }{ 1+= naJ and }.....,,,,( ,2121 knnn aaaaaK ++−= By local switching with respect to ( )Jan , , we obtain a simple Fushimi tree of (n+k-1, k)-type with respect to block },.....,,,....,,{ 221 knnn aaaaa ++ , R.N. Yadav / BIBECHANA 11(1) (2014) 157-160: (Online Publication: March, 2014) p.160 where an and an+1 are cut vertices. Denote by 1G this simple Fushimi tree of (n+k-1, k)-type. Applying the same procedure to ,1G we get a simple Fushimi tree of (n+k-2,k)-type. Repeating the same method, we get a simple Fushimi tree of (k, k)-type at last. References [1] P. J. Cameron, J. M. Goethals, J. J. Seidel, E. E. Shult, J. Algebra, 43 (1976) 305. [2] D. M. Cvetkovic, M. Doob, I. Gutman, A. Torgasev, Annals of Discrete Mathematics 36, North- Roland, Amsterdam, 1991. [3] P. J. Cameron, J. J. Seidel, S. V. Tsaranov, J. Algebra, 164 (1994) 173. [4] J. E. Humphreys, Reflection group and Coxeter groups, Cambridge Staudies in Advanced Mathamatics 28, Cambridge, 1989. [5] T. Ishihara, J. Math. Univ. Tokushim, 36 (2002) 1.