-
Avoidable vertices and edges in graphs : existence, characterization, and applicationsBeisegel, Jesse ...A vertex in a graph is simplicial if its neighborhood forms a clique. We consider three generalizations of the concept of simplicial vertices: avoidable vertices (also known as OCF-vertices), ... simplicial paths, and their common generalization avoidable paths. In an earlier version of this paper, published as an extended abstract in the proceedings of the 16th International Symposium on Algorithms and Data Structures (WADS 2019), we presented a general conjecture on the existence of avoidable paths. The conjecture was recently proved by Bonamy et al. (2020). The conjecture—now a theorem—implies a result due to Ohtsuki, Cheung, and Fujisawa from 1976 on the existence of avoidable vertices and a result due to Chvátal, Sritharan, and Rusu from 2002 on the existence of simplicial paths in graphs excluding all sufficiently long induced cycles. In turn, both of these results generalize Dirac’s classical result on the existence of simplicial vertices in chordal graphs. We prove that every graph with at least two edges has two avoidable edges, which strengthens the statement of the theorem of Bonamy et al. for the case of paths of length one. We point out a close relationship between avoidable vertices in a graph and its minimal triangulations, and identify new algorithmic uses of avoidable vertices, leading to new polynomially solvable cases of the maximum weight clique problem in two classes of graphs simultaneously generalizing chordal graphs and circular-arc graphs. Finally, we observe that the results about the existence of avoidable vertices and edges have interesting consequences for highly symmetric graphs: in a vertex-transitive graph every induced two-edge path closes to an induced cycle, while in an edge-transitive graph every three-edge path closes to a cycle and every induced three-edge path closes to an induced cycle.Vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 309, mar. 2022, str. 285-300)Vrsta gradiva - članek, sestavni delLeto - 2022Jezik - angleškiCOBISS.SI-ID - 91552003
Avtor
Beisegel, Jesse |
Chudnovsky, Maria, 1977- |
Gurvich, Vladimir |
Milanič, Martin, 1980- |
Milanič, Mary Agnes
Teme
izogibna točka |
izogibna povezava |
leksikografsko iskanje v širino |
1-popolno usmerljiv graf |
bisimplicialna eliminacijska shema |
problem najtežje klike |
avoidable vertex |
avoidable edge |
LBFS |
1-perfectly orientable graph |
bisimplicial elimination ordering |
maximum weight clique problem
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Beisegel, Jesse | |
Chudnovsky, Maria, 1977- | |
Gurvich, Vladimir | |
Milanič, Martin, 1980- | 30211 |
Milanič, Mary Agnes | 39384 |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.