1. Decompositions of the wreath product of certain directed graphs into directed hamiltonian cyclesAlice Lacaze-Masmonteil, 2026, original scientific article Abstract: We affirm several special cases of a conjecture that first appears in Alspach et al. (1987) which stipulates that the wreath (lexicographic) product of two hamiltonian decomposable di- rected graphs is also hamiltonian decomposable. Specifically, we show that the wreath product of hamiltonian decomposable directed graph G, such that |V (G)| is even and |V (G)| ⩾ 3, with a directed m-cycle such that m ⩾ 4 or the complete symmetric directed graph on m vertices such that m ⩾ 3, is hamiltonian decomposable. We also show the wreath product of a directed n-cycle, where n is even, with a directed m-cycle, where m ∈ {2, 3}, is not hamiltonian decomposable.
Keywords: wreath product, decompositions, hamiltonian cycle, directed graphs
Published in RUP: 17.03.2026; Views: 454; Downloads: 21
 Full text (538,63 KB) |
2. Plane triangulations without large 2-treesAllan Bickle, Gunnar Brinkmann, 2026, original scientific article Abstract: In 1995 Leizhen Cai asked whether each plane triangulation has a spanning 2-tree. This question was recently answered in the negative by Bickle. He gave a plane triangulation on 38 vertices for which each 2-tree contained in it misses at least one vertex. We give a smaller example on 29 vertices and show that for each c>0 there are plane triangulations P=(V,E), so that each 2-tree that is a subgraph of P contains fewer than c|V| vertices. We also give a lower bound for the size of a maximum 2-tree in plane triangulations by proving that each plane triangulation P=(V,E) contains a 2-tree on at least log_2 (|V|-1)+4 -log_2 3 vertices. Finally we give structural criteria based on the decomposition trees of Jackson and Yu that guarantee the existence of spanning 2-trees in plane triangulations. The results are proven by using the close relation of 2-trees to hamiltonian cycles and to induced trees in the dual for plane triangulations without separating triangles.
Keywords: 2-tree, triangulation, Hamiltonian cycle, Yutsis partition
Published in RUP: 21.12.2025; Views: 623; Downloads: 3
Full text (339,53 KB) |
3. 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: 833; Downloads: 4
Full text (478,50 KB) |
4. Določeni razredi (hiper)grafov in njihove algebraične lastnosti : doktorska disertacijaPaweł Petecki, 2016, doctoral dissertation Keywords: hypergraph, hamiltonian cycle, decomposition, double generalized Petersen graph, automorphism group, vertex-transitive, sign graph, L-eigenvalue, lollipop graph
Published in RUP: 09.08.2016; Views: 5557; Downloads: 38
 Link to full text |
