1. Conformality of minimal transversals of maximal cliquesEndre Boros, Vladimir Gurvich, Martin Milanič, Dmitry Tikhanovsky, Yushi Uno, 2026, original scientific article Abstract: Given a hypergraph ℋ, the dual hypergraph of ℋis the hypergraph of all minimal transversals of ℋ. A hypergraph is conformal if it is the family of maximal cliques of a graph. In a recent work, Boros, Gurvich, Milanič, and Uno (Journal of Graph Theory, 2025) studied conformality of dual hypergraphs and proved several results related to this property, leading in particular to a polynomial-time algorithm for recognizing graphs in which, for any fixed k, all minimal transversals of maximal cliques have size at most k. In this follow-up work, we provide a novel aspect to the study of graph clique transversals, by considering the dual conformality property from the perspective of graphs. More precisely, we study graphs for which the family of minimal transversals of maximal cliques is conformal. Such graphs are called clique dually conformal (CDC for short). It turns out that the class of CDC graphs is a rich generalization of the class of P4-free graphs. As our main results, we completely completely characterize CDC graphs within the families of triangle-free graphs and split graphs. Both characterizations lead to polynomial-time recognition algorithms. Generalizing the fact that every P4-free graph is CDC, we also show that the class of CDC graphs is closed under substitution, in the strong sense that substituting a graph H for a vertex of a graph G results in a CDC graph if and only if both G and H are CDC.
Keywords: maximal clique, minimal transversal, conformal hypergraph, triangle-free graph, split graph
Published in RUP: 16.12.2025; Views: 25; Downloads: 2
 Full text (1,65 MB)
This document has more files! More... |
2. On {k}-Roman graphsKenny Bešter Štorgel, Nina Chiarelli, Lara Fernández, J. Pascal Gollin, Claire Hilaire, Valeria Alejandra Leoni, Martin Milanič, 2025, published scientific conference contribution Abstract: For a positive integer k, a {k}-Roman dominating function of a graph G = (V, E) is a function f : V → {0, 1, . . . , k} satisfying f (N(v)) ≥ k for each vertex v ∈ V with f (v) = 0. Every graph G satisfies γ{Rk}(G) ≤ kγ(G), where γ{Rk}(G) denotes the minimum weight of a {k}-Roman dominating function of G and γ(G) is the domination number of G. In this work we study graphs for which the equality is reached, called {k}-Roman graphs. This extends the concept of {k}-Roman trees studied by Wang et al. in 2021 to gen- eral graphs. We prove that for every k ≥ 3, the problem of recognizing {k}-Roman graphs is NP-hard, even when restricted to split graphs. We provide partial answers to the question of which split graphs are {2}-Roman: we characterize {2}-Roman split graphs that can be decomposed with respect to the split join operation into two smaller split graphs and classify the {k}-Roman property within two specific families of split graphs that are prime with respect to the split join operation: suns and their complements.
Keywords: graph domination, {k}-Roman domination, {k}-Roman graph, split graph, split join, NP-completeness
Published in RUP: 16.12.2025; Views: 29; Downloads: 2
Full text (395,09 KB)
This document has more files! More... |
3. Nut graphs with a given automorphism groupNino Bašić, Patrick W. Fowler, 2025, original scientific article Abstract: A nut graph is a simple graph of order 2 or more for which the adjacency matrix has a single zero eigenvalue such that all nonzero kernel eigenvectors have no zero entry (i.e. are full). It is shown by construction that every finite group can be represented as the group of automorphisms of infinitely many nut graphs. It is further shown that such nut graphs exist even within the class of regular graphs; the cases where the degree is 8, 12, 16, 20 or 24 are realised explicitly.
Keywords: nut graph, graph automorphism, automorphism group, nullity, graph spectra, f-universal
Published in RUP: 25.11.2025; Views: 300; Downloads: 4
Full text (526,71 KB)
This document has more files! More... |
4. On cubic polycirculant nut graphsNino Bašić, Ivan Damnjanović, 2025, original scientific article Abstract: A nut graph is a nontrivial simple graph whose adjacency matrix contains a one-dimensional null space spanned by a vector without zero entries. Moreover, an $\ell$-circulant graph is a graph that admits a cyclic group of automorphisms having $\ell$ vertex orbits of equal size. It is not difficult to observe that there exists no cubic $1$-circulant nut graph or cubic $2$-circulant nut graph, while the full classification of all the cubic $3$-circulant nut graphs was recently obtained (Damnjanović et al. in Electron. J. Comb. 31(2):P2.31, 2024). Here, we investigate the existence of cubic $\ell$-circulant nut graphs for $\ell \geq 4$ and show that there is no cubic $4$-circulant nut graph or cubic $5$-circulant nut graph by using a computer-assisted proof. Furthermore, we rely on a construction based approach in order to demonstrate that there exist infinitely many cubic $\ell$-circulant nut graphs for any fixed $\ell \in \{6, 7\}$ or $\ell \geq 9$.
Keywords: nut graph, polycirculant graph, cubic graph, pregraph, voltage graph
Published in RUP: 19.11.2025; Views: 224; Downloads: 5
Full text (581,83 KB)
This document has more files! More... |
5. A unified Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groupsJ. Pascal Gollin, Kevin Hendrey, O-joung Kwon, Sang-il Oum, Youngho Yoo, 2025, original scientific article Abstract: In 1965, Erdős and Pósa proved that there is an (approximate) duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold for odd cycles, and Dejter and Neumann-Lara asked in 1988 to find all pairs (l, z) of integers where such a duality holds for the family of cycles of length l modulo z. We characterise all such pairs, and we further generalise this characterisation to cycles in graphs labelled with a bounded number of abelian groups, whose values avoid a bounded number of elements of each group. This unifies almost all known types of cycles that admit such a duality, and it also provides new results. Moreover, we characterise the obstructions to such a duality in this setting, and thereby obtain an analogous characterisation for cycles in graphs embeddable on a fixed compact orientable surface.
Keywords: Erdős-Pósa property, cycle packing, group-labelled graph
Published in RUP: 17.11.2025; Views: 247; Downloads: 8
Full text (1,17 MB)
This document has more files! More... |
6. On bipartite (1,1,k)-mixed graphsCristina Dalfó, Grahame Erskine, Geoffrey Exoo, Miquel Àngel Fiol, James Tuite, 2025, original scientific article Abstract: Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this paper, we consider the case where such graphs are bipartite and in which the undirected and directed degrees are one. The best graphs, in terms of the number of vertices, are presented for small diameters. Moreover, two infinite families of such graphs with diameter k and number of vertices of the order of 2k/2 are proposed, one of them being totally regular (1,1)-mixed graphs. In addition, we present two more infinite families called chordal ring and chordal double ring mixed graphs, which are bipartite and related to tessellations of the plane. Finally, we give an upper bound that improves the Moore bound for bipartite mixed graphs for r = z = 1.
Keywords: mixed graph, degree/diameter problem, Moore bound, bipartite graph
Published in RUP: 03.11.2025; Views: 290; Downloads: 0
Full text (628,98 KB) |
7. On extremal (almost) edge-girth-regular graphsGabriela Araujo-Pardo, György Kiss, István Porupsánszki, 2025, original scientific article Abstract: A k-regular graph of girth g is called an edge-girth-regular graph, or an egr-graph for short, if each of its edges is contained in exactly λ distinct g-cycles. An egr-graph is called extremal for the triple (k, g, λ) if has the smallest possible order. We prove that some graphs arising from incidence graphs of finite planes are extremal egr-graphs. We also prove new lower bounds on the order of egr-graphs.
Keywords: edge-girth-regular graph, cage problem, finite biaffine planes
Published in RUP: 03.11.2025; Views: 232; Downloads: 1
Full text (547,76 KB) |
8. |
9. A sharp upper bound for the harmonious total chromatic number of graphs and multigraphsMarién Abreu, John Baptist Gauci, Davide Mattiolo, Giuseppe Mazzuoccolo, Federico Romaniello, Christian Rubio-Montiel, Tommaso Traetta, 2025, original scientific article Abstract: A proper total colouring of a graph G is called harmonious if it has the further property that when replacing each unordered pair of incident vertices and edgeswith their colours, then no pair of colours appears twice. The smallest number of colours for it to exist is called the harmonious total chromatic number of G, denoted by h_t(G). Here, we give a general upper bound for h_t(G) in terms of the order n of G. Our two main results are obvious consequences of the computation of the harmonious total chromatic number of the complete graph Kn and of the complete multigraph λK_n, where λ is the number of edges joining each pair of vertices of Kn. In particular, Araujo-Pardo et al. have recently shown that 3/2 n ≤ h_t(K_n)≤ 5/3 n + θ(1). In this paper, we prove that h_t(K_n) = ⌈3/2 n⌉ except for h_t(K₁) = 1 and h_t(K₄) = 7; therefore, h_t(G)≤ ⌈3/2 n⌉, for every graph G on n > 4 vertices. Finally, we extend such a result to the harmonious total chromatic number of the complete multigraph λKn and as a consequence show that h_t(G) ≤ (λ-1)(2⌈n/2⌉-1)+⌈3n/2⌉ for n > 4, where G is a multigraph such that λ is the maximum number of edges between any two vertices.
Keywords: total colouring, harmonious colouring, complete graphs, complete multigraphs, Levi graph
Published in RUP: 03.11.2025; Views: 283; Downloads: 2
Full text (387,22 KB) |
10. Banff designs: difference methods for coloring incidence graphsMarco Buratti, Francesca Merola, Anamari Nakić, Christian Rubio-Montiel, 2025, original scientific article Abstract: We present some results on the harmonious colourings of the Levi graph of a 2-design, focusing on Steiner 2-design. It is easily seen that the harmonious chromatic number of such a Levi graph is at least the number of points of the design: we study and construct Banff designs, that is designs such that this lower bound is attained.
Keywords: Harmonious chromatic number, Levi graph, combinatorial design
Published in RUP: 03.11.2025; Views: 225; Downloads: 2
Full text (426,74 KB) |
