Discrete Mathematics & Theoretical Computer Science |

We examine the classic game of Cops and Robbers played on models of dynamic graphs, that is, graphs evolving over discrete time steps. At each time step, a graph instance is generated as a subgraph of the underlying graph of the model. The cops and the robber take their turns on the current graph instance. The cops win if they can capture the robber at some point in time. Otherwise, the robber wins. In the offline case, the players are fully aware of the evolution sequence, up to some finite time horizon T. We provide a O(n 2k+1 T) algorithm to decide whether a given evolution sequence for an underlying graph with n vertices is k-cop-win via a reduction to a reachability game. In the online case, there is no knowledge of the evolution sequence, and the game might go on forever. Also, each generated instance is required to be connected. We provide a nearly tight characterization for sparse underlying graphs, i.e., with at most linear number of edges. We prove λ + 1 cops suffice to capture the robber in any underlying graph with n − 1 + λ edges. Further, we define a family of underlying graphs with n−1+λ edges where λ−1 cops are necessary (and sufficient) for capture.

In 1946, Erdős posed the distinct distance problem, which seeks to findthe minimum number of distinct distances between pairs of points selected fromany configuration of $n$ points in the plane. The problem has since beenexplored along with many variants, including ones that extend it into higherdimensions. Less studied but no less intriguing is Erdős' distinct angleproblem, which seeks to find point configurations in the plane that minimizethe number of distinct angles. In their recent paper "Distinct Angles inGeneral Position," Fleischmann, Konyagin, Miller, Palsson, Pesikoff, and Wolfuse a logarithmic spiral to establish an upper bound of $O(n^2)$ on the minimumnumber of distinct angles in the plane in general position, which prohibitsthree points on any line or four on any circle. We consider the question of distinct angles in three dimensions and providebounds on the minimum number of distinct angles in general position in thissetting. We focus on pinned variants of the question, and we examine explicitconstructions of point configurations in $\mathbb{R}^3$ which useself-similarity to minimize the number of distinct angles. Furthermore, westudy a variant of the distinct angles question regarding distinct angle chainsand provide bounds on the minimum number of distinct chains in $\mathbb{R}^2$and $\mathbb{R}^3$.

In 2020 Bang-Jensen et. al. generalized the Hajós join of two graphs to theclass of digraphs and generalized several results for vertex colorings indigraphs. Although, as a consequence of these results, a digraph can beobtained by Hajós constructions (directed Hajós join and identifyingnon-adjacent vertices), determining the Hajós constructions to obtain thedigraph is a complex problem. In particular, Bang-Jensen et al. posed theproblem of determining the Hajós operations to construct the symmetric5-cycle from the complete symmetric digraph of order 3 using only Hajósconstructions. We successfully adapted a rank-based genetic algorithm to solvethis problem by the introduction of innovative recombination and mutationoperators from graph theory. The Hajós Join became the recombination operatorand the identification of independent vertices became the mutation operator. Inthis way, we were able to obtain a sequence of only 16 Hajós operations toconstruct the symmetric cycle of order 5.

We study a family of generalizations of Edge Dominating Set on directedgraphs called Directed $(p,q)$-Edge Dominating Set. In this problem an arc$(u,v)$ is said to dominate itself, as well as all arcs which are at distanceat most $q$ from $v$, or at distance at most $p$ to $u$. First, we give significantly improved FPT algorithms for the two mostimportant cases of the problem, $(0,1)$-dEDS and $(1,1)$-dEDS (that correspondto versions of Dominating Set on line graphs), as well as polynomial kernels.We also improve the best-known approximation for these cases from logarithmicto constant. In addition, we show that $(p,q)$-dEDS is FPT parameterized by$p+q+tw$, but W-hard parameterized by $tw$ (even if the size of the optimal isadded as a second parameter), where $tw$ is the treewidth of the underlyinggraph of the input. We then go on to focus on the complexity of the problem on tournaments. Here,we provide a complete classification for every possible fixed value of $p,q$,which shows that the problem exhibits a surprising behavior, including caseswhich are in P; cases which are solvable in quasi-polynomial time but not in P;and a single case $(p=q=1)$ which is NP-hard (under randomized reductions) andcannot be solved in sub-exponential time, under standard assumptions.

Given a boolean predicate $\Pi$ on labeled networks (e.g., proper coloring,leader election, etc.), a self-stabilizing algorithm for $\Pi$ is a distributedalgorithm that can start from any initial configuration of the network (i.e.,every node has an arbitrary value assigned to each of its variables), andeventually converge to a configuration satisfying $\Pi$. It is known thatleader election does not have a deterministic self-stabilizing algorithm usinga constant-size register at each node, i.e., for some networks, some of theirnodes must have registers whose sizes grow with the size $n$ of the networks.On the other hand, it is also known that leader election can be solved by adeterministic self-stabilizing algorithm using registers of $O(\log \log n)$bits per node in any $n$-node bounded-degree network. We show that this latterspace complexity is optimal. Specifically, we prove that every deterministicself-stabilizing algorithm solving leader election must use $\Omega(\log \logn)$-bit per node registers in some $n$-node networks. In addition, we show thatour lower bounds go beyond leader election, and apply to all problems thatcannot be solved by anonymous algorithms.

The following problem has been known since the 80's. Let $\Gamma$ be anAbelian group of order $m$ (denoted $|\Gamma|=m$), and let $t$ and $m_i$, $1\leq i \leq t$, be positive integers such that $\sum_{i=1}^t m_i=m-1$.Determine when $\Gamma^*=\Gamma\setminus\{0\}$, the set of non-zero elements of$\Gamma$, can be partitioned into disjoint subsets $S_i$, $1 \leq i \leq t$,such that $|S_i|=m_i$ and $\sum_{s\in S_i}s=0$ for every $i$, $1 \leq i \leqt$. It is easy to check that $m_i\geq 2$ (for every $i$, $1 \leq i \leq t$) and$|I(\Gamma)|\neq 1$ are necessary conditions for the existence of suchpartitions, where $I(\Gamma)$ is the set of involutions of $\Gamma$. It wasproved that the condition $m_i\geq 2$ is sufficient if and only if$|I(\Gamma)|\in\{0,3\}$. For other groups (i.e., for which $|I(\Gamma)|\neq 3$and $|I(\Gamma)|>1$), only the case of any group $\Gamma$ with$\Gamma\cong(Z_2)^n$ for some positive integer $n$ has been analyzed completelyso far, and it was shown independently by several authors that $m_i\geq 3$ issufficient in this case. Moreover, recently Cichacz and Tuza proved that, if$|\Gamma|$ is large enough and $|I(\Gamma)|>1$, then $m_i\geq 4$ is sufficient.In this paper we generalize this result for every Abelian group of order $2^n$.Namely, we show that the condition $m_i\geq 3$ is sufficient for $\Gamma$ suchthat $|I(\Gamma)|>1$ and $|\Gamma|=2^n$, for every positive integer $n$. Wealso present some applications of this result to graph magic- […]

We study the computational complexity of $c$-Colored $P_\ell$ Deletion and$c$-Colored $C_\ell$ Deletion. In these problems, one is given a$c$-edge-colored graph and wants to destroy all induced $c$-colored paths orcycles, respectively, on $\ell$ vertices by deleting at most $k$ edges. Herein,a path or cycle is $c$-colored if it contains edges of $c$ distinct colors. Weshow that $c$-Colored $P_\ell$ Deletion and $c$-Colored $C_\ell$ Deletion areNP-hard for each non-trivial combination of $c$ and $\ell$. We then analyze theparameterized complexity of these problems. We extend the notion ofneighborhood diversity to edge-colored graphs and show that both problems arefixed-parameter tractable with respect to the colored neighborhood diversity ofthe input graph. We also provide hardness results to outline the limits ofparameterization by the standard parameter solution size $k$. Finally, weconsider bicolored input graphs and show a special case of $2$-Colored $P_4$Deletion that can be solved in polynomial time.

Inspired by Lelek's idea from [Disjoint mappings and the span of spaces,Fund. Math. 55 (1964), 199 -- 214], we introduce the novel notion of the spanof graphs. Using this, we solve the problem of determining the \emph{maximalsafety distance} two players can keep at all times while traversing a graph.Moreover, their moves must be made with respect to certain move rules. For thispurpose, we introduce different variants of a span of a given connected graph.All the variants model the maximum safety distance kept by two players in agraph traversal, where the players may only move with accordance to a specificset of rules, and their goal: visit either all vertices, or all edges. For eachvariant, we show that the solution can be obtained by considering onlyconnected subgraphs of a graph product and the projections to the factors. Wecharacterise graphs in which it is impossible to keep a positive safetydistance at all moments in time. Finally, we present a polynomial timealgorithm that determines the chosen span variant of a given graph.

In this paper we first study $k \times n$ Youden rectangles of small orders.We have enumerated all Youden rectangles for a range of small parameter values,excluding the almost square cases where $k = n-1$, in a large scale computersearch. In particular, we verify the previous counts for $(n,k) = (7,3),(7,4)$, and extend this to the cases $(11,5), (11,6), (13,4)$ and $(21,5)$. Forsmall parameter values where no Youden rectangles exist, we also enumeraterectangles where the number of symbols common to two columns is always one oftwo possible values, differing by 1, which we call \emph{near Youdenrectangles}. For all the designs we generate, we calculate the order of theautotopism group and investigate to which degree a certain transformation canyield other row-column designs, namely double arrays, triple arrays and sesquiarrays. Finally, we also investigate certain Latin rectangles with threepossible pairwise intersection sizes for the columns and demonstrate that thesecan give rise to triple and sesqui arrays which cannot be obtained from Youdenrectangles, using the transformation mentioned above.

An s-branching flow f in a network N = (D, u), where u is the capacity function, is a flow thatreaches every vertex in V(D) from s while loosing exactly one unit of flow in each vertex other thans. Bang-Jensen and Bessy [TCS, 2014] showed that, when every arc has capacity n − 1, a network Nadmits k arc-disjoint s-branching flows if and only if its associated digraph D contains k arc-disjoints-branchings. Thus a classical result by Edmonds stating that a digraph contains k arc-disjoints-branchings if and only if the indegree of every set X ⊆ V (D) \ {s} is at least k also characterizesthe existence of k arc-disjoint s-branching flows in those networks, suggesting that the larger thecapacities are, the closer an s-branching flow is from simply being an s-branching. This observationis further implied by results by Bang-Jensen et al. [DAM, 2016] showing that there is a polynomialalgorithm to find the flows (if they exist) when every arc has capacity n − c, for every fixed c ≥ 1,and that such an algorithm is unlikely to exist for most other choices of the capacities. In this paper,we investigate how a property that is a natural extension of the characterization by Edmonds’ relatesto the existence of k arc-disjoint s-branching flows in networks. Although this property is alwaysnecessary for the existence of the flows, we show that it is not always sufficient and that it is hardto decide if the desired flows exist even if we know beforehand that the network satisfies it. […]

We obtain an explicit formula for the variance of the number of $k$-peaks ina uniformly random permutation. This is then used to obtain an asymptoticformula for the variance of the length of longest $k$-alternating subsequencein random permutations. Also a central limit is proved for the latterstatistic.

An edge-colored graph is \emph{rainbow }if no two edges of the graph have thesame color. An edge-colored graph $G^c$ is called \emph{properly colored} ifevery two adjacent edges of $G^c$ receive distinct colors in $G^c$. A\emph{strongly edge-colored} graph is a proper edge-colored graph such thatevery path of length $3$ is rainbow. We call an edge-colored graph $G^c$\emph{rainbow vertex pair-pancyclic} if any two vertices in $G^c$ are containedin a rainbow cycle of length $\ell$ for each $\ell$ with $3 \leq \ell \leq n$.In this paper, we show that every strongly edge-colored graph $G^c$ of order$n$ with minimum degree $\delta \geq \frac{2n}{3}+1$ is rainbow vertexpair-pancyclicity.

This paper considers the following three Roman domination graph invariants onKneser graphs: Roman domination, total Roman domination, and signed Roman domination. For Kneser graph $K_{n,k}$, we present exact values for Roman dominationnumber $\gamma_{R}(K_{n,k})$ and total Roman domination number$\gamma_{tR}(K_{n,k})$ proving that for $n\geqslant k(k+1)$,$\gamma_{R}(K_{n,k}) =\gamma_{tR}(K_{n,k}) = 2(k+1)$. For signed Romandomination number $\gamma_{sR}(K_{n,k})$, the new lower and upper bounds for$K_{n,2}$ are provided: we prove that for $n\geqslant 12$, the lower bound isequal to 2, while the upper bound depends on the parity of $n$ and is equal to3 if $n$ is odd, and equal to $5$ if $n$ is even. For graphs of smallerdimensions, exact values are found by applying exact methods from literature.

Recently geometric hypergraphs that can be defined by intersections ofpseudohalfplanes with a finite point set were defined in a purely combinatorialway. This led to extensions of earlier results about points and halfplanes topseudohalfplanes, including polychromatic colorings and discrete Helly-typetheorems about pseudohalfplanes. Here we continue this line of research and introduce the notion of convexsets of such pseudohalfplane hypergraphs. In this context we prove severalresults corresponding to classical results about convexity, namely Helly'sTheorem, Carathéodory's Theorem, Kirchberger's Theorem, Separation Theorem,Radon's Theorem and the Cup-Cap Theorem. These results imply the respectiveresults about pseudoconvex sets in the plane defined using pseudohalfplanes. It turns out that most of our results can be also proved using orientedmatroids and topological affine planes (TAPs) but our approach is differentfrom both of them. Compared to oriented matroids, our theory is based on alinear ordering of the vertex set which makes our definitions and proofs quitedifferent and perhaps more elementary. Compared to TAPs, which are continuousobjects, our proofs are purely combinatorial and again quite different inflavor. Altogether, we believe that our new approach can further ourunderstanding of these fundamental convexity results.

Gallai's path decomposition conjecture states that if $G$ is a connectedgraph on $n$ vertices, then the edges of $G$ can be decomposed into at most$\lceil \frac{n }{2} \rceil$ paths. A graph is said to be an odd semi-clique ifit can be obtained from a clique on $2k+1$ vertices by deleting at most $k-1$edges. Bonamy and Perrett asked if the edges of every connected graph $G$ on$n$ vertices can be decomposed into at most $\lfloor \frac{n}{2} \rfloor$ pathsunless $G$ is an odd semi-clique. A graph $G$ is said to be 2-degenerate ifevery subgraph of $G$ has a vertex of degree at most $2$. In this paper, weprove that the edges of any connected 2-degenerate graph $G$ on $n$ verticescan be decomposed into at most $\lfloor \frac{n }{2} \rfloor$ paths unless $G$is a triangle.

We discuss a notion of convergence for binary trees that is based on subtreesizes. In analogy to recent developments in the theory of graphs, posets andpermutations we investigate some general aspects of the topology, such as acharacterization of the set of possible limits and its structure as a metricspace. For random trees the subtree size topology arises in the context ofalgorithms for searching and sorting when applied to random input, resulting ina sequence of nested trees. For these we obtain a structural result based on alocal version of exchangeability. This in turn leads to a central limittheorem, with possibly mixed asymptotic normality.

Twin-width is a graph width parameter recently introduced by Bonnet, Kim,Thomassé & Watrigant. Given two graphs $G$ and $H$ and a graph product$\star$, we address the question: is the twin-width of $G\star H$ bounded by afunction of the twin-widths of $G$ and $H$ and their maximum degrees? It isknown that a bound of this type holds for strong products (Bonnet, Geniet, Kim,Thomassé & Watrigant; SODA 2021). We show that bounds of the same form holdfor Cartesian, tensor/direct, corona, rooted, replacement, and zig-zagproducts. For the lexicographical product it is known that the twin-width ofthe product of two graphs is exactly the maximum of the twin-widths of theindividual graphs (Bonnet, Kim, Reinald, Thomassé & Watrigant; IPEC 2021).In contrast, for the modular product we show that no bound can hold. Inaddition, we provide examples showing many of our bounds are tight, and giveimproved bounds for certain classes of graphs.