-
Graphs with at most two moplexesDallard, 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.Source: Journal of graph theory. - ISSN 0364-9024 (Vol. 107, iss. 1, Sep. 2024, str. 38-69)Type of material - article, component part ; adult, seriousPublish date - 2024Language - englishCOBISS.SI-ID - 196261891
Author
Dallard, Clément Jean |
Ganian, Robert |
Hatzel, Meike |
Krnc, Matjaž, 1987- |
Milanič, Martin, 1980-
Topics
asteroidno število |
izogibno vozlišče |
koprimerljivostni graf |
Hamiltonska pot |
mopleks |
simplicialno vozlišče |
asteroidal number |
avoidable vertex |
cocomparability graph |
Hamiltonian path |
moplex |
simplicial vertex
Shelf entry
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 |
---|---|
Dallard, Clément Jean | 53750 |
Ganian, Robert | |
Hatzel, Meike | |
Krnc, Matjaž, 1987- | 34562 |
Milanič, Martin, 1980- | 30211 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.