New methods for finding minimum genus embeddings of graphs on orientable and non-orientable surfaces

angleški

2019

letnik 17, številka 1

rod   vložitev grafa

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Problem 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šanj.

29.05.2020