Skip to main content
SUPERVISOR
Bijan Taeri,Mohammad-Reza Vedadi
بیژن طائری (استاد راهنما) محمد رضا ودادی (استاد مشاور)
 
STUDENT
Kazem Shokri
کاظم شکری

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1388

TITLE

Integral Cayley graphs over abelian groups
Let G be a finite, additive abelian group. A subset S of G is called a Cayley subset if 0 notin S and ? S = S where S = { s : s ? S } . The undirected Cayley graph Cay( G; S ) has vertex set G and edge set {{ a; b } : a; b ? G; ab ? S } . A graph is called integral, if all of its eigenvalues are integers. For an abelian group G we prove that Cay( G; S ) is integral, if S belongs to the Boolean algebra B ( G ) generated by the subgroups of group G . We prove that the converse is hold for cyclic groups. In fact for a Cayley subset S of the cyclic group Z n of order n , where n ? 2, we prove that Cay(Z n ; S ) is integral if and only if S ? B (Z n ). Let S be a Cayley subset of G . If for every a ? S , | a | ? { 2 ; 3 ; 4 ; 6 } , where | a | denotes the order of a , then we show that S ? B ( G ). A finite group G is called Cayley integral, if every undirected Cayley graph over group G is integral . We finde all nontrivial abelian Cayley integral groups. Let m 1 ,…,m r be positive integers and D = { d 1 ,…,d k } a set of integers, where 1 ? d i ? r , i = 1 ,…, k . The Hamming graph H = Ham( m 1 ,…,m r ; D ) has as its vertex set the abelian group G = Z m 1 ×· · ·× Z m r . The Hamming distance of vertices x = ( x 1 ,…, x r ) and y = ( y 1 ,…, y r ) is d ( x; y ) = { i :1 ? i ? r; x i noteq y i }| : Vertices x and y are adjacent in H , if d ( x; y ) ? D . We show that every Hamming graph Ham( m 1 ,…,m r ; 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 × n cells. Such that each cell has to be filed with a number (color) ranging from 1 to n 2 such that every block, row or column contains all of the colors 1 ,…, n 2. The Sudoku graph has as its vertices the n .n cells of an n -Sudoku. Vertices (cells) are adjacent, if they are in the same block, row or column. In a variant of Sudoku, positional Sudoku cells have to satisfy an additional condition. Distinct cells in the same position of their respective blocks have to be colored differently. The underlying positional Sudoku graph gets additional edges in comparison to Sudoku graph. We prove that Every Sudoku graph and every 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 appears exactly once in every row and in every column. For a pandiagonal Latin square two additional conditions have to be satisfied. Every number 1 ,…, n has to appear exactly once in the main diagonal and its broken parallels as well as in the secondary diagonal and its broken parallels. For n ? 2 the pandiagonal Latin square graph PLSG( n ) has as its vertex set the n .n 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) parallel to the main diagonal or in the same (broken) parallel to the secondary diagonal. We show that every pandiagonal Latin square graph PLSG( n ) is an integral Cayley graph.
فرض کنید S یک زیرمجموعه از گروه جمعی G باشد به طوری که 0 ? S و –S=S . در این صورت S را یک زیر مجموعه کیلی از G می نامیم. گراف کیلی Cay(G,S) گرافی با مجموعه رئوس G است. درا ین گراف دو راس a و b مجاورند اگر و تنها اگر a-b ? S . اگر هر مقدار ویژه ی یک گراف صحیح باشد آنگاه گراف را صحیح می نامیم. همچنین در صورتی که به ازای هر زیر مجموعه کیلی S از G گراف کیلی Cay(G,S) صحیح باشد آنگاه گروه G را صحیح کیلی می نامیم. در این پایان نامه ثابت می کنیم اگر S متعلق به جبر بولی B(G) باشد آنگاه گراف کیلی Cay(G,S) صحیح است و اگر گروه G صحیح کیلی باشد آنگاه برای هر a ناصفر از G ‌ داریم مرتبه a دو سه چهار ویا شش است. هم چنین در این پایان نامه همه ی گروه های آبلی (غیر بدیهی) صحیح کیلی تعین شده است. در این پایان نامه گراف همینگ گراف سودوکو گراف سودوکو مکانی و گراف مربع لاتین سراسر قطری را بررسی می کنیم و نشان می دهیم این گراف ها گراف های کیلی صحیح هستند. .

ارتقاء امنیت وب با وف بومی