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.
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.
PDF
