460 KB104 KB200820252019Conder, Marston D. E.Stokes, Klaraštevilka:1letnik:17str. 1-35ISSN:1855-3966COBISSID_HOST:18911577URN:URN:NBN:SI:doc-AZ6JLT2JenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneagenusgraph embeddingrodvložitev grafaNew methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces|The question of how to find the smallest genus of all embeddings of a given finite connected graph on an orientable (or non-orientable) surface has a long and interesting history. In this paper we introduce four new approaches to help answer this question, in both the orientable and non-orientable cases. One approach involves taking orbits of subgroups of the automorphism group on cycles of particular lengths in the graph as candidates for subsets of the faces of an embedding. Another uses properties of an auxiliary graph defined in terms of compatibility of these cycles. We also present two methods that make use of integer linear programming, to help determine bounds for the minimum genus, and to find minimum genus embeddings. This work was motivated by the problem of finding the minimum genus of the Hoffman-Singleton graph, and succeeded not only in solving that problem but also in answering several other open questionsProblem določitve najmanjšega roda vseh vložitev danega končnega povezanega grafa v orientabilno (ali neorientabilno) ploskev ima dolgo in zanimivo zgodovino. V tem članku vpeljemo štiri nove pristope, ki pomagajo odgovoriti na to vprašanje tako v orientabilnih kot v neorientabilnih primerih. Eden od možnih pristopov je, da kot kandidate za podmnožice lic vložitev vzamemo orbite podgrup grupe avtomorfizmov na ciklih določene dolžine v grafu. Drug pristop uporablja lastnosti pomožnega grafa, ki je definiran glede na usklajenost teh ciklov. Predstavimo tudi dve metodi, ki temeljita na celoštevilskem linearnem programiranju in pomagata določiti meje za minimalni rod ter poiskati vložitve z najmanjšim rodom. To delo je bilo motivirano s problemom določitve minimalnega roda Hoffman-Singletonovega grafa. Poleg rešitve tega problema smo uspeli odgovoriti tudi na več drugih odprtih vprašanjTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije