| Naslov: | Primitive, edge-short, isometric, and pantochordal cycles |
|---|
| Avtorji: | ID Guzman, Gover E. C. (Avtor)
ID González Laffitte, Marcos E. (Avtor)
ID Fujita, André (Avtor)
ID Stadler, Peter F. (Avtor) |
|---|
| Datoteke: |  ADAM_Guzman,Gonzalez_Laffitte,Fujita,Stadler_2025.pdf (478,50 KB)
MD5: 2B073C0A892AABAD0C651205E400BCE3
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | ZUP - Založba Univerze na Primorskem
|
|---|
| Opis: | A cycle in a graph G is said to be primitive from its vertex x if at least one of its edges does not belong to any shorter cycle that passes through x. This type of cycle and an associated notion of extended neighborhoods play a key role in message-passing algorithms that compute spectral properties of graphs with short loops. Here, we investigate such primitive cycles and graphs without long primitive cycles in a more traditional graph-theoretic framework. We show that a cycle is primitive from all its vertices if and only if it is isometric. We call a cycle fully redundant cycles if it is not primitive from any of its vertices and show that fully redundant cycles, in particular, are not edge short, i.e., they cannot be represented as the edge-disjoint union of a single edge and two shortest paths in G. The families Rk and Lk of graphs with all cycles of length at least k + 1 being fully redundant and not edge-short, respectively, coincide for k = 3 and k = 4. In these graphs, all cycles of length at least k + 1 are pantochordal, i.e., each of their vertices is incident with a chord. None of these results generalizes to k ≥ 5. Moreover, R₃ = L₃ turn out to be the block graphs, and R₄ = L₄ are the graphs with complete multi-partite blocks. The cographs, finally, are shown to form a proper subset of R₅. |
|---|
| Ključne besede: | edge-short cycle, chord, block-graph, complete multipartite graph, wheel graphs, cographs, geodesic cycles, Hamiltonian cycles |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 10.03.2025 |
|---|
| Založnik: | Založba Univerze na Primorskem |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | 19 str. |
|---|
| Številčenje: | Vol. 8, no. 2, [article no.] P2.01 |
|---|
| PID: | 20.500.12556/RUP-22064  |
|---|
| UDK: | 51 |
|---|
| eISSN: | 2590-9770 |
|---|
| DOI: | 10.26493/2590-9770.1754.cd0 |
|---|
| Datum objave v RUP: | 03.11.2025 |
|---|
| Število ogledov: | 214 |
|---|
| Število prenosov: | 0 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
