{"?xml":{"@version":"1.0"},"edm:RDF":{"@xmlns:dc":"http://purl.org/dc/elements/1.1/","@xmlns:edm":"http://www.europeana.eu/schemas/edm/","@xmlns:wgs84_pos":"http://www.w3.org/2003/01/geo/wgs84_pos","@xmlns:foaf":"http://xmlns.com/foaf/0.1/","@xmlns:rdaGr2":"http://rdvocab.info/ElementsGr2","@xmlns:oai":"http://www.openarchives.org/OAI/2.0/","@xmlns:owl":"http://www.w3.org/2002/07/owl#","@xmlns:rdf":"http://www.w3.org/1999/02/22-rdf-syntax-ns#","@xmlns:ore":"http://www.openarchives.org/ore/terms/","@xmlns:skos":"http://www.w3.org/2004/02/skos/core#","@xmlns:dcterms":"http://purl.org/dc/terms/","edm:WebResource":[{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:DOC-KQBYU7DA/af8d61e0-3d32-4196-8116-75979ef0317e/PDF","dcterms:extent":"478 KB"},{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:DOC-KQBYU7DA/1f502611-8d28-4c7f-9a13-98efb3b2df6e/TEXT","dcterms:extent":"56 KB"},{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:DOC-KQBYU7DA/463bba78-6f79-49f4-aee4-048cbfb95960/PDF","dcterms:extent":"231 KB"},{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:DOC-KQBYU7DA/d9dc5a8b-0424-4a31-8d34-8d5593069779/TEXT","dcterms:extent":"7 KB"}],"edm:ProvidedCHO":{"@rdf:about":"URN:NBN:SI:DOC-KQBYU7DA","dcterms:issued":"2025","dc:creator":["Fujita, André","González Laffitte, Marcos E.","Guzman, Gover E. C.","Stadler, Peter F."],"dc:format":[{"@xml:lang":"sl","#text":"številka:2, article  p2.01"},{"@xml:lang":"sl","#text":"letnik:8"},{"@xml:lang":"sl","#text":"str. 1-19"}],"dc:identifier":["DOI:10.26493/2590-9770.1754.cd0","ISSN:2590-9770","COBISSID_HOST:285680387","URN:URN:NBN:SI:doc-KQBYU7DA"],"dc:language":"en","dc:publisher":{"@xml:lang":"sl","#text":"Fakulteta za matematiko, naravoslovje in informacijske tehnologije"},"dc:source":{"@xml:lang":"sl","#text":"The art of discrete and applied mathematics"},"dc:subject":[{"@xml:lang":"en","#text":"block-graph"},{"@xml:lang":"sl","#text":"blokovski graf"},{"@xml:lang":"en","#text":"chord"},{"@xml:lang":"en","#text":"cographs"},{"@xml:lang":"en","#text":"complete multipartite graph"},{"@xml:lang":"en","#text":"edge-short cycle"},{"@xml:lang":"en","#text":"geodesic cycles"},{"@xml:lang":"sl","#text":"geodetski cikli"},{"@xml:lang":"en","#text":"Hamiltonian cycles"},{"@xml:lang":"sl","#text":"Hamiltonovi cikli"},{"@xml:lang":"sl","#text":"kografi"},{"@xml:lang":"sl","#text":"polni večdelni graf"},{"@xml:lang":"sl","#text":"povezavno kratek cikel"},{"@xml:lang":"sl","#text":"tetiva"},{"@xml:lang":"en","#text":"wheel graphs"}],"dc:title":{"@xml:lang":"sl","#text":"Primitive, edge-short, isometric, and pantochordal cycles|"},"dc:description":[{"@xml:lang":"sl","#text":"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 R5"},{"@xml:lang":"sl","#text":"Cikel 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 R5"}],"edm:type":"TEXT","dc:type":[{"@xml:lang":"sl","#text":"znanstveno časopisje"},{"@xml:lang":"en","#text":"journals"},{"@rdf:resource":"http://www.wikidata.org/entity/Q361785"}]},"ore:Aggregation":{"@rdf:about":"http://www.dlib.si/?URN=URN:NBN:SI:DOC-KQBYU7DA","edm:aggregatedCHO":{"@rdf:resource":"URN:NBN:SI:DOC-KQBYU7DA"},"edm:isShownBy":{"@rdf:resource":"http://www.dlib.si/stream/URN:NBN:SI:DOC-KQBYU7DA/af8d61e0-3d32-4196-8116-75979ef0317e/PDF"},"edm:rights":{"@rdf:resource":"http://creativecommons.org/licenses/by/4.0/"},"edm:provider":"Slovenian National E-content Aggregator","edm:intermediateProvider":{"@xml:lang":"en","#text":"National and University Library of Slovenia"},"edm:dataProvider":{"@xml:lang":"sl","#text":"Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije"},"edm:object":{"@rdf:resource":"http://www.dlib.si/streamdb/URN:NBN:SI:DOC-KQBYU7DA/maxi/edm"},"edm:isShownAt":{"@rdf:resource":"http://www.dlib.si/details/URN:NBN:SI:DOC-KQBYU7DA"}}}}