Algebarska i kombinatorna svojstva grafova pridruzenih stepeno-asocijativnim grupoidima

Abstract

Usmereni stepeni graf ~G(G) grupe G uveli su Kelarev i Quinn [37] kao digraf sa skupom cvorova G u kome je x ! y ako je y stepen elementa x, a stepeni graf G(G) je odgovarajuci prost graf, i njega su prvi proucavali Chakrabarty, Ghosh i Sen [17]. Obogaceni stepeni graf G e(G) od G, koji je uveden u [1], je prost graf sa istim skupom cvorova u kome su dva cvora susedna ako su oba stepeni nekog elementa te grupe.U disertaciji su predstavljeni dokazi iz [12] i [73] da se, za konacnu stepenoasocijativnu lupu G sa inverzima, ~ G(G), G(G) i G e(G) medusobno odreduju. Ovo povlaci da sva tri navedena grafa pridruzena konacnoj grupi u istoj meri odreduju razne osobine te grupe, kao sto su broj elemenata bilo kog reda i nilpotentnost te grupe. Dokazano je da, u slucaju torziono slobodne grupe u kojoj je svaki nejedinicni element sadrzan u jedinstvenoj maksimalnoj ciklicnoj podgrupi, stepeni graf odreduje usmereni stepeni graf, sto je rezultat rada [14], i analogno je dokazano i za torziono slobodne grupe klase nilpotentnosti klase 2. Pruzen je dokaz da je svaki automorzam stepenog grafa stepeno-asocijativne lupe sa inverzima automorzam obogacenog grafa. Dat je opis obogacenih stepenih grafova konacnih Abelovih grupa. Prezentirano je nekoliko potrebnih uslova da graf bude obogaceni stepeni graf neke konacne grupe, kao i algoritam koji za obogaceni stepeni graf konacne nilpotentne grupe daje obogaceni stepeni graf njene podgrupe Sylowa.Komutirajuci graf grupe je prost graf ciji je skup cvorova nosac grupe, i u kome su dva elementa susedna ako komutiraju. U disertaciji je predstavljen dokaz Bernharda Neumanna [54] da, ako komutirajuci graf grupe nema beskonacan nezavisan skup, onda on nema ni proizvoljno velike konacne nezavisne skupove. Okarakterisane su nilpotentne grupe ciji stepeni graf nema beskonacni nezavisni skup, sto je rezultat rada [1]. Prezentovan je dokaz Shitova [69] da je hromatski broj stepenog grafa stepeno-asocijativnog grupoida najvise prebrojiv, i dokazano je da je hromatski broj obogacenog stepenog grafa stepeno-asocijativne lupe sa inverzima takode najvise prebrojiv. Izlozen je dokaz iz [1] da je stepeni graf svake grupe ogranicenog eksponenta perfektan, i data je karakterizacija konacnih nilpotentnih grupa ciji je obogaceni stepeni graf perfektan.

The directed power graph ~G(G) of a group G was introduced by Kelarev and Quinn [37] as the digraph with its vertex set G in which x ! y if y is a power of x.The power graph G(G) is the underlying simple graph, and it was rst studied by Chakrabarty, Ghosh and Sen [17]. The enhanced power graph G e(G) of G, which was introduced in [1], is the simple graph with the same vertex set in which two vertices are adjacent if they are powers of one element.In this thesis are presented the proofs from [12] and [73] that, for any powerassociative loop G with inverses,~ G(G), G(G) and G e(G) determine each other. It follows that each of these three graphs associated to a nite group provides the same amount of information about the group, such as the number of elements of any order and nilpotency of the group. It is also proved that, in the case of a torsionfree group in which every non-identity element is contained in a unique maximal cyclic subgroup, the power graph determines the directed power graph, which is a result from [14], and the same is proved for torsion-free groups of nilpotency class 2.It is proved that an automorphism of the power graph of a power-associative loop with inverses is an automorphism of the enhanced power graph. A description of enhanced power graphs of abelian groups is given. Several necessary conditions for a graph to be the enhanced power graph of a nite group are presented, as well as an algorithm which, given the enhanced power graph of a nite nilpotent group, constructs the enhanced power graph of the Sylow subgroup. The commuting graph of a group is the simple graph whose vertex set is the universe of the group, and in which two elements are adjacent if they commute. In the thesis is presented the proof by Bernhard Neumann [54] that, if the commuting graph of a group doesn't have any innite independent set, then there is a nite bound on cardinality of its independent sets. Nilpotent groups whose power graphs don't have any innite independent set are characterized, which is a result from [1]. The proof of Shitov [69] that the chromatic number of the power graph of a power-associative groupoid is at most countable is presented, and it is proved that the chromatic number of the enhanced power graph of power-associative loops with inverses are at most countable too. The proof from [1] that the power graph of any group of nite exponent is presented, and nite nilpotent groups whose enhanced power graph is perfect are characterized.