برخي خواص گراف هاي دوكيلي

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

Some Properties of Bi Cayley Graphs Ehsan Bampoori e bampoori@math iut ac ir September 18 2013 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 Dr Sayed Ghahreman Taherian taherian@cc iut ac ir2000 MSC 05C25 20B25 05C60 Keywords Cayley graph Bi Cayley graph Semi regular and regular action Perfect matching Extendability Abstract This M Sc thesis is based on the following papers Weijun Liu Wei Jin A classification of nonabelian simple 3 BCI groups European Journal of Combina torics 31 2010 1257 1264 Xing Gao Yanfeng Luo On the extendability of Bi Cayley graphs of finite abelian groups Discrete Math ematics 309 2009 5943 5949Let G a finite group and S be subset of a group G such that 1 S and S S 1 the Cayley graph Cay G S of G with respect to S is defined as the graph with vertex set G and edge set x sx x G s S For aCayley graph Cay G S of a finite group G it is called a CI graph if for any another Cayley graph Cay G T whenever Cay G S Cay G T there exists an automorphism Aut G suchthat S T Let R S T be subsets of a group G such that R R 1 S S 1 and 1 R S Define the undirected graph BCay G R S T to have vertex set G 0 1 and with vertices h i g j adjacent if and only if one of thefollowing three possibilities occurs 1 i j 0 and gh 1 R 2 i j 1 and gh 1 S 3 i 0 j 1 and gh 1 T The graph BCay G R S T is called a bi Cayley graph Equivalently a bi Cayley graph may be defined as agraph V E which admits an automorphism group acting semiregular on the vertex set V with two orbits of equal size Let G be a finite group G and a subset S G possibly S contains the identity element thebi Cayley graph BCay G S of G with respect to S is the graph with vertex set G 0 1 and with edge set x 0 sx 1 x G t S Then BCay G S is a well defined bipartite graph with bipartition subsets say U G 0 W G 1 There are two important isomorphisms for bi Cayley graphs Let G be a finitegroup S be a subset of G Suppose X BCay G S g h are two elements of G is a group automorphism Then we have BCay G S 1 BCay G S BCay G gSh 2 BCay G S The above two isomorphisms and their compounds are called Cayley isomorphisms of bi Cayley graphs Furthermore if there exist Cayley isomorphisms between two bi Cayley graphs BCay G S and BCay G T then there existg G Aut G such that T gS A bi Cayley graph BCay G S is called a BCI graph if for anybi Cayley graph BCay G T whenever BCay G S BCay G T we have T gS for some g G Aut G A group G is called an m BCI group if all bi Cayley graphs of G of valency at most m areBCI graphs A set M of edges of a graph is called a matching of if no two members of M share a commonvertex A matching M is perfect if every vertex of is covered by an edge of M A graph admitting a perfectmatching is called n extendable if V 2n 2 and every matching of size n in can be extended to a perfectmatching of In one paper we prove that a finite nonabelian simple group is a 3 BCI group if and only if itis A5 In seconed paper the extendability of Bi Cayley graphs of finite abelian groups is explored In particular 2 extendable and 3 extendable Bi Cayley graphs of finite abelian groups are characterized

بمپوري، احسان

برخي خواص گراف هاي دوكيلي

عمل منظم و نيمه منظم , گراف كيلي , جورسازي كامل , توسعه پذيري