1. Regular colouring defect of a cubic graph and the conjectures of Fan-Raspaud and FulkersonJán Karabáš, Edita Máčajová, Roman Nedela, Martin Škoviera, 2026, izvirni znanstveni članek Opis: We introduce a new invariant of a cubic graph – its regular colouring defect – which is defined as the smallest number of edges left uncovered by any collection of three perfect matchings that have no edge in common. This invariant is a modification of colouring defect, an invariant introduced by Steffen in 2025, whose definition does not require the empty intersection condition. In this paper we discuss the relationship of this invariant to the well-known conjectures of Fulkerson (1971) and Fan and Raspaud (1994) and prove that colouring defect and regular colouring defect can be arbitrarily far apart.
Ključne besede: cubic graph, perfect matching, colouring defect, Fulkerson Conjecture, Fan and Raspaud Conjecture
Objavljeno v RUP: 03.03.2026; Ogledov: 420; Prenosov: 12
 Celotno besedilo (313,05 KB) |
2. Clar and Fries structures for fullerenesPatrick W. Fowler, Wendy Myrvold, Rebecca L. Vandenberg, Elizabeth J. Hartung, Jack E. Graver, 2026, 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: 491; Prenosov: 2
Celotno besedilo (843,13 KB) |
3. Finding a perfect matching of F_2^n with prescribed differencesBenedek Kovács, 2026, 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: 409; Prenosov: 1
Celotno besedilo (467,06 KB) |
4. Perfect matching cuts partitioning a graph into complementary subgraphsDiane Castonguay, Erika M. M. Coelho, Hebert Coelho, Julliano R. Nascimento, Uéverton S. Souza, 2025, izvirni znanstveni članek Opis: In PARTITION INTO COMPLEMENTARY SUBGRAPHS (COMP-SUB) we are given a graph G = (V, E), and an edge set property Π, and asked whether G can be decomposed into two graphs, H and its complement H̄, for some graph H, in such a way that the edge cut [V(H), V(H̄)] satisfies the property Π. Motivated by previous work, we consider COMP-SUB(Π) when the property Π=PM specifies that the edge cut of the decomposition is a perfect matching. We prove that COMP-SUB(PM) is GI-hard when the graph G is C_5-free or G is {C_k ≥ 7, C̄_k ≥ 7}-free. On the other hand, we show that COMP-SUB(PM) is polynomial-time solvable on hole-free graphs and on P5-free graphs. Furthermore, we present characterizations of COMP-SUB(PM) on chordal, distance-hereditary, and extended P_4-laden graphs.
Ključne besede: graph partitioning, complementary subgraphs, perfect matching, matching cut, graph isomorphism
Objavljeno v RUP: 21.10.2025; Ogledov: 805; Prenosov: 4
Celotno besedilo (420,94 KB) |
5. On cyclic edge-connectivity of fullerenesKlavdija Kutnar, Dragan Marušič, 2008, izvirni znanstveni članek Opis: 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$▫.
Ključne besede: graph, fullerene graph, cyclic edge-connectivity, hamilton cycle, perfect matching
Objavljeno v RUP: 03.04.2017; Ogledov: 3806; Prenosov: 146
 Povezava na celotno besedilo |
