1. Domination in cylindrical graphsJosé Antonio Martínez, Mercè Mora, María Luz Puertas, Javier Tejel, 2026, izvirni znanstveni članek Opis: The domination number γ(Cm □ Pn) of the Cartesian product Cm □ Pn of a cycle and a path has been computed when m ≡ 0, 2 (mod 5). In the remaining cases m ≡ 1, 3, 4 (mod 5), exact formulae for γ(Cm □ Pn) have been determined when either n ≤ 22 or m ≤ 30. For the rest of the cases, only lower and upper bounds for γ(Cm □ Pn) are known. In this paper, we study γ(Cm □ Pn) when m ≡ 1, 3, 4 (mod 5). In particular, we compute γ(Cm □ Pn) if 30 ≤ m ≡ 1 (mod 5) and n ≥ 22, and we provide tighter lower and upper bounds for γ(Cm □ Pn) if m ≡ 3, 4 (mod 5).
Ključne besede: Domination in graphs, Cartesian product graphs, tropical matrix multiplication
Objavljeno v RUP: 20.08.2026; Ogledov: 248; Prenosov: 6
 Celotno besedilo (1,43 MB) |
2. Extending graph burning to hypergraphsAndrea C. Burgess, Caleb W. Jones, David A. Pike, 2026, izvirni znanstveni članek 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: 308; Prenosov: 5
Celotno besedilo (413,95 KB) |
3. Some results on ▫$\sigma_t$▫-irregularitySlobodan Filipovski, Darko Dimitrov, Martin Knor, Riste Škrekovski, 2026, izvirni znanstveni članek Opis: The (\sigma_t)-irregularity (or sigma total index) is a graph invariant defined as [ \sigma_t(G)=\sum_{{u,v}\subseteq V(G)}(d(u)-d(v))^2, ] where (d(z)) denotes the degree of a vertex (z). This irregularity measure was proposed by Réti in 2019 and recently rediscovered by Dimitrov and Stevanović in 2023. In this paper, we remark that (\sigma_t(G)=n^2\operatorname{Var}(G)), where (\operatorname{Var}(G)) is the degree variance of the graph. We show that among all complete bipartite graphs on (n) vertices, one of the corresponding complete bipartite graphs whose part sizes are closest to (n(2-\sqrt{2})/4) and (n(2+\sqrt{2})/4) has the maximum sigma total index. Moreover, various upper and lower bounds for (\sigma_t)-irregularity are provided. In this direction, we establish a relation between the graph energy (\mathcal{E}(G)) and (\sigma_t)-irregularity and derive bounds related to the Laplacian eigenvalues of the graph.
Ključne besede: irregularity, total irregularity, energy of graphs, Laplacian eigenvalues
Objavljeno v RUP: 14.08.2026; Ogledov: 216; Prenosov: 6
Celotno besedilo (335,30 KB)
Gradivo ima več datotek! Več... |
4. Every Q-polynomial distance-regular graph is sharp over $\mathbb{R}$Blas Fernández, Jae-Ho Lee, Jongyook Park, 2026, izvirni znanstveni članek Opis: Let $\Gamma$ be a $Q$-polynomial distance-regular graph, and let $T=T(x)$ denote its Terwilliger algebra with respect to a fixed vertex $x$. While it has long been known that every irreducible $T$-module over the complex field is sharp, the corresponding result over the real field had remained unproved. In this work, we establish that every irreducible $T$-module over $\mathbb{R}$ is also sharp. This resolves the real analogue of a theorem of Nomura and Terwilliger and shows that every $Q$-polynomial distance-regular graph is sharp over both $\mathbb{R}$ and $\mathbb{C}$. As further consequences, we prove that the complexification of an irreducible real $T$-module remains irreducible, characterize isomorphism classes via complexification, determine the Wedderburn decomposition of the real Terwilliger algebra, and show that several naturally arising subalgebras are commutative and consist entirely of symmetric matrices. These results clarify the relationship between the real and complex representation theories of the Terwilliger algebra and
provide new structural insight into $Q$-polynomial distance-regular graphs.
Ključne besede: distance-regular graphs, Q-polynomial property, Terwilliger algebra
Objavljeno v RUP: 17.07.2026; Ogledov: 346; Prenosov: 5
 Povezava na datoteko |
5. Uniform equations for bipartite graphs and the center of a Terwilliger algebraŠtefko Miklavič, Giusy Monzillo, 2026, izvirni znanstveni članek Opis: The uniform property was introduced by P. Terwilliger in the context of graded posets and was later extended to connected bipartite graphs. The core of this definition involves the so called uniform equations that must be satisfied. Let Γ denote a connected bipartite graph. Fix a vertex x of Γand let T=T(x) denote the corresponding Terwilliger algebra. In this paper, we study the connections between the uniform equations and the center of T. We show that these uniform equations give rise to a certain subspace of the center of T. Changing the logical direction, we show that if a matrix of a particular form belongs to the center of T, then uniform equations are satisfified.
Ključne besede: uniform equations, center of a Terwilliger algebra, bipartite graphs
Objavljeno v RUP: 08.05.2026; Ogledov: 489; Prenosov: 18
Celotno besedilo (966,73 KB)
Gradivo ima več datotek! Več... |
6. |
7. Decompositions of the wreath product of certain directed graphs into directed hamiltonian cyclesAlice Lacaze-Masmonteil, 2026, izvirni znanstveni članek Opis: We affirm several special cases of a conjecture that first appears in Alspach et al. (1987) which stipulates that the wreath (lexicographic) product of two hamiltonian decomposable di- rected graphs is also hamiltonian decomposable. Specifically, we show that the wreath product of hamiltonian decomposable directed graph G, such that |V (G)| is even and |V (G)| ⩾ 3, with a directed m-cycle such that m ⩾ 4 or the complete symmetric directed graph on m vertices such that m ⩾ 3, is hamiltonian decomposable. We also show the wreath product of a directed n-cycle, where n is even, with a directed m-cycle, where m ∈ {2, 3}, is not hamiltonian decomposable.
Ključne besede: wreath product, decompositions, hamiltonian cycle, directed graphs
Objavljeno v RUP: 17.03.2026; Ogledov: 561; Prenosov: 38
Celotno besedilo (538,63 KB) |
8. Type-based computation of knowledge graph statisticsIztok Savnik, Kiyoshi Nitta, Riste Škrekovski, Nikolaus Augsten, 2025, izvirni znanstveni članek Opis: We propose a formal model of a knowledge graph (abbr. KG) that classifies the ground triples into sets that correspond to the triple types. The triple types are partially ordered by the sub-type relation. Consequently, the sets of ground triples that are the interpretations of triple types are partially ordered by the subsumption relation. The types of triple patterns restrict the sets of ground triples, which need to be addressed in the evaluation of triple patterns, to the interpretation of the types of triple patterns. Therefore, a schema graph of a KG should include all triple types that are likely to be determined as the types of triple patterns. The stored schema graph consists of the selected triple types that are stored in a KG and the complete schema graph includes all valid triple types of KG. We propose choosing the schema graph, which consists of the triple types from a strip around the stored schema graph, i.e., the triple types from the stored schema graph and some adjacent levels of triple types with respect to the sub-type relation. Given a selected schema graph, the statistics are updated for each ground triple t from a KG. First, we determine the set of triple types stt from the schema graph that are affected by adding a triple t to an RDF store. Finally, the statistics of triple types from the set stt are updated.
Ključne besede: knowledge graphs, RDF stores, graph database systems
Objavljeno v RUP: 16.01.2026; Ogledov: 1043; Prenosov: 6
Celotno besedilo (677,80 KB)
Gradivo ima več datotek! Več... |
9. Automorphisms and quotients of 2-colored quasi best match graphsAnnachiara Korchmaros, 2026, izvirni znanstveni članek Opis: 2-colored quasi best match graphs (2-qBMGs) are directed graphs that arose in evolution theory. Investigations of 2-qBMGs have mostly focused on computational issues. However, 2-qBMGs also have relevant properties for structural graph theory; in particular, their undirected underlying graph is free from induced paths and cycles of size at least 6. In this paper, results on the structure of the automorphism groups of 2-qBMGs are obtained, which shows how to construct 2-qBMGs with large automorphism groups.
Ključne besede: group of automorphisms, bipartite graphs, phylogenetics
Objavljeno v RUP: 05.01.2026; Ogledov: 1507; Prenosov: 6
Celotno besedilo (498,12 KB) |
10. On the leaves of graph search treesRobert Scheffler, 2026, 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: 894; Prenosov: 39
Celotno besedilo (515,71 KB) |
