Iskanje po repozitoriju

Opis: Graph burning is a round-based game or process that discretely models the spread of influence throughout a network. We introduce a generalization of graph burning which applies to hypergraphs, as well as a variant called "lazy" hypergraph burning. Interestingly, lazily burning a graph is trivial, while lazily burning a hypergraph can be quite complicated. Moreover, the lazy burning model is a useful tool for analyzing the round-based model. One of our key results is that arbitrary hypergraphs do not satisfy a bound analogous to the one in the Burning Number Conjecture for graphs. We also obtain bounds on the burning number and lazy burning number of a hypergraph in terms of its parameters, and present several open problems in the field of (lazy) hypergraph burning.
Ključne besede: Combinatorial games on graphs, pursuit-evasion, graph searching, graph burning, hypergraph theory
Objavljeno v RUP: 18.08.2026; Ogledov: 332; Prenosov: 5
Celotno besedilo (413,95 KB)

Opis: We study reflection-symmetric realisations of symmetric graphs in the plane that allow a continuous symmetry and edge-length preserving deformation. To do so, we identify a necessary combinatorial condition on graphs with reflection-symmetric flexible realisations. This condition is based on a specific type of edge colouring, where edges are assigned one of three colours in a symmetric way. From some of these colourings we also construct concrete reflection-symmetric realisations with their corresponding symmetry preserving motion. We study also a specific class of reflection-symmetric realisations consisting of triangles and parallelograms.
Ključne besede: Flexible framework, rigidity, reflection symmetry, edge coloring
Objavljeno v RUP: 18.08.2026; Ogledov: 263; Prenosov: 6
Celotno besedilo (571,84 KB)

Opis: A ({3, m}; g)-semicubic graph is a graph where the degree of each vertex is either 3 or m and the girth of the graph is g; if m = 3 we have a cubic graph. In this paper, we construct families of semicubic graphs of even girth and small order using two different techniques. The first technique generalizes a previous construction, which glues cubic cages of girth g together at remote vertices (vertices at distance at least g/2). The second technique, the main content of this paper, produces bipartite semicubic ({3, m}; g)-graphs of even girth g using voltage graphs over ℤm. For girth g = 4t + 2, t ≥ 1, the constructed graphs have two vertices of degree m. For girth g = 4t, t ≥ 2, the construction produces graphs with exactly three vertices of degree m (of course, the remaining vertices are of degree 3 in both cases). In particular, we describe infinite families of ({3, m}; g)−semicubic graphs for g = {6, 8, 10, 12} for infinitely many values of m. The cases g = {6, 8} include the unique 6-cage and the unique 8-cage when m = 3. The families obtained in this paper for girth g = {10, 12} include examples of orders that match the best-known bounds for ({3, m}; g)−semicubic graphs until this moment.
Ključne besede: Graph, semicubic graph, girth, voltage graph
Objavljeno v RUP: 17.08.2026; Ogledov: 222; Prenosov: 4
Celotno besedilo (574,36 KB)

Opis: Let G be a group. The BCI problem asks whether two Haar graphs of G are isomorphic if and only if they are isomorphic by an element of an explicit list of isomorphisms. We first generalize this problem in a natural way and give a theoretical way to solve the isomorphism problem for the natural generalization. We then restrict our attention to abelian groups and, with an exception, reduce the problem to the isomorphism problem for a related quotient, component, or corresponding Cayley digraph. For Haar graphs of an abelian group of odd order with connection sets S those of Cayley graphs (i.e. S = -S), the exception does not exist. For Haar graphs of cyclic groups of odd order with connection sets those of a Cayley graph, among others, we solve the isomorphism problem.
Ključne besede: Cayley, Haar, CI, BCI, abelian group
Objavljeno v RUP: 17.08.2026; Ogledov: 228; Prenosov: 6
Celotno besedilo (511,43 KB)

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: 272; Prenosov: 3
Celotno besedilo (331,17 KB)