1. Primitive, edge-short, isometric, and pantochordal cyclesGover E. C. Guzman, Marcos E. González Laffitte, André Fujita, Peter F. Stadler, 2025, original scientific article Abstract: 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₅.
Keywords: edge-short cycle, chord, block-graph, complete multipartite graph, wheel graphs, cographs, geodesic cycles, Hamiltonian cycles
Published in RUP: 03.11.2025; Views: 129; Downloads: 0
 Full text (478,50 KB) |
2. Basic tetravalent oriented graphs of independent-cycle typeNemanja Poznanović, Cheryl E. Praeger, 2025, original scientific article Abstract: The family OG(4) consisting of graph-group pairs (Γ, G), where Γ is a finite, connected, 4-valent graph admitting a G-vertex-, and G-edge-transitive, but not G-arc-transitive action, has recently been examined using a normal quotient methodology. A subfamily of OG(4) has been identified as ‘basic’, due to the fact that all members of OG(4) are normal covers of at least one basic pair. We provide an explicit classification of those basic pairs (Γ, G) which have at least two independent cyclic G-normal quotients (these are G-normal quotients which are not extendable to a common cyclic normal quotient).
Keywords: half-arc-transitive, vertex-transitive graph, edge-transitive graph, normal cover, cycle graph
Published in RUP: 21.10.2025; Views: 229; Downloads: 1
Full text (398,19 KB) |
3. On cyclic edge-connectivity of fullerenesKlavdija Kutnar, Dragan Marušič, 2008, original scientific article Abstract: A graph is said to be cyclically ▫$k$▫-edge-connected, if at least ▫$k$▫ edges must be removed to disconnect it into two components, each containing a cycle. Such a set of ▫$k$▫ edges is called a cyclic-k-edge cutset and it is called a trivial cyclic-k-edge cutset if at least one of the resulting two components induces a single ▫$k$▫-cycle. It is known that fullerenes, that is, 3-connected cubic planar graphs all of whose faces are pentagons and hexagons, are cyclically 5-edge-connected. In this article it is shown that a fullerene ▫$F$▫ containing a nontrivial cyclic-5-edge cutset admits two antipodal pentacaps, that is, two antipodal pentagonal faces whose neighboring faces are also pentagonal. Moreover, it is shown that ▫$F$▫ has a Hamilton cycle, and as a consequence at least ▫$15 \cdot 2^{n/20-1/2}$▫ perfect matchings, where ▫$n$▫ is the order of ▫$F$▫.
Keywords: graph, fullerene graph, cyclic edge-connectivity, hamilton cycle, perfect matching
Published in RUP: 03.04.2017; Views: 3344; Downloads: 143
 Link to full text |
