1. Clar numbers of leapfrog fullerenesJack E. Graver, Elizabeth J. Hartung, 2025 Opis: 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.
Ključne besede: chemical graph theory, fullerenes, leapfrog fullerenes, Clar number, Fries number, Kekulé structure, perfect matching
Objavljeno v RUP: 27.07.2026; Ogledov: 156; Prenosov: 3
 Celotno besedilo (1,70 MB)
Gradivo ima več datotek! Več... |
2. On the null spaces of quartic circulant graphsIvan Damnjanović, 2025 Opis: 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.
Ključne besede: circulant graph, quartic graph, null space, nut graph, singular graph, adjacency matrix
Objavljeno v RUP: 27.07.2026; Ogledov: 143; Prenosov: 2
Celotno besedilo (372,95 KB)
Gradivo ima več datotek! Več... |
3. Minimum entropy of graphs with given sizeStijn Cambie, Matteo Mazzamurro, 2025 Opis: 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.
Ključne besede: graph entropy
Objavljeno v RUP: 27.07.2026; Ogledov: 166; Prenosov: 3
Celotno besedilo (253,92 KB)
Gradivo ima več datotek! Več... |
4. Every atom-atom map for neutral molecules can be explained by electron pushing diagramsChristoph Flamm, Stefan Müller, Peter F. Stadler, 2025 Opis: 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.
Ključne besede: chemical reaction networks, graph transformations, reaction mechanisms
Objavljeno v RUP: 27.07.2026; Ogledov: 164; Prenosov: 5
Celotno besedilo (343,62 KB)
Gradivo ima več datotek! Več... |
5. Graph classes closed under self-intersectionKonrad K. Dabrowski, Vadim V. Lozin, Martin Milanič, Andrea Munaro, Daniël Paulusma, Viktor Zamaraev, 2026, objavljeni znanstveni prispevek na konferenci Opis: 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.
Ključne besede: graph classes, self-intersection closed, dichotomy, independent set, clique-width, treewidth
Objavljeno v RUP: 15.07.2026; Ogledov: 190; Prenosov: 6
Celotno besedilo (805,02 KB)
Gradivo ima več datotek! Več... |
6. Classification of pentavalent symmetric tricirculantsYasamin Khaefi, Klavdija Kutnar, Dragan Marušič, 2026, izvirni znanstveni članek Opis: 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.
Ključne besede: pentavalent graph, symmetric, semiregular automorphism, tricirculant
Objavljeno v RUP: 22.06.2026; Ogledov: 335; Prenosov: 10
Celotno besedilo (425,21 KB)
Gradivo ima več datotek! Več... |
7. 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, izvirni znanstveni članek Opis: 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.
Ključne besede: totally regular mixed graph, girth, projective plane, biaffine plane
Objavljeno v RUP: 04.06.2026; Ogledov: 366; Prenosov: 14
Celotno besedilo (480,02 KB)
Gradivo ima več datotek! Več... |
8. Group distance magic cubic graphsSylwia Cichacz, Štefko Miklavič, 2026, izvirni znanstveni članek Opis: 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.
Ključne besede: group distance magic labeling, Kotzig array, generalized Petersen graph
Objavljeno v RUP: 06.05.2026; Ogledov: 508; Prenosov: 9
Celotno besedilo (187,65 KB)
Gradivo ima več datotek! Več... |
9. Treewidth versus clique number. v. further connections with tree‐independence numberClaire Hilaire, Martin Milanič, Ðorđe Vasić, 2026, izvirni znanstveni članek Opis: We continue the study of (tw, ω)‐bounded graph classes, that is, hereditary graph classes in which large treewidth is witnessed by the presence of a large clique, and the relation of this property to boundedness of the tree‐independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milanič, and Štorgel in 2024. Dallard et al. showed that bounded tree‐independence number is sufficient for (tw, ω)‐boundedness, and conjectured that the converse holds. While this conjecture has been recently disproved, it is still interesting to determine classes where the conjecture holds; for example, the conjecture is still open for graph classes excluding an induced star, as well as for finitely many forbidden induced subgraphs. In this paper, we identify further families of graph classes where (tw, ω)‐boundedness is equivalent to bounded tree‐independence number. We settle a number of cases of finitely many forbidden induced subgraphs, obtain several equivalent characterizations of (tw, ω)-boundedness in subclasses of the class of complements of line graphs, and give a short proof of a recent result of Ahn, Gollin, Huynh, and Kwon [SODA 2025] establishing bounded tree-independence number for graphs excluding a fixed induced star and a fixed number of independent cycles.
Ključne besede: clique number, hereditary graph class, line graph, tree‐independence number, treewidth
Objavljeno v RUP: 09.04.2026; Ogledov: 604; Prenosov: 12
Celotno besedilo (1,87 MB)
Gradivo ima več datotek! Več... |
10. A note on Cayley nut graphs whose degree is divisible by fourIvan Damnjanović, 2026, izvirni znanstveni članek Opis: A nut graph is a nontrivial simple graph such that its adjacency matrix has a one-dimensional null space spanned by a full vector. Fowler et al. in 2020 proved that there is a d-regular vertex-transitive nut graph of order n only if 4 ∣ d, 2 ∣ n, n ≥ d + 4 or d≡₄2, 4 ∣ n and n ≥ d + 6. It was recently shown that there exists a d-regular circulant nut graph of order n if and only if 4 ∣ d, 2 ∣ n, d > 0, together with n ≥ d + 4 if d≡₈4 and n ≥ d + 6 if 8 ∣ d, as well as (n, d) ≠ (16, 8) (in the paper from 2024). In this paper, we demonstrate the existence of a d-regular Cayley nut graph of order n for each n and d with 4 ∣ d, d > 0 and 2 ∣ n, n ≥ d + 4, thereby finding all the orders attainable by a Cayley nut graph, or vertex-transitive nut graph, with a fixed degree divisible by four.
Ključne besede: nut graph, Cayley graph, vertex-transitive graph, circulant graph, graph spectrum, graph eigenvalue
Objavljeno v RUP: 23.03.2026; Ogledov: 890; Prenosov: 7
Celotno besedilo (404,59 KB) |
