-
Shifting paths to avoidable onesGurvich, Vladimir ...Razširitev inducirane poti ▫$P$▫ v grafu ▫$G$▫ je taka inducirana pot ▫$P'$▫, da po izbrisu krajišč poti ▫$P'$▫ dobimo pot ▫$P$▫. Inducirana pot v grafu je izogibna, če je vsaka od njenih razširitev ... vsebovana v nekem induciranem ciklu. Leta 2019 so Beisegel, Chudnovsky, Gurvich, Milanič in Servatius postavili domnevo, da vsak graf, ki premore inducirano pot na ▫$k$▫ točkah, premore tudi izogibno inducirano pot enake dolžine. V istem delu so avtorji dokazali rezultat za ▫$k = 2$▫. Primer ▫$k = 1$▫ je bil znan veliko prej, kar so pokazali Ohtsuki, Cheung in Fujisawa leta 1976. Domnevo so za vse vrednosti k leta 2020 dokazali Bonamy, Defrain, Hatzel in Thiebaut. V tem prispevku s podobnim pristopom posplošimo njihov rezultat z vidika rekonfiguracije. Pokažemo, da je poljubno inducirano pot v danem grafu mogoče premakniti v izogibno pot z zaporedjem premikov. Tu kot premik smatramo taki dve inducirani poti na ▫$k$▫ točkah, da unija njunih točk inducira pot na ▫$k + 1$▫ točkah. Podobne rezultate dobimo tudi za ne nujno inducirane poti in za sprehode. Po drugi strani pa trditve ni mogoče razširiti na sledi, ali na izometrične poti.Source: Journal of graph theory. - ISSN 0364-9024 (Vol. 100, iss. 1, May 2022, str. 69-83)Type of material - article, component part ; adult, seriousPublish date - 2022Language - englishCOBISS.SI-ID - 88493571
Author
Gurvich, Vladimir |
Krnc, Matjaž, 1987- |
Milanič, Martin, 1980- |
Vyalyi, Mikhail N.
Topics
izogiben sprehod |
sklenjen sprehod |
cikel |
inducirana pot |
izometrična pot |
pot |
rekonfiguracija |
prestavljanje |
sled |
sprehod |
avoidable walk |
closed walk |
cycle |
induced path |
isometric path |
path |
reconfiguration |
shifting |
trail |
walk
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 |
---|---|
Gurvich, Vladimir | |
Krnc, Matjaž, 1987- | 34562 |
Milanič, Martin, 1980- | 30211 |
Vyalyi, Mikhail N. |
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.