20.500.12556/RUP-22064 Primitive, edge-short, isometric, and pantochordal cycles Primitivni, povezavno kratki, izometrični in pantokordalni cikli 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₅. edge-short cycle chord block-graph complete multipartite graph wheel graphs cographs geodesic cycles Hamiltonian cycles povezavno kratek cikel tetiva blokovski graf polni veˇcdelni graf kolesni grafi kografi geodetski cikli Hamiltonovi cikli true false true Založba Univerze na Primorskem Angleški jezik Slovenski jezik Članek v reviji 2025-11-03 11:10:12 2025-11-03 11:10:12 2025-11-18 03:04:09 0000-00-00 00:00:00 2025 0 0 19 str. no. 2, [article no.] P2.01 Vol. 8 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2025-03-10 51 2590-9770 10.26493/2590-9770.1754.cd0 ADAM_Guzman,Gonzalez_Laffitte,Fujita,Stadler_2025.pdf ADAM_Guzman,Gonzalez_Laffitte,Fujita,Stadler_2025.pdf 1 2B073C0A892AABAD0C651205E400BCE3 8cae0ab665070fdefdfb21fc27b5b6633bbddde58c902ed0bca972e9c124bdff 40644b07-b89e-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=32009 Založba Univerze na Primorskem 0 0 0