1. Irregular graph labelings in Abelian groupsSylwia Cichacz, 2026, original scientific article Abstract: Let G⃗ = (V,E) be a directed graph of order n. If there exists a mapping ψ from E(G⃗) to an Abelian group Γ such that if we define a mapping φ_ψ from V(G⃗) to Γ by
φ_ψ(x) = ∑y ∈ N⁺(x)ψ(xy) − ∑y ∈ N⁻(x)ψ(yx), (x ∈ V(G⃗)), then φψ is injective, then such a labeling ψ is called Γ-irregular.
Recently it was showed that if n is large enough then G⃗ has a Γ-irregular labeling for any Γ such that |Γ| > (1 + ε)n (in the paper from Cichacz and Tuza from 2022). In this paper, we prove that if all weakly connected components of G⃗ are of size at least 4, then G⃗ has a Γ-irregular labeling for any finite group Γ such that |Γ| >= n + 5.
Keywords: finite Abelian group, directed graph, zero-sum sets
Published in RUP: 11.08.2026; Views: 62; Downloads: 0
 Full text (331,17 KB) |
2. Domination of subcubic planar graphs with large girthEun-Kyung Cho, Eric Culver, Stephen G. Hartke, Vesna Iršič Chenoweth, 2026, original scientific article Abstract: Since Reed conjectured in 1996 that the domination number of a connected cubic graph of order n is at most ⌈1/3n⌉, the domination number of cubic graphs has been extensively studied. It is now known that the conjecture is false in general, but Henning and Dorbec showed that it holds for graphs with girth at least 9. Zhu and Wu stated an analogous conjecture for 2-connected cubic planar graphs.
In this paper, we present a new upper bound for the domination number of subcubic planar graphs: if G is a subcubic planar graph with girth at least 8, then γ(G) < n₀ + 3/4 n₁ + 11/20 n₂ + 7/20 n₃, where n_i denotes the number of vertices in G of degree i, for i ∈ {0, 1, 2, 3}. We also prove that if G is a subcubic planar graph with girth at least 9, then γ(G) < n₀ + 13/17 n₁ + 9/17 n₂ + 6/17 n₃.
Keywords: domination, subcubic planar graph, upper bound
Published in RUP: 11.08.2026; Views: 44; Downloads: 0
Full text (635,04 KB) |
3. Clar numbers of leapfrog fullerenesJack E. Graver, Elizabeth J. Hartung, 2025 Abstract: A fullerene is a 3-regular plane graph with only hexagonal and pentagonal faces. The Fries number of a fullerene G, F(G), is the maximum number of benzene rings over all possible Kekulé structures for G. The Clar number of G, C(G), is the maximum number of independent benzene rings possible over all possible Kekulé structures for G. In this paper, we show that for leapfrog fullerenes, any set of faces attaining the Clar number is a subset of faces attaining the Fries number. This property is false for fullerenes in general (as shown in paper from E. J. Hartung in 2014). We then show that if L(G) is the leapfrog of a fullerene G, then the Clar number of L(G) is equal to the vertex independence number of G.
Keywords: chemical graph theory, fullerenes, leapfrog fullerenes, Clar number, Fries number, Kekulé structure, perfect matching
Published in RUP: 27.07.2026; Views: 159; Downloads: 3
Full text (1,70 MB)
This document has more files! More... |
4. On the null spaces of quartic circulant graphsIvan Damnjanović, 2025 Abstract: A nut graph is a nontrivial simple graph whose adjacency matrix has a one-dimensionalnull space such that its nonzero vectors contain no zero elements. For circulant graphs, itis known that they are nut if and only if their nullity is one. This fact was recently usedby the author in order to show that there exists ad-regular circulant nut graph of order n if and only if 4|d,2|n, d >0, alongside n ≥d+ 4 if d≡84, and n ≥d+ 6 if 8|d, and (n, d)̸= (16,8). Here, we deal with the quartic circulant graphs and disclose several results regarding their null spaces. First of all, we derive an explicit formula for computing the nullity of any quartic circulant graph. Furthermore, we provide the full nut graph characterization among these graphs. Finally, we determine all such graphs that attain the minimum or maximum nullity with respect to a given order. We also give the extremal null spaces of these graphs.
Keywords: circulant graph, quartic graph, null space, nut graph, singular graph, adjacency matrix
Published in RUP: 27.07.2026; Views: 152; Downloads: 2
Full text (372,95 KB)
This document has more files! More... |
5. Minimum entropy of graphs with given sizeStijn Cambie, Matteo Mazzamurro, 2025 Abstract: The first degree-based graph entropy of a graph is the Shannon entropy of its degree sequence. Its correct interpretation as a measure of uniformity of the degree sequence requires the determination of its extremal values given natural constraints. In this paper,we prove that the graphs with given size that minimize the first degree-based graph entropy are precisely the colex graphs.
Keywords: graph entropy
Published in RUP: 27.07.2026; Views: 179; Downloads: 3
Full text (253,92 KB)
This document has more files! More... |
6. Every atom-atom map for neutral molecules can be explained by electron pushing diagramsChristoph Flamm, Stefan Müller, Peter F. Stadler, 2025 Abstract: Chemical reactions can be understood as transformations of multigraphs (molecules)that preserve vertex labels (atoms) and degrees (sums of bonding and non-bonding electrons), thereby implying the atom-atom map of a reaction. The corresponding reaction mechanism is often described by an electron pushing diagram that explains the transformation by consecutive local relocations of individual edges (electron pairs). Here, we showthat every degree-preserving map between multigraphs, and thus every atom-atom map, can be generated by cyclic electron pushing. Moreover, it is always possible to decompose such an explanation into electron pushing diagrams involving only four electron pairs. This inturn implies that every reaction can be decomposed into a sequence of elementary reactions that involve at most two educt molecules and two product molecules. Hence, the requirement of a mechanistic explanation in terms of electron pushing and imaginary transition states involving only a small number of bonds does not impose a combinatorial constraint on the feasibility of hypothetical chemical reactions.
Keywords: chemical reaction networks, graph transformations, reaction mechanisms
Published in RUP: 27.07.2026; Views: 175; Downloads: 5
Full text (343,62 KB)
This document has more files! More... |
7. Graph classes closed under self-intersectionKonrad K. Dabrowski, Vadim V. Lozin, Martin Milanič, Andrea Munaro, Daniël Paulusma, Viktor Zamaraev, 2026, published scientific conference contribution Abstract: A graph class is monotone if it is closed under taking subgraphs. A monotone class defined by finitely many obstructions has bounded treewidth if and only if one of the obstructions is a tripod, i.e. a disjoint union of subdivided claws and paths. This dichotomy also characterizes exactly those monotone graph classes for which many NP-hard graph problems admit polynomial-time algorithms. These dichotomies do not extend to the universe of all hereditary classes. This leads to the question of whether we can extend known dichotomies for monotone classes to larger families of hereditary classes. We answer this question affirmatively by considering the family of hereditary graph classes closed under self-intersection. This family is known to be located strictly between the monotone and hereditary classes. We prove a new structural characterization of graphs in self-intersection-closed classes excluding a tripod. In contrast to monotone classes excluding a tripod, these classes do not necessarily have bounded treewidth; in fact, they do not even need to be sparse. We use our characterization to give a complete dichotomy for Maximum Independent Set, and its weighted variant, on self-intersection-closed classes defined by finitely many obstructions: these problems are in P if the class excludes a tripod and NP-hard otherwise. Our dichotomy generalizes several known results on Maximum Independent Set in the literature. We also apply our characterization to obtain a dichotomy for Maximum Induced Matching on self-intersection-closed classes of bipartite graphs defined by finitely many obstructions, and for Satisfiability and Counting Satisfiability on self-intersection-closed classes of (bipartite) incidence graphs defined by finitely many obstructions. Finally, we use our characterization to obtain a dichotomy for boundedness of clique-width for self-intersection-closed classes of bipartite graphs defined by finitely many obstructions.
Keywords: graph classes, self-intersection closed, dichotomy, independent set, clique-width, treewidth
Published in RUP: 15.07.2026; Views: 203; Downloads: 6
Full text (805,02 KB)
This document has more files! More... |
8. Classification of pentavalent symmetric tricirculantsYasamin Khaefi, Klavdija Kutnar, Dragan Marušič, 2026, original scientific article Abstract: A graph $\Gamma$ is said to be an {\em $m$-Cayley graph} on a group $G$ ($|G|\ne 1$) if its automorphism group contains a semiregular subgroup isomorphic to $G$ having $m$ orbits on the vertex set of $\Gamma$. If $G$ is cyclic and $m=3$ then $\Gamma$ is called a {\em tricirculant}. A graph is said to be {\em symmetric} if its automorphism group acts transitively on the set of its arcs. In this paper, it is shown that with the exception of $K_6$, no connected pentavalent symmetric tricirculant exists.
Keywords: pentavalent graph, symmetric, semiregular automorphism, tricirculant
Published in RUP: 22.06.2026; Views: 341; Downloads: 10
Full text (425,21 KB)
This document has more files! More... |
9. Extremal totally regular mixed graphs and partially oriented incidence graphs of projective and biaffine planesTatiana Bagin Jajcay, Robert Jajcay, György Kiss, István Porupsánszki, 2025, original scientific article Abstract: An (r, z; g)-mixed graph is a graph containing both edges and darts satisfying the regularity property that each vertex of the graph is incident to r edges, z ingoing and z outgoing darts (called total regularity), and being of oriented girth g, i.e., containing an oriented cycle of length g, and no shorter oriented cycles. The problem addressed in this paper is analogous to the Cage Problem and calls for determining the orders of the smallest totally regular (r, z; g)-mixed graphs. We derive several upper and lower bounds on the orders of such minimal graphs, study the relations between these extremal graphs and their non-oriented or digraphical counterparts, and focus on properties of totally regular mixed graphs obtained by replacing some of the edges of the incidence graphs of projective and biaffine planes by darts. We also introduce two constructions based on introducing additional edges or darts into induced subgraphs of these incidence graphs.
Keywords: totally regular mixed graph, girth, projective plane, biaffine plane
Published in RUP: 04.06.2026; Views: 374; Downloads: 14
Full text (480,02 KB)
This document has more files! More... |
10. Group distance magic cubic graphsSylwia Cichacz, Štefko Miklavič, 2026, original scientific article Abstract: A $\Gamma$-distance magic labeling of a graph $G = (V, E)$ with $|V| = n$ is a bijection $\ell$ from $V$ to an Abelian group $\Gamma$ of order $n$, for which there exists $\mu \in \Gamma$, such that the weight $w(x) =\sum_{y\in N(x)}\ell(y)$ of every vertex $x \in V$ is equal to $\mu$. In this case, the element $\mu$ is called the magic constant of $G$. A graph $G$ is called a group distance magic if there exists a $\Gamma$-distance magic labeling of $G$ for every Abelian group $\Gamma$ of order $n$. In this paper, we focused on cubic $\Gamma$-distance magic graphs as well as some properties of such graphs.
Keywords: group distance magic labeling, Kotzig array, generalized Petersen graph
Published in RUP: 06.05.2026; Views: 517; Downloads: 9
Full text (187,65 KB)
This document has more files! More... |
