گراف هاي كيلي صحيح روي گروههاي آبلي

چكيده انگليسي :

Integral Cayley graphs over abelian groups Kazem Shokri k shokri@math iut ac ir January 28 2012 Master of Science Thesis in Farsi Departement of Mathematical Sciences Isfahan University of Technology Isfahan 84156 8311 IranSupervisor Dr Bijan Taeri b taeri@cc iut ac irAdvisor Mohamadreza Vedadi m vedadi@cc iut ac ir2000 MSC 05C25 05C50Key Words Cayley graph Integral graph Cayley integral group Hamming graph Sudokugraph Positional Sudoku graph Pandiagonal Latin square graphAbstract This Msc thesis is based on the following paperKlotz W Sander T Integral Cayley graphs over abelian groups Electronic J Combinatorics 17 2010 R81 1 13 Let G be a nite additive abelian group A subset S of G is called a Cayley subset if 0 S and S S where S s s S The undirected Cayley graph Cay G S has vertex set G and edgeset a b a b G ab S A graph is called integral if all of its eigenvalues are integers For anabelian group G we prove that Cay G S is integral if S belongs to the Boolean algebra B G generatedby the subgroups of group G We prove that the converse is hold for cyclic groups In fact for a Cayleysubset S of the cyclic group Zn of order n where n 2 we prove that Cay Zn S is integral if and only ifS B Zn Let S be a Cayley subset of G If for every a S a 2 3 4 6 where a denotes the orderof a then we show that S B G A nite group G is called Cayley integral if every undirected Cayleygraph over group G is integral Denote by Zk the n fold direct product of Zk with itself We proof that nall nontrivial abelian Cayley integral groups are Zn Zm Zn Zm Zn Zm Zn m 1 n 1 2 3 4 2 3 2 4Let m1 mr be positive integers and D d1 dk a set of integers where 1 di r i 1 k The Hamming graph H Ham m1 mr D has as its vertex set the abelian group G Zm1 Zmr The Hamming distance of vertices x x1 xr and y y1 yr is d x y i 1 i r xi yi Vertices x and y are adjacent in H if d x y D We show that every Hamminggraph Ham m1 mr D is an integral Cayley graph For an integer n 2 an n Sudoku is an arrangement of n n square blocks each consisting of n ncells Such that each cell has to be lled with a number color ranging from 1 to n2 such that everyblock row or column contains all of the colors 1 n2 The Sudoku graph has as its vertices the n2cells of an n Sudoku Vertices cells are adjacent if they are in the same block row or column In avariant of Sudoku positional Sudoku cells have to satisfy an additional condition Distinct cells in thesame position of their respective blocks have to be colored di erently The underlying positional Sudokugraph gets additional edges in comparison to Sudoku graph We prove that Every Sudoku graph andevery positional Sudoku graph is an integral Cayley graph A Latin square is an n n matrix with entries from 1 2 n such that every number 1 n appearsexactly once in every row and in every column For a pandiagonal Latin square two additional conditionshave to be satis ed Every number 1 n has to appear exactly once in the main diagonal and itsbroken parallels as well as in the secondary diagonal and its broken parallels For n 2 the pandiagonalLatin square graph PLSG n has as its vertex set the n2 positions of an n n matrix Distinct vertices positions are adjacent if they are in the same row in the same column in the same broken parallelto the main diagonal or in the same broken parallel to the secondary diagonal We show that everypandiagonal Latin square graph PLSG n is an integral Cayley graph

شكري، كاظم

گراف هاي كيلي صحيح روي گروههاي آبلي

گراف همينگ , گراف سودوكومكاني و گراف مربع لاتين سراسر قطري