DIKUL - logo
(UL)
PDF
  • Graphs with two moplexes [Elektronski vir]
    Dallard, Clément Jean ...
    Mopleksi so naravne grafovske strukture, na katere lahko gledamo kot posplošitev Diracovega klasičnega izreka o tetivnih grafih, na splošne grafe. Znano je, da je ta pojem tesno povezan z ... leksikografskim iskanjem v grafih, pa tudi z asteroidnimi trojkami, in je bil uporabljen v več algoritmih, povezanih z razredi grafov, kot so intervalni grafi, grafi brez krempljev in grafi brez diamantov. Čeprav ima vsak graf, ki ni poln, vsaj dva mopleksa, je malo znanega o strukturnih lastnostih grafov z omejenim številom mopleksov. Preučevanje teh grafov je med drugim motivirano s primerjavo med mopleksi v splošnih grafih in simplicialnimi moduli v tetivnih grafih: veliko je namreč znanega o tetivnih grafih z omejenim številom simplicialnih modulov (na primer, tetivni grafi, ki imajo največ dva simplicialna modula, so intervalni). Po drugi strani o grafih z omejenim številom mopleksov vemo zelo malo. V tem delu začnemo z raziskavo ▫$k$▫-mopleksnih grafov, ki so definirani kot grafi, ki vsebujejo največ ▫$k$▫ mopleksov. Posebej zanimiv je najmanjši netrivialni primer, ▫$k = 2$▫, ki ustreza razredu intervalnih grafov. Kot naš glavni strukturni rezultat pokažemo, da je razred povezanih 2-mopleksnih grafov umeščen med razred pravih intervalnih grafov in razred koprimerljivostnih grafov; poleg tega sta obe vključitvi tesni za hereditarne razrede. Z vidika teorije kompleksnosti to vodi do naravnega vprašanja, ali prisotnost največ dveh mopleksov zagotavlja zadostno količino strukture za učinkovito reševanje problemov, za katere je znano, da so nerešljivi na grafih koprimerljivosti, ne pa tudi na pravih intervalnih grafih. Razvijemo nove prevedbe, ki na to vprašanje odgovarjajo negativno za dva relevantna problema, in sicer izomorfizem grafa in problem največjega prereza. Poleg tega za grafe z večjim številom mopleksov posplošimo prej znani rezultat, da imajo grafi brez asteroidnih trojk največ dva mopleksa na bolj splošno trdivev za večje asteroidne množice. Obravnavamo tudi zadostne pogoje za obstoj hamiltonskih poti v 2-mopleksnih grafih ter nekatere druge povezave z izogibnimi vozlišči.
    Source: Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium [Elektronski vir] (Str. 248-256)
    Type of material - conference contribution ; adult, serious
    Publish date - 2021
    Language - english
    COBISS.SI-ID - 93541123

    Link(s):

    https://www.sciencedirect.com/science/article/pii/S1877050921021700
    DOI

Shelf entry