ALL libraries (COBIB.SI union bibliographic/catalogue database)
13.
Graphs with at most two moplexes
Dallard, Clément Jean ...
Mopleks je naravna grafovska struktura, ki se pojavi pri posplošitvi Diracovega klasičnega izreka za tetivne grafe na splošne grafe. Pojem je tesno povezan z leksikografskimi iskanji v grafih, pa ...tudi s asteroidnimi trojicami, in je bil uporabljen v več algoritmih, povezanih z grafovskimi razredi, kot so intervalni grafi, ter grafi brez induciranih krempljev oz. diamantov. Čeprav ima vsak graf, ki ni poln, vsaj dva mopleksa, ni veliko znanega o strukturnih lastnostih grafov z omejenim številom mopleksov. Raziskava teh grafov je delno motivirana s paralelo med mopleksi v splošnih grafih in simplicialnimi moduli v tetivnih grafih: za razliko od situacije z mopleksi so lastnosti tetivnih grafov z omejenim številom simplicialnih modulov dobro razumljene. Na primer, tetivni grafi, ki imajo največ dva simplicialna modula, so intervalni. V tem delu začenjamo preiskavo ▫$k$▫-mopleksnih grafov, ki so definirani kot grafi, ki vsebujejo največ ▫$k$▫ mopleksov. Posebej zanimiv je najmanjši netrivialen primer, ▫$k = 2$▫. Kot naš glavni strukturni rezultat pokažemo, da se razred ▫$2$▫-mopleksnih grafov nahaja med razredoma pravih intervalnih grafov in neprimerljivostnih grafov (obe vključitvi sta tesni za hereditarne razrede). S stališča računske zahtevnosti to vodi do naravnega vprašanja, ali prisotnost največ dveh mopleksov zagotavlja dovoljšno količino strukture za učinkovito reševanje problemov, ki so sicer znani kot nerazrešljivi na neprimerljivostnih grafih, ne pa tudi na pravih intervalnih grafih. Razvijemo nove prevedbe, ki na to vprašanje odgovarjajo negativno za dva takšna problema: problem izomorfizma grafa, ter problem največjega prereza. Po drugi strani pa pokažemo, da vsak povezan ▫$2$▫-mopleksni graf vsebuje hamiltonsko pot, kar posploši enako lastnost povezanih pravih intervalnih grafov. Poleg tega posplošimo znani rezultat o obstoju največ dveh mopleksov v grafih brez asteroidnih trojk, na bolj splošen rezultat o grafih s poljubno velikostjo asteroidnih množic.
It was not necessary to add the material to the shelf.
Bibliographic material was successfully added on shelf.
Adding bibliographical material on shelf was not successful.
Material is already on the shelf.
Permalink
URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year
Impact factor
Edition
Category
Classification
JCR
SNIP
JCR
SNIP
JCR
SNIP
JCR
SNIP
Select the library membership card:
DRS,
in which the journal is indexed
Database name
Field
Year
Links to authors' personal bibliographies
Links to information on researchers in the SICRIS system
Subject headings in COBISS General List of Subject Headings
Select pickup location
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
