1. Clar and Fries structures for fullerenesPatrick W. Fowler, Wendy Myrvold, Rebecca L. Vandenberg, Elizabeth J. Hartung, Jack E. Graver, 2025, izvirni znanstveni članek Opis: Fries and Clar numbers are qualitative indicators of stability in conjugated π systems. For a given Kekulé structure, call any hexagon that contains three double bonds benzenoid. The Fries number is the maximum number of benzenoid hexagons, whereas the Clar number is the maximum number of independent benzenoid hexagons, in each case taken over all Kekulé structures. A Kekulé structure that realises the Fries (Clar) number is a Fries (Clar) structure. For benzenoids, it is not known whether every Fries structure is also a Clar structure. For fullerenes C_n, it is known that some Clar structures in large examples correspond to no Fries structure. We show that Fries structures that are not Clar occur early: examples where some Fries structure is not Clar start at C_34, and examples where no Fries structure is Clar start at C_48. Hence, it is unsafe to use fullerene Fries structures as routes to Clar number. However, Fries structures often describe the neutral fullerene better than a Clar structure, e.g. in rationalising bond lengths in the experimental isomer of C_60. Conversely, an extension of Clar sextet theory suggests the notion of anionic Clar number for fullerene anions, where both pentagons and hexagons may support sextets.
Ključne besede: chemical graph theory, fullerenes, benzenoids, Clar, Fries, Kekule, perfect matching
Objavljeno v RUP: 22.12.2025; Ogledov: 109; Prenosov: 1
 Celotno besedilo (843,13 KB) |
2. On the leaves of graph search treesRobert Scheffler, 2025, izvirni znanstveni članek Opis: Graph searches and their respective search trees are widely used in algorithmic graph theory. The problem whether a given spanning tree can be a graph search tree has been considered for different searches, graph classes and search tree paradigms. Similarly, the question whether a particular vertex can be visited last by some search has been studied extensively in recent years. We combine these two problems by considering the question whether a vertex can be a leaf of a graph search tree. We show that for particular search trees, including DFS trees, this problem is easy if we allow the leaf to be the first vertex of the search ordering. We contrast this result by showing that the problem becomes hard for many searches, including DFS and BFS, if we forbid the leaf to be the first vertex. Additionally, we present several structural and algorithmic results for search tree leaves of chordal graphs.
Ključne besede: graph search, graph search trees, leaves, chordal graphs
Objavljeno v RUP: 21.12.2025; Ogledov: 138; Prenosov: 1
Celotno besedilo (515,71 KB) |
3. Tight upper bounds for the p-anionic Clar number of fullerenesAaron Slobodin, Wendy Myrvold, Gary MacGillivray, Patrick W. Fowler, 2025, izvirni znanstveni članek Opis: A fullerene is an all-carbon molecule with a polyhedral structure where each atom is bonded to three other atoms and each face is either a pentagon or a hexagon. Fullerenes correspond to 3-regular planar graphs whose faces have sizes 5 or 6. The p-anionic Clar number C_(p)(G) of a fullerene G is equal to p + h, where h is maximized over all choices of p + h independent faces (exactly p pentagons and h hexagons) the deletion of whose vertices leave a graph with a perfect matching. This definition is motivated by the chemical observation that pentagonal rings can accommodate an extra electron, so that the pentagons of a
fullerene with charge −p, compete with the hexagons to host ‘Clar sextets’ of six electrons, and pentagons will preferentially acquire the p excess electrons of the anion.
Tight upper bounds are established for the p-anionic Clar number of fullerenes for p > 0. The upper bounds are derived via graph theoretic arguments and new results on minimal cyclic-k-edge cutsets in IPR fullerenes (fullerenes that have all pentagons pairwise disjoint). These bounds are shown to be tight by infinite families of fullerenes that achieve them.
Ključne besede: chemical graph theory, anionic Clar number, fullerenes
Objavljeno v RUP: 21.12.2025; Ogledov: 151; Prenosov: 1
Celotno besedilo (1,11 MB) |
4. Finding a perfect matching of F_2^n with prescribed differencesBenedek Kovács, 2025, izvirni znanstveni članek Opis: We consider the following question by Balister, Győri and Schelp: given 2^{n-1} nonzero vectors in F_2^n with zero sum, is it always possible to partition the elements of F_2^n into pairs such that the difference between the two elements of the i-th pair is equal to the i-th given vector for every i? An analogous question in F_p, which is a case of the so-called "seating couples" problem, has been resolved by Preissmann and Mischler in 2009. In this paper, we prove the conjecture in F_2^n in the case when the number of distinct values among the given difference vectors is at most n-2log(n)-1, and also in the case when at least a fraction 1/2+ε of the given vectors are equal (for all ε>0 and n sufficiently large based on ε).
Ključne besede: binary vector spaces, seating couples, prescribed differences, perfect matching, functional batch code, graph colourings
Objavljeno v RUP: 21.12.2025; Ogledov: 137; Prenosov: 0
Celotno besedilo (467,06 KB) |
5. Tight toughness variant condition for fractional k-factorsWei Gao, Weifan Wang, Yaojun Chen, 2025, izvirni znanstveni članek Opis: The toughness t(G) of graph G is formalized as the minimum ratio of |S| and ω(G − S) over all vertex subsets S subject to ω(G − S) > 1. As the unique variant parameter of toughness, τ(G) is formulated as the minimum ratio of |S| and ω(G − S) − 1 traversing all the vertex subset S restricted to ω(G − S) ≥ 2. The extant contributions reveal that there is a substantial correlation between toughness and fractional factors. However, there is still a paucity of solid studies on toughness variants τ(G). This work provides several theoretical underpinnings for the tight toughness variant bound for a graph G which admits a fractional k-factor. To be specific, a graph G has a fractional k-factor if τ(G) > k for k ≥ 3 and if τ(G)>3/2 for k = 2. The sharpness of the given bounds is explained by counterexamples.
Ključne besede: graph, toughness, toughness variant, fractional k-factor
Objavljeno v RUP: 21.12.2025; Ogledov: 147; Prenosov: 0
Celotno besedilo (1,11 MB) |
6. Treewidth is NP-complete on cubic graphsHans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dušan Knop, Paloma T. Lima, Martin Milanič, Sebastian Ordyniak, Sukanya Pandey, Ondřej Suchý, 2025, izvirni znanstveni članek Opis: The concept of avoidable paths in graphs was introduced by Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius in 2019 as a common generalization of avoidable vertices and simplicial paths. In 2020, Bonamy, Defrain, Hatzel, and Thiebaut proved that every graph containing an induced path of order k also contains an avoidable induced path of the same order. They also asked whether one could generalize this result to other avoidable structures, leaving the notion of avoidability up to interpretation. In this paper, we address this question: we specify the concept of avoidability for arbitrary graphs equipped with two terminal vertices. We provide both positive and negative results, some of which are related to a recent work by Chudnovsky, Norin, Seymour, and Turcotte in 2024. We also discuss several open questions.
Ključne besede: treewidth, cubic graph, NP'completeness
Objavljeno v RUP: 18.12.2025; Ogledov: 117; Prenosov: 0
Celotno besedilo (550,69 KB)
Gradivo ima več datotek! Več... |
7. Conformality of minimal transversals of maximal cliquesEndre Boros, Vladimir Gurvich, Martin Milanič, Dmitry Tikhanovsky, Yushi Uno, 2026, izvirni znanstveni članek Opis: Given a hypergraph ℋ, the dual hypergraph of ℋis the hypergraph of all minimal transversals of ℋ. A hypergraph is conformal if it is the family of maximal cliques of a graph. In a recent work, Boros, Gurvich, Milanič, and Uno (Journal of Graph Theory, 2025) studied conformality of dual hypergraphs and proved several results related to this property, leading in particular to a polynomial-time algorithm for recognizing graphs in which, for any fixed k, all minimal transversals of maximal cliques have size at most k. In this follow-up work, we provide a novel aspect to the study of graph clique transversals, by considering the dual conformality property from the perspective of graphs. More precisely, we study graphs for which the family of minimal transversals of maximal cliques is conformal. Such graphs are called clique dually conformal (CDC for short). It turns out that the class of CDC graphs is a rich generalization of the class of P4-free graphs. As our main results, we completely completely characterize CDC graphs within the families of triangle-free graphs and split graphs. Both characterizations lead to polynomial-time recognition algorithms. Generalizing the fact that every P4-free graph is CDC, we also show that the class of CDC graphs is closed under substitution, in the strong sense that substituting a graph H for a vertex of a graph G results in a CDC graph if and only if both G and H are CDC.
Ključne besede: maximal clique, minimal transversal, conformal hypergraph, triangle-free graph, split graph
Objavljeno v RUP: 16.12.2025; Ogledov: 168; Prenosov: 2
Celotno besedilo (1,65 MB)
Gradivo ima več datotek! Več... |
8. On {k}-Roman graphsKenny Bešter Štorgel, Nina Chiarelli, Lara Fernández, J. Pascal Gollin, Claire Hilaire, Valeria Alejandra Leoni, Martin Milanič, 2025, objavljeni znanstveni prispevek na konferenci Opis: For a positive integer k, a {k}-Roman dominating function of a graph G = (V, E) is a function f : V → {0, 1, . . . , k} satisfying f (N(v)) ≥ k for each vertex v ∈ V with f (v) = 0. Every graph G satisfies γ{Rk}(G) ≤ kγ(G), where γ{Rk}(G) denotes the minimum weight of a {k}-Roman dominating function of G and γ(G) is the domination number of G. In this work we study graphs for which the equality is reached, called {k}-Roman graphs. This extends the concept of {k}-Roman trees studied by Wang et al. in 2021 to gen- eral graphs. We prove that for every k ≥ 3, the problem of recognizing {k}-Roman graphs is NP-hard, even when restricted to split graphs. We provide partial answers to the question of which split graphs are {2}-Roman: we characterize {2}-Roman split graphs that can be decomposed with respect to the split join operation into two smaller split graphs and classify the {k}-Roman property within two specific families of split graphs that are prime with respect to the split join operation: suns and their complements.
Ključne besede: graph domination, {k}-Roman domination, {k}-Roman graph, split graph, split join, NP-completeness
Objavljeno v RUP: 16.12.2025; Ogledov: 176; Prenosov: 2
Celotno besedilo (395,09 KB)
Gradivo ima več datotek! Več... |
9. Nut graphs with a given automorphism groupNino Bašić, Patrick W. Fowler, 2025, izvirni znanstveni članek Opis: A nut graph is a simple graph of order 2 or more for which the adjacency matrix has a single zero eigenvalue such that all nonzero kernel eigenvectors have no zero entry (i.e. are full). It is shown by construction that every finite group can be represented as the group of automorphisms of infinitely many nut graphs. It is further shown that such nut graphs exist even within the class of regular graphs; the cases where the degree is 8, 12, 16, 20 or 24 are realised explicitly.
Ključne besede: nut graph, graph automorphism, automorphism group, nullity, graph spectra, f-universal
Objavljeno v RUP: 25.11.2025; Ogledov: 358; Prenosov: 4
Celotno besedilo (526,71 KB)
Gradivo ima več datotek! Več... |
10. On cubic polycirculant nut graphsNino Bašić, Ivan Damnjanović, 2025, izvirni znanstveni članek Opis: A nut graph is a nontrivial simple graph whose adjacency matrix contains a one-dimensional null space spanned by a vector without zero entries. Moreover, an $\ell$-circulant graph is a graph that admits a cyclic group of automorphisms having $\ell$ vertex orbits of equal size. It is not difficult to observe that there exists no cubic $1$-circulant nut graph or cubic $2$-circulant nut graph, while the full classification of all the cubic $3$-circulant nut graphs was recently obtained (Damnjanović et al. in Electron. J. Comb. 31(2):P2.31, 2024). Here, we investigate the existence of cubic $\ell$-circulant nut graphs for $\ell \geq 4$ and show that there is no cubic $4$-circulant nut graph or cubic $5$-circulant nut graph by using a computer-assisted proof. Furthermore, we rely on a construction based approach in order to demonstrate that there exist infinitely many cubic $\ell$-circulant nut graphs for any fixed $\ell \in \{6, 7\}$ or $\ell \geq 9$.
Ključne besede: nut graph, polycirculant graph, cubic graph, pregraph, voltage graph
Objavljeno v RUP: 19.11.2025; Ogledov: 246; Prenosov: 5
Celotno besedilo (581,83 KB)
Gradivo ima več datotek! Več... |
