We study a variant of the Cops and Robbers game on graphs in which the robbers damage the visited vertices, aiming to maximize the number of damaged vertices. For that game with one cop against $s$ robbers a conjecture was made by Carlson, Halloran and Reinhart that the cop can save three vertices from being damaged as soon as the maximum degree of the base graph is at least $\binom{s}{2} + 2$. We are able to verify the conjecture and prove that it is tight once we add the assumption that the base graph is triangle free. We also study the game without that assumption, disproving the conjecture in full generality and further attempting to locate the smallest maximum degree of a base graph which guarantees that the cop can save three vertices against $s$ robbers. We show that this number is between $2\binom{s}{2} - 3$ and $2\binom{s}{2} + 1$. Furthermore, after the game has been previously studied with one cop and multiple robbers, as well as with one robber and multiple cops, we initiate the study of the game with two cops and two robbers. In the case when the base graph is a cycle we determine the exact number of damaged vertices. Additionally, when the base graph is a path we provide bounds that differ by an additive constant.
Given a set of $n$ colored points $P \subset \mathbb{R}^d$ we wish to store $P$ such that, given some query region $Q$, we can efficiently report the colors of the points appearing in the query region, along with their frequencies. This is the \emph{color frequency reporting} problem. We study the case where query regions $Q$ are axis-aligned boxes or dominance ranges. If $Q$ contains $k$ colors, the main goal is to achieve ``strictly output sensitive'' query time $O(f(n) + k)$. Firstly, we show that, for every $s \in \{ 2, \dots, n \}$, there exists a simple $O(ns\log_s n)$ size data structure for points in $\mathbb{R}^2$ that allows frequency reporting queries in $O(\log n + k\log_s n)$ time. Secondly, we give a lower bound for the weighted version of the problem in the arithmetic model of computation, proving that with $O(m)$ space one can not achieve query times better than $Ω\left(ϕ\frac{\log (n / ϕ)}{\log (m / n)}\right)$, where $ϕ$ is the number of possible colors. This means that our data structure is near-optimal. We extend these results to higher dimensions as well. Thirdly, we present a transformation that allows us to reduce the space usage of the aforementioned data structure to $O(n(s ϕ)^\varepsilon \log_s n)$. Finally, we give an $O(n^{1+\varepsilon} + m \log n + K)$-time algorithm that can answer $m$ dominance queries in $\mathbb{R}^2$ with total output complexity $K$, while using only linear working space. new version for submission to DMTCS journal
Stijn Cambie, Jan Goedgebeur, Jorik Jooken, Tibo Van den Eede
For integers $k,g,d$, a $(k;g,d)$-cage (or simply girth-diameter cage) is a smallest $k$-regular graph of girth $g$ and diameter $d$ (if it exists). The order of a $(k;g,d)$-cage is denoted by $n(k;g,d)$. We determine asymptotic lower and upper bounds for the ratio between the order and the diameter of girth-diameter cages as the diameter goes to infinity. We also prove that this ratio can be computed in constant time for fixed $k$ and $g$. We theoretically determine the exact values $n(3;g,d)$, and count the number of corresponding girth-diameter cages, for $g \in \{4,5\}$. Moreover, we design and implement an exhaustive graph generation algorithm and use it to determine the exact order of several open cases and obtain -- often exhaustive -- sets of the corresponding girth-diameter cages. The largest case we generated and settled with our algorithm is a $(3;7,35)$-cage of order 136. 23 pages
Saúl A. Blanco, Mikhail P. Golubyatnikov, Elena V. Konstantinova, Natalia V. Maslova, Luka A. Nikiforov
The cubic pancake graphs are Cayley graphs over the symmetric group $\mathrm{Sym}_n$ generated by three prefix reversals. There is the following open problem: characterize all the sets of three prefix reversals that generate $\mathrm{Sym}_n$. As the largest prefix reversal of length $n$ is always included in a triple, we give a complete solution of the problem when any of the two smallest or the two largest lengths but $n$ are included in a triple of prefix reversals. Moreover, some conditions implying a triple of prefix reversals does not generate $\mathrm{Sym}_n$ are considered. Computational results on the diameter and the girth of some cubic pancake graphs are presented, and conjectures for future research are formulated. 26 pages, 4 tables, 3 figures, 27 references
Notions of graph similarity provide alternative perspective on the graph isomorphism problem and vice-versa. In this paper, we consider measures of similarity arising from mismatch norms as studied in Gervens and Grohe: the edit distance $δ_{\mathcal{E}}$, and the metrics arising from $\ell_p$-operator norms, which we denote by $δ_p$ and $δ_{|p|}$. We address the following question: can these measures of similarity be used to design polynomial-time approximation algorithms for graph isomorphism? We show that computing an optimal value of $δ_{\mathcal{E}}$ is \NP-hard on pairs of graphs with the same number of edges. In addition, we show that computing optimal values of $δ_p$ and $δ_{|p|}$ is \NP-hard even on pairs of $1$-planar graphs with the same degree sequence and bounded degree. These two results improve on previous known ones, which did not examine the restricted case where the pairs of graphs are required to have the same number of edges. Finally, we study similarity problems on strongly regular graphs and prove some near optimal inequalities with interesting consequences on the computational complexity of graph and group isomorphism.
Let $D$ be a digraph of order $p\geq5$ with minimum degree at least $p-1$ and with minimum semi-degree at least $p/2-1$. In his excellent and renowned paper, ``Long Cycles in Digraphs" (Proc. London Mathematical Society (3), 42 (1981), Thomassen fully characterized the following for $p=2n+1$: (i) $D$ has a cycle of length at least $2n$; and (ii) $D$ is Hamiltonian. Motivated by this result, and building on some of the ideas in Thomassen's paper, we investigated the Hamiltonicity (when $p$ is even) and pancyclcity (when $p$ is arbitrary) such digraphs. We have given a complete description of whether such digraphs are Hamiltonian ($p$ is even), are pancyclic ($p$ is arbitrary). Since the proof is very long, we have divided it into three parts. In this paper, we provide a full description of the following: (iii) for $k=3$ and $k=4$, the digraph $D$ contains a cycle of length $k$; and (iv) the digraph $D$ contains a pre-Hamiltonian cycle, i.e. a cycle of length $p-1$.
The relation between local structure and global cycle properties is a classical topic in graph theory. A graph $G$ is locally linear if $G[N(v)]$ is a path for every $v\in V(G)$. It is locally Hamiltonian or locally traceable if every vertex neighborhood induces a Hamiltonian or traceable graph, respectively. Earlier work by Pareek and Skupień, Skupień, Davies and Thomassen, Asratian and Oksimets, and de Wet and van Aardt studied extremal questions for these related graph classes. We prove that the minimum order of a nonhamiltonian locally linear graph is $12$ and that, for every integer $n\geq 12$, the minimum size of such a graph of order $n$ is $2n$. We also prove that every nontraceable locally linear graph of order $n$ has at least $2n+3$ edges. 16 pages, 4 figures
Given a point set, mostly a grid in our case, we seek upper and lower bounds on the number of curves that are needed to cover the point set. We say a curve covers a point if the curve passes through the point. We consider such coverings by monotonic curves, lines, orthoconvex curves, circles, etc. We also study a problem that is converse of the covering problem -- if a set of $n^2$ points in the plane is covered by $n$ lines then can we say something about the configuration of the points?
Rui Li, Gregory Gutin, He Zhang, Zhao Wang, Xiaoyan Zhang, Yaping Mao
Cartesian product networks are always regarded as a tool for ``combining'' two given networks with established properties to obtain a new one that inherits properties from both. For a graph $F=(V,E)$ and a set $S\subseteq V(F)$ of at least two vertices, \emph{an $S$-Steiner tree} or \emph{a Steiner tree connecting $S$} (or simply, \emph{an $S$-tree}) is a subgraph $T=(V',E')$ of $F$ that is a tree with $S\subseteq V'$. For $S\subseteq V(F)$ and $|S|\geq 2$, the {\it generalized local edge-connectivity} $λ(S)$ is the maximum number of edge-disjoint Steiner trees connecting $S$ in $F$. For an integer $k$ with $2\leq k\leq n$, the {\it generalized $k$-edge-connectivity} $λ_k(F)$ of a graph $F$ is defined as $λ_k(F)=\min\{λ(S)\,|\,S\subseteq V(F) \ and \ |S|=k\}$.In this paper, we give sharp upper and lower bounds for $λ_k(G\Box H)$, where $\Box$ is the Cartesian product operation, and $G,H$ are two graphs. 14 pages; 3 figures
The star chromatic number on a graph is the minimum number of colors in a proper vertex coloring forbidding any $P_4$ with two colors (bicolored). This problem was introduced by Grünbaum (1973) together with the acyclic coloring of graphs, where bicolored cycles are avoided. In this paper, we study a generalization of this problem, by considering proper vertex coloring on graphs forbidding bicolored paths of a fixed length, which was initially discussed by Alon, McDiarmid, and Reed (1991). Here, we study this problem on products of two paths. We show that at least 4 colors are needed to properly color the product of paths, $P_m\square P_n$, avoiding a bicolored $P_k,$ unless $n<k-2$ or $m<k-2.$ With this result, the above question is settled for all $k$ on 2-dimensional grids.
Whitney proved that 3-connected planar graphs admit a unique embedding on the sphere. In contrast, Enami investigated embeddings of 3-connected cubic planar graphs on non-spherical surfaces with non-negative Euler characteristic. He established that such an embedding exists if and only if the dual graph contains a particular subgraph. Here, strong embeddings are investigated motivated by the cycle double cover conjecture and the relation to triangulated surfaces. We provide a complete characterization of strong embeddings on the projective plane, the torus, and the Klein bottle in terms of a distinguished subset of Enami's subgraphs. This characterization not only deepens the structural understanding of graph embeddings on non-spherical surfaces, but also establishes a robust foundation for computing cycle double covers. As a direct consequence, we derive explicit criteria that determine when a graph does not admit a strong embedding on these surfaces-offering new tools for both theoretical analysis and algorithmic applications.
In 1977, Chung, Chung and Liu generalized the definition of the Ramsey number. They introduced the $s$-chromatic Ramsey number as follows. Let $1\leq s< t$ be integers and let $A_{1}, A_{2}, \dots, A_{c}$ be subsets with size $s$ of $[t]$, where $c= {t\choose s}$. For given graphs $G_{1}, G_{2}, \dots, G_{c}$, the {\it $s$-chromatic Ramsey number} $r^{s, t}(G_{1}, G_{2}, \dots, G_{c})$, is the minimum positive integer $N$ such that every $t$-coloring of $E(K_{N})$ yields a copy of $G_{i}$ whose edges are colored by colors in the color set $A_{i}$ for some $i\in [c]$. The {\it star-critical $s$-chromatic Ramsey number} $r_{*}^{s, t}(G_{1}, G_{2}, \dots, G_{c})$, is the minimum integer $\ell$ such that every $t$-coloring of the edges in $K_{N}- E(K_{1, N- 1- \ell})$ yields a copy of $G_{i}$ whose edges are colored by colors in the color set $A_{i}$ for some $i\in [c]$, where $N= r^{s, t}(G_{1}, G_{2}, \dots, G_{c})$. If $G_{1}= G_{2}= \dots= G_{c}= G$, then we simplify them to $r^{s, t}(G)$ (also called the {\it weakened Ramsey number}) and $r^{s, t}_{*}(G)$, respectively. In this paper, we determine all the values of $r^{s, t}(K_{1, m})$ and $r_{*}^{s, t}(K_{1, m})$, and part of the value of $r^{s, t}(K_{1, m_{1}}, K_{1, m_{2}}, \dots, K_{1, m_{c}})$.
Alexander Dobler, Stephen Kobourov, Debajyoti Mondal, Martin Nöllenburg
We consider hypergraph visualizations that represent vertices as points in the plane and hyperedges as curves passing through the points of their incident vertices. Specifically, we consider several different variants of this problem by (a) restricting the curves to be lines or line segments, (b) allowing two curves to cross if they do not share an element, or not; and (c) allowing two curves to overlap or not. We show $\exists\mathbb{R}$-hardness for six of the eight resulting decision problem variants and describe polynomial-time algorithms in some restricted settings. Lastly, we briefly touch on what happens if we allow the lines of the represented hyperedges to have bends - to this we generalize a counterexample to a long-standing result that was sometimes assumed to be correct. 24 pages, 12 figures
For a sequence of tasks, each with a positive integer period, the pinwheel scheduling problem involves finding a valid schedule in the sense that the schedule performs one task per day and each task is performed at least once every consecutive days of its period. It had been conjectured by Chan and Chin (1993) that there exists a valid schedule for any sequence of tasks with density, the sum of the reciprocals of each period, at most $\frac{5}{6}$. Recently, Kawamura (2024, in press) settled this conjecture affirmatively. In this paper we consider an extended version with real periods proposed by Kawamura, in which a valid schedule must perform each task $i$ having a real period~$a_{i}$ at least $l$ times in any $\lceil l a_{i} \rceil$ consecutive days for all positive integer $l$. We show that any sequence of tasks such that the periods take three distinct real values and the density is at most $\frac{5}{6}$ admits a valid schedule. We hereby conjecture that the conjecture of Chan and Chin is true also for real periods.
In a recent paper, Francis, Illickan, Jose and Rajendraprasad showed that every $n$-vertex plane graph $G$ has (under some natural restrictions) a vertex-partition into two sets $V_1$ and $V_2$ such that each $V_i$ is \emph{dominating} (every vertex of $G$ contains a vertex of $V_i$ in its closed neighbourhood) and \emph{face-hitting} (every face of $G$ is incident to a vertex of $V_i$). Their proof works by considering a supergraph $G'$ of $G$ that has certain properties, and among all such graphs, taking one that has the fewest edges. As such, their proof is not algorithmic. Their proof also relies on the 4-color theorem, for which a quadratic-time algorithm exists, but it would not be easy to implement. In this paper, we give a new proof that every $n$-vertex plane graph $G$ has (under the same restrictions) a vertex-partition into two dominating face-hitting sets. Our proof is constructive, and requires nothing more complicated than splitting a graph into 2-connected components, finding an ear decomposition, and computing a perfect matching in a 3-regular plane graph. For all these problems, linear-time algorithms are known and so we can find the vertex-partition in linear time. Preliminary version appeared at SOFSEM 2026
Recently, in the context of walks of hexagonal circle packings, interest has emerged in the family of skew Dyck paths with two variants of down-steps. These paths have steps $U, D_g, D_b, L=D_r$. Using generating functions, the kernel method and (in)finite linear systems, contributions to the (average) height and other enumerations are made. As in many similar instances, the average height is of order $\sqrt n$. Suggestions by two reviewers are included. Third version contains some formatting
K. Adaricheva, A. Mata, S. Silberger, A. Zamojska-Dzienio
We study maximal sublattices of finite semidistributive lattices via their complements. We focus on the conjecture that such complements are always intervals, which is known to be true for bounded lattices. Since the class of semidistributive lattices is the intersection of classes of join- and meet-semidistributive lattices, we study also complements for these classes, and in particular convex geometries of convex dimension 2, which is a subclass of join-semidistributive lattices. In the latter case, we describe the complements of maximal sublattices completely, as well as the procedure of finding all complements of maximal sublattices. 21 pages, 11 figures
Given a class of (undirected) graphs $\mathcal{C}$, we say that a Feedback Arc Set (FAS for short) $F$ is a $\mathcal{C}$-FAS if the graph induced by the edges of $F$ (forgetting their orientations) belongs to $\mathcal{C}$. We show that deciding if a tournament has a $\mathcal{C}$-FAS is NP-complete when $\mathcal{C}$ is the class of all forests. We are motivated by connections between $\mathcal{C}$-FAS and structural parameters of tournaments, such as the dichromatic number, the clique number of tournaments, and the strong Erdős-Hajnal property.
We consider partially ordered sets of combinatorial structures under consecutive orders, meaning that two structures are related when one embeds in the other such that `consecutive' elements remain consecutive in the image. Given such a partially ordered set, we may ask decidability questions about its avoidance sets: subsets defined by a finite number of forbidden substructures. Two such questions ask, given a finite set of structures, whether its avoidance set is well quasi-ordered (i.e. contains no infinite antichains) or atomic (i.e. cannot be expressed as the union of two proper subsets). Extending some recent new approaches, we will establish a general framework, which enables us to answer these problems for a wide class of combinatorial structures, including graphs, digraphs and collections of relations.
We consider the permutation analogue of Penney's game for words. Two players, in order, each choose a permutation of length $k\ge3$; then a sequence of independent random values from a continuous distribution is generated, until the relative order of the last $k$ numbers coincides with one of the chosen permutations, making that player the winner. We compute the winning probabilities for all pairs of permutations of length 3 and some pairs of length 4, showing that, as in the original version for words, the game is non-transitive. Our proofs introduce new bijections for consecutive patterns in permutations. We also give some formulas to compute the winning probabilities more generally, and conjecture a winning strategy for the second player when $k$ is arbitrary.
