478 KB56 KB231 KB7 KB2025Fujita, AndréGonzález Laffitte, Marcos E.Guzman, Gover E. C.Stadler, Peter F.številka:2, article p2.01letnik:8str. 1-19DOI:10.26493/2590-9770.1754.cd0ISSN:2590-9770COBISSID_HOST:285680387URN:URN:NBN:SI:doc-KQBYU7DAenFakulteta za matematiko, naravoslovje in informacijske tehnologijeThe art of discrete and applied mathematicsblock-graphblokovski grafchordcographscomplete multipartite graphedge-short cyclegeodesic cyclesgeodetski cikliHamiltonian cyclesHamiltonovi ciklikografipolni večdelni grafpovezavno kratek cikeltetivawheel graphsPrimitive, edge-short, isometric, and pantochordal cycles|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, R3 = L3 turn out to be the block graphs, and R4 = L4 are the graphs with complete multi-partite blocks. The cographs, finally, are shown to form a proper subset of R5Cikel v grafu G je primitiven za svojo točko x, če najmanj ena njegovih povezav ne pripada nobenemu krajšemu ciklu, ki gre skozi x. Tovrstni cikel in z njim povezan pojem razširjenih okolic igrata ključno vlogo v algoritmih za posredovanje sporočil, ki izračunavajo spektralne lastnosti grafov s kratkimi zankami. Tukaj raziskujemo takšne primitivne cikle in grafe brez dolgih primitivnih ciklov v tradicionalnejšem okviru teorije grafov. Pokažemo, da je cikel primitiven za vse svoje točke natanko takrat, ko je izometričen. Cikel imenujemo popolnoma redundanten, če ni primitiven za nobeno svojo točko, in pokažemo, da popolnoma redundantni cikli niso povezavno kratki, to pomeni, da se jih ne da predstaviti kot povezavno disjunktno unijo ene same povezave in dveh krajših poti v grafu G. Družini Rk in Lk grafov z vsemi cikli dolžine najmanj k+1, ki so popolnoma redundantni oz. niso povezavno kratki, sovpadata za k=3 in k=4. V teh grafih so vsi cikli dolžine najmanj k+1 pantokordalni, kar pomeni, da je vsaka od točk incidentna neki tetivi. Noben od teh rezultatov se ne posploši na k?5. Poleg tega se je izkazalo, da so R3=L3 blokovski grafi, in da so R4=L4 grafi s popolnimi večdelnimi bloki. Nazadnje pokažemo, da kografi tvorijo pravo podmnožico družine R5TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije