Iskanje po repozitoriju

Opis: 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.
Ključne besede: finite Abelian group, directed graph, zero-sum sets
Objavljeno v RUP: 11.08.2026; Ogledov: 73; Prenosov: 0
Celotno besedilo (331,17 KB)

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: 161; Prenosov: 3
Celotno besedilo (1,70 MB)
Gradivo ima več datotek! Več...

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: 180; Prenosov: 3
Celotno besedilo (253,92 KB)
Gradivo ima več datotek! Več...

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: 204; Prenosov: 6
Celotno besedilo (805,02 KB)
Gradivo ima več datotek! Več...

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: 374; Prenosov: 14
Celotno besedilo (480,02 KB)
Gradivo ima več datotek! Več...