1. Treewidth versus clique number. v. further connections with tree‐independence numberClaire Hilaire, Martin Milanič, Ðorđe Vasić, 2026, original scientific article Abstract: We continue the study of (tw, ω)‐bounded graph classes, that is, hereditary graph classes in which large treewidth is witnessed by the presence of a large clique, and the relation of this property to boundedness of the tree‐independence number, a graph parameter introduced independently by Yolov in 2018 and by Dallard, Milanič, and Štorgel in 2024. Dallard et al. showed that bounded tree‐independence number is sufficient for (tw, ω)‐boundedness, and conjectured that the converse holds. While this conjecture has been recently disproved, it is still interesting to determine classes where the conjecture holds; for example, the conjecture is still open for graph classes excluding an induced star, as well as for finitely many forbidden induced subgraphs. In this paper, we identify further families of graph classes where (tw, ω)‐boundedness is equivalent to bounded tree‐independence number. We settle a number of cases of finitely many forbidden induced subgraphs, obtain several equivalent characterizations of (tw, ω)-boundedness in subclasses of the class of complements of line graphs, and give a short proof of a recent result of Ahn, Gollin, Huynh, and Kwon [SODA 2025] establishing bounded tree-independence number for graphs excluding a fixed induced star and a fixed number of independent cycles.
Keywords: clique number, hereditary graph class, line graph, tree‐independence number, treewidth
Published in RUP: 09.04.2026; Views: 144; Downloads: 9
 Full text (1,87 MB)
This document has more files! More... |
2. A note on Cayley nut graphs whose degree is divisible by fourIvan Damnjanović, 2026, original scientific article Abstract: A nut graph is a nontrivial simple graph such that its adjacency matrix has a one-dimensional null space spanned by a full vector. Fowler et al. in 2020 proved that there is a d-regular vertex-transitive nut graph of order n only if 4 ∣ d, 2 ∣ n, n ≥ d + 4 or d≡₄2, 4 ∣ n and n ≥ d + 6. It was recently shown that there exists a d-regular circulant nut graph of order n if and only if 4 ∣ d, 2 ∣ n, d > 0, together with n ≥ d + 4 if d≡₈4 and n ≥ d + 6 if 8 ∣ d, as well as (n, d) ≠ (16, 8) (in the paper from 2024). In this paper, we demonstrate the existence of a d-regular Cayley nut graph of order n for each n and d with 4 ∣ d, d > 0 and 2 ∣ n, n ≥ d + 4, thereby finding all the orders attainable by a Cayley nut graph, or vertex-transitive nut graph, with a fixed degree divisible by four.
Keywords: nut graph, Cayley graph, vertex-transitive graph, circulant graph, graph spectrum, graph eigenvalue
Published in RUP: 23.03.2026; Views: 147; Downloads: 4
Full text (404,59 KB) |
3. |
4. Random walks and the electronic structure of grapheneNino Bašić, Patrick W. Fowler, Barry T. Pickup, Primož Potočnik, 2026, original scientific article Abstract: Results from the mathematical literature on random walks reveal a closed-form analytical expression for the ▫$\pi$▫-energy and bond number of graphene in the simplest tight-binding model and its Hartree-Fock Hubbard extension. Closed-form expressions follow for all ▫$\pi$▫ spectral moments of graphene. Bond numbers of carbon and boron nitride (BN) zigzag nanotubes are found as finite sums, with graphene and hexagonal boron nitride sheets as asymptotes.
Keywords: graph theory, random walks, graphene, bond number, tight-binding model, spectral moments, Hubbard model, zigzag nanotubes, hexagonal boron nitride, gamma function
Published in RUP: 10.03.2026; Views: 285; Downloads: 6
Full text (4,70 MB)
This document has more files! More... |
5. 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, original scientific article Abstract: 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.
Keywords: cubic graph, perfect matching, colouring defect, Fulkerson Conjecture, Fan and Raspaud Conjecture
Published in RUP: 03.03.2026; Views: 304; Downloads: 7
Full text (313,05 KB) |
6. NERVIS : An Interactive System for Graph-Based Exploration and Editing of Named EntitiesUroš Šmajdek, Ciril Bohak, 2025, independent scientific component part or a chapter in a monograph Abstract: We present an interactive visualization system for exploring named entities and their relationships across document collections. The system is designed around a graph-based representation that integrates three types of nodes: documents, entity mentions, and entities. Connections capture two key relationship types: (i) identical entities across contexts, and (ii) co-locations of mentions within documents. Multiple coordinated views enable users to examine entity occurrences, discover clusters of related mentions, and explore higher-level entity group relationships. To support flexible and iterative exploration, the interface offers fuzzy views with approximate connections, as well as tools for interactively editing the graph by adding or removing links, entities, and mentions, as well as editing entity terms. Additional interaction features include filtering, mini-map navigation, and export options to JSON or image formats for downstream analysis and reporting. This approach contributes to human-centered exploration of entity-rich text data by combining graph visualization, interactive refinement, and adaptable perspectives on relationships.
Keywords: Named Entity Visualization, Graph Exploration, Interactive Visualization
Published in RUP: 30.01.2026; Views: 353; Downloads: 0
Full text (839,67 KB) |
7. Type-based computation of knowledge graph statisticsIztok Savnik, Kiyoshi Nitta, Riste Škrekovski, Nikolaus Augsten, 2025, original scientific article Abstract: 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.
Keywords: knowledge graphs, RDF stores, graph database systems
Published in RUP: 16.01.2026; Views: 541; Downloads: 2
Full text (677,80 KB)
This document has more files! More... |
8. Nut digraphsNino Bašić, Patrick W. Fowler, Maxine M. McCarthy, Primož Potočnik, 2026, original scientific article Abstract: A nut graph is a simple graph whose kernel is spanned by a single full vector (i.e., the adjacency matrix has a single zero eigenvalue and all non-zero kernel eigenvectors have no zero entry). We classify generalisations of nut graphs to nut digraphs: a digraph whose kernel (resp. co-kernel) is spanned by a full vector is dextro-nut (resp. laevo-nut); a bi-nut digraph is both laevo- and dextro-nut; an ambi-nut digraph is a bi-nut digraph where kernel and co-kernel are spanned by the same vector; a digraph is inter-nut if the intersection of the kernel and co-kernel is spanned by a full vector. It is known that a nut graph is connected, leafless and non-bipartite. It is shown here that an ambi-nut digraph is strongly connected, non-bipartite (i.e., has a non-bipartite underlying graph) and has minimum in-degree and minimum out-degree of at least 2. Refined notions of core and core-forbidden vertices apply to singular digraphs. Infinite families of nut digraphs and systematic coalescence, crossover and multiplier constructions are introduced. Relevance of nut digraphs to topological physics is discussed.
Keywords: nut graph, core graph, nullity, directed graph, nut digraph, dextro-nut, laevo-nut, bi-nut, ambi-nut, inter-nut, dextro-core vertex, laevo-core vertex, graph spectra
Published in RUP: 09.01.2026; Views: 381; Downloads: 28
Full text (873,25 KB)
This document has more files! More... |
9. Nut graphs with a prescribed number of vertex and edge orbitsNino Bašić, Ivan Damnjanović, 2026, original scientific article Abstract: A nut graph is a nontrivial graph whose adjacency matrix has a one-dimensional null space spanned by a vector without zero entries. Recently, it was shown that a nut graph has more edge orbits than vertex orbits. It was also shown that for any even $r \geq 2$ and any $k \geq r + 1$, there exist infinitely many nut graphs with r vertex orbits and k edge orbits. Here, we extend this result by finding all the pairs $(r, k)$ for which there exists a nut graph with $r$ vertex orbits and $k$ edge orbits. In particular, we show that for any $k \geq 2$, there are infinitely many Cayley nut graphs with $k$ edge orbits and $k$ arc orbits.
Keywords: nut graph, vertex orbit, edge orbit, arc orbit, Cayley graph, automorphism
Published in RUP: 09.01.2026; Views: 408; Downloads: 5
Full text (445,35 KB)
This document has more files! More... |
10. Linear bounds on treewidth in terms of excluded planar minorsJ. Pascal Gollin, Kevin Hendrey, Sang-il Oum, Bruce Reed, 2025, original scientific article Abstract: One of the fundamental results in graph minor theory is that for every planar graph $H$, there is a minimum integer $f(H)$ such that graphs with no minor isomorphic to $H$ have treewidth at most $f(H)$. A lower bound for $f(H)$ can be obtained by considering the maximum integer $k$ such that $H$ contains $k$ vertex-disjoint cycles. There exists a graph of treewidth $\Omega(k\log k)$ which does not contain $k$ vertex-disjoint cycles, from which it follows that $f(H) = \Omega(k\log k)$. In particular, if $f(H)$ is linear in $\lvert V(H) \rvert$ for graphs $H$ from a subclass of planar graphs, it is necessary that $n$-vertex graphs from the class contain at most $\lvert V(H) \rvert$ vertex-disjoint cycles. We ask whether this is also a sufficient condition, and demonstrate that this is true for classes of planar graphs with bounded component size. For an $n$-vertex graph $H$ which is a disjoint union of $r$ cycles, we show that ${f(H) \leq 3n/2 + O(r^2 \log r)}$, and improve this to $f(H)$≤$n$+O(√$n$) when $r$=2. In particular this bound is linear when $r$=O(√$n$/logn). We present a linear bound for $f(H)$ when $H$ is a subdivision of an $r$-edge planar graph for any constant~$r$. We also improve the best known bounds for $f(H)$ when $H$ is the wheel graph or the 4×4 grid, obtaining a bound of 160 for the latter.
Keywords: graph minor, treewidth, cycle packing
Published in RUP: 05.01.2026; Views: 673; Downloads: 2
Full text (613,98 KB)
This document has more files! More... |
