Discrete Mathematics & Theoretical Computer Science |

In Defective Coloring we are given a graph $G$ and two integers $\chi_d$,$\Delta^*$ and are asked if we can $\chi_d$-color $G$ so that the maximumdegree induced by any color class is at most $\Delta^*$. We show that thisnatural generalization of Coloring is much harder on several basic graphclasses. In particular, we show that it is NP-hard on split graphs, even whenone of the two parameters $\chi_d$, $\Delta^*$ is set to the smallest possiblefixed value that does not trivialize the problem ($\chi_d = 2$ or $\Delta^* =1$). Together with a simple treewidth-based DP algorithm this completelydetermines the complexity of the problem also on chordal graphs. We thenconsider the case of cographs and show that, somewhat surprisingly, DefectiveColoring turns out to be one of the few natural problems which are NP-hard onthis class. We complement this negative result by showing that DefectiveColoring is in P for cographs if either $\chi_d$ or $\Delta^*$ is fixed; thatit is in P for trivially perfect graphs; and that it admits a sub-exponentialtime algorithm for cographs when both $\chi_d$ and $\Delta^*$ are unbounded.

This paper studies three classes of cellular automata from a computational point of view: freezing cellular automata where the state of a cell can only decrease according to some order on states, cellular automata where each cell only makes a bounded number of state changes in any orbit, and finally cellular automata where each orbit converges to some fixed point. Many examples studied in the literature fit into these definitions, in particular the works on cristal growth started by S. Ulam in the 60s. The central question addressed here is how the computational power and computational hardness of basic properties is affected by the constraints of convergence, bounded number of change, or local decreasing of states in each cell. By studying various benchmark problems (short-term prediction, long term reachability, limits) and considering various complexity measures and scales (LOGSPACE vs. PTIME, communication complexity, Turing computability and arithmetical hierarchy) we give a rich and nuanced answer: the overall computational complexity of such cellular automata depends on the class considered (among the three above), the dimension, and the precise problem studied. In particular, we show that all settings can achieve universality in the sense of Blondel-Delvenne-K\r{u}rka, although short term predictability varies from NLOGSPACE to P-complete. Besides, the computability of limit configurations starting from computable initial configurations separates bounded-change from […]

Hamiltonian cycles in graphs were first studied in the 1850s. Since then, animpressive amount of research has been dedicated to identifying classes ofgraphs that allow Hamiltonian cycles, and to related questions. Thecorresponding decision problem, that asks whether a given graph is Hamiltonian(i.\,e.\ admits a Hamiltonian cycle), is one of Karp's famous NP-completeproblems. In this paper we study graphs of bounded degree that are \emph{far}from being Hamiltonian, where a graph $G$ on $n$ vertices is \emph{far} frombeing Hamiltonian, if modifying a constant fraction of $n$ edges is necessaryto make $G$ Hamiltonian. We give an explicit deterministic construction of aclass of graphs of bounded degree that are locally Hamiltonian, but (globally)far from being Hamiltonian. Here, \emph{locally Hamiltonian} means that everysubgraph induced by the neighbourhood of a small vertex set appears in someHamiltonian graph. More precisely, we obtain graphs which differ in $\Theta(n)$edges from any Hamiltonian graph, but non-Hamiltonicity cannot be detected inthe neighbourhood of $o(n)$ vertices. Our class of graphs yields a class ofhard instances for one-sided error property testers with linear querycomplexity. It is known that any property tester (even with two-sided error)requires a linear number of queries to test Hamiltonicity (Yoshida, Ito, 2010).This is proved via a randomised construction of hard instances. In contrast,our construction is deterministic. So far only very few […]

Let asc and desc denote respectively the statistics recording the number of ascents or descents in a sequence having non-negative integer entries. In a recent paper by Andrews and Chern, it was shown that the distribution of asc on the inversion sequence avoidance class $I_n(\geq,\neq,>)$ is the same as that of $n-1-\text{asc}$ on the class $I_n(>,\neq,\geq)$, which confirmed an earlier conjecture of Lin. In this paper, we consider some further enumerative aspects related to this equivalence and, as a consequence, provide an alternative proof of the conjecture. In particular, we find recurrence relations for the joint distribution on $I_n(\geq,\neq,>)$ of asc and desc along with two other parameters, and do the same for $n-1-\text{asc}$ and desc on $I_n(>,\neq,\geq)$. By employing a functional equation approach together with the kernel method, we are able to compute explicitly the generating function for both of the aforementioned joint distributions, which extends (and provides a new proof of) the recent result $|I_n(\geq,\neq,>)|=|I_n(>,\neq,\geq)|$. In both cases, an algorithm is formulated for computing the generating function of the asc distribution on members of each respective class having a fixed number of descents.

Let $G=(V(G),E(G))$ be a finite simple undirected graph with vertex set$V(G)$, edge set $E(G)$ and vertex subset $S\subseteq V(G)$. $S$ is termed\emph{open-dominating} if every vertex of $G$ has at least one neighbor in $S$,and \emph{open-independent, open-locating-dominating} (an $OLD_{oind}$-set forshort) if no two vertices in $G$ have the same set of neighbors in $S$, andeach vertex in $S$ is open-dominated exactly once by $S$. The problem ofdeciding whether or not $G$ has an $OLD_{oind}$-set has important applicationsthat have been reported elsewhere. As the problem is known to be$\mathcal{NP}$-complete, it appears to be notoriously difficult as we show thatits complexity remains the same even for just planar bipartite graphs ofmaximum degree five and girth six, and also for planar subcubic graphs of girthnine. Also, we present characterizations of both $P_4$-tidy graphs and thecomplementary prisms of cographs that have an $OLD_{oind}$-set.

A bramble in an undirected graph $G$ is a family of connected subgraphs of$G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either$V(H_1) \cap V(H_2) \neq \emptyset$ or there is an edge of $G$ with oneendpoint in $V(H_1)$ and the second endpoint in $V(H_2)$. The order of thebramble is the minimum size of a vertex set that intersects all elements of abramble. Brambles are objects dual to treewidth: As shown by Seymour and Thomas, themaximum order of a bramble in an undirected graph $G$ equals one plus thetreewidth of $G$. However, as shown by Grohe and Marx, brambles of high ordermay necessarily be of exponential size: In a constant-degree $n$-vertexexpander a bramble of order $\Omega(n^{1/2+\delta})$ requires size exponentialin $\Omega(n^{2\delta})$ for any fixed $\delta \in (0,\frac{1}{2}]$. On theother hand, the combination of results of Grohe and Marx and Chekuri andChuzhoy shows that a graph of treewidth $k$ admits a bramble of order$\widetilde{\Omega}(k^{1/2})$ and size $\widetilde{\mathcal{O}}(k^{3/2})$.($\widetilde{\Omega}$ and $\widetilde{\mathcal{O}}$ hide polylogarithmicfactors and divisors, respectively.) In this note, we first sharpen the second bound by proving that every graph$G$ of treewidth at least $k$ contains a bramble of order$\widetilde{\Omega}(k^{1/2})$ and congestion $2$, i.e., every vertex of $G$ iscontained in at most two elements of the bramble (thus the bramble is of sizelinear in its order). Second, we provide a tight upper […]

This note defines a notion of multiplicity for nodes in a rooted tree andpresents an asymptotic calculation of the maximum multiplicity over all leavesin a Bienaymé-Galton-Watson tree with critical offspring distribution $\xi$,conditioned on the tree being of size $n$. In particular, we show that if $S_n$is the maximum multiplicity in a conditional Bienaymé-Galton-Watson tree,then $S_n = \Omega(\log n)$ asymptotically in probability and under the furtherassumption that ${\bf E}\{2^\xi\} < \infty$, we have $S_n = O(\log n)$asymptotically in probability as well. Explicit formulas are given for theconstants in both bounds. We conclude by discussing links with an alternatedefinition of multiplicity that arises in the root-estimation problem.

Initiated by Davis, Nelson, Petersen and Tenner (2018), the enumerative studyof pinnacle sets of permutations has attracted a fair amount of attentionrecently. In this article, we provide a recurrence that can be used to computeefficiently the number $|\mathfrak{S}_n(P)|$ of permutations of size $n$ with agiven pinnacle set $P$, with arithmetic complexity $O(k^4 + k\log n)$ for $P$of size $k$. A symbolic expression can also be computed in this way forpinnacle sets of fixed size. A weighted sum $q_n(P)$ of $|\mathfrak{S}_n(P)|$proposed in Davis, Nelson, Petersen and Tenner (2018) seems to have a simpleform, and a conjectural form is given recently by Flaque, Novelli and Thibon(2021+). We settle the problem by providing and proving an alternative form of$q_n(P)$, which has a strong combinatorial flavor. We also study admissibleorderings of a given pinnacle set, first considered by Rusu (2020) andcharacterized by Rusu and Tenner (2021), and we give an efficient algorithm fortheir counting.

Let $k$ and $n$ be integers such that $1\leq k \leq n-1$, and let $G$ be asimple graph of order $n$. The $k$-token graph $F_k(G)$ of $G$ is the graphwhose vertices are the $k$-subsets of $V(G)$, where two vertices are adjacentin $F_k(G)$ whenever their symmetric difference is an edge of $G$. In thispaper we show that if $G$ is a tree, then the connectivity of $F_k(G)$ is equalto the minimum degree of $F_k(G)$.

The determining number of a graph $G = (V,E)$ is the minimum cardinality of aset $S\subseteq V$ such that pointwise stabilizer of $S$ under the action of$Aut(G)$ is trivial. In this paper, we provide some improved upper and lowerbounds on the determining number of Kneser graphs. Moreover, we provide theexact value of the determining number for some subfamilies of Kneser graphs.

Motivated by the study of pattern avoidance in the context of permutationsand ordered partitions, we consider the enumeration of weak-ordering chainsobtained as leaves of certain restricted rooted trees. A tree of order $n$ isgenerated by inserting a new variable into each node at every step. A nodebecomes a leaf either after $n$ steps or when a certain stopping condition ismet. In this paper we focus on conditions of size 2 ($x=y$, $x<y$, or $x\le y$)and several conditions of size 3. Some of the cases considered here lead to thestudy of descent statistics of certain `almost' pattern-avoiding permutations.

We consider the Erdős-Pósa property for immersions and topologicalminors in tournaments. We prove that for every simple digraph $H$, $k\in\mathbb{N}$, and tournament $T$, the following statements hold: (i) If in $T$ one cannot find $k$ arc-disjoint immersion copies of $H$, thenthere exists a set of $\mathcal{O}_H(k^3)$ arcs that intersects all immersioncopies of $H$ in $T$. (ii) If in $T$ one cannot find $k$ vertex-disjoint topological minor copiesof $H$, then there exists a set of $\mathcal{O}_H(k\log k)$ vertices thatintersects all topological minor copies of $H$ in $T$. This improves the results of Raymond [DMTCS '18], who proved similarstatements under the assumption that $H$ is strongly connected.

An equitable partition into branchings in a digraph is a partition of the arcset into branchings such that the sizes of any two branchings differ at most byone. For a digraph whose arc set can be partitioned into $k$ branchings, therealways exists an equitable partition into $k$ branchings. In this paper, wepresent two extensions of equitable partitions into branchings in digraphs:those into matching forests in mixed graphs; and into $b$-branchings indigraphs. For matching forests, Király and Yokoi (2022) considered atricriteria equitability based on the sizes of the matching forest, and thematching and branching therein. In contrast to this, we introduce asingle-criterion equitability based on the number of covered vertices, which isplausible in the light of the delta-matroid structure of matching forests.While the existence of this equitable partition can be derived from a lemma inKirály and Yokoi, we present its direct and simpler proof. For$b$-branchings, we define an equitability notion based on the size of the$b$-branching and the indegrees of all vertices, and prove that an equitablepartition always exists. We then derive the integer decomposition property ofthe associated polytopes.

In this paper, we study a variant of graph domination known as $(t, r)$broadcast domination, first defined in Blessing, Insko, Johnson, and Mauretourin 2015. In this variant, each broadcast provides $t-d$ reception to eachvertex a distance $d < t$ from the broadcast. If $d \ge t$ then no reception isprovided. A vertex is considered dominated if it receives $r$ total receptionfrom all broadcasts. Our main results provide some upper and lower bounds onthe density of a $(t, r)$ dominating pattern of an infinite grid, as well asmethods of computing them. Also, when $r \ge 2$ we describe a family ofcounterexamples to a generalization of Vizing's Conjecture to $(t,r)$ broadcastdomination.

Let $P$ be a set of $n\geq 3$ points in general position in the plane. Theedge disjointness graph $D(P)$ of $P$ is the graph whose vertices are all theclosed straight line segments with endpoints in $P$, two of which are adjacentin $D(P)$ if and only if they are disjoint. We show that the connectivity of$D(P)$ is at least$\binom{\lfloor\frac{n-2}{2}\rfloor}{2}+\binom{\lceil\frac{n-2}{2}\rceil}{2}$,and that this bound is tight for each $n\geq 3$.

Given a graph and an integer $k$, it is an NP-complete problem to decidewhether there is a dominating set of size at most $k$. In this paper we studythis problem for the Knödel Graph on $n$ vertices using elementary numbertheory techniques. In particular, we show an explicit upper bound for thedomination number of the Knödel Graph on $n$ vertices any time that we canfind a prime number $p$ dividing $n$ for which $2$ is a primitive root.

The number of down-steps between pairs of up-steps in $k_t$-Dyck paths, ageneralization of Dyck paths consisting of steps $\{(1, k), (1, -1)\}$ suchthat the path stays (weakly) above the line $y=-t$, is studied. Results areproved bijectively and by means of generating functions, and lead to severalinteresting identities as well as links to other combinatorial structures. Inparticular, there is a connection between $k_t$-Dyck paths and perforationpatterns for punctured convolutional codes (binary matrices) used in codingtheory. Surprisingly, upon restriction to usual Dyck paths this yields a newcombinatorial interpretation of Catalan numbers.

Layered treewidth and row treewidth are recently introduced graph parametersthat have been key ingredients in the solution of several well-known openproblems. It follows from the definitions that the layered treewidth of a graphis at most its row treewidth plus 1. Moreover, a minor-closed class has boundedlayered treewidth if and only if it has bounded row treewidth. However, it hasbeen open whether row treewidth is bounded by a function of layered treewidth.This paper answers this question in the negative. In particular, for everyinteger $k$ we describe a graph with layered treewidth 1 and row treewidth $k$.We also prove an analogous result for layered pathwidth and row pathwidth.

We study the neighborhood polynomial and the complexity of its computationfor chordal graphs. The neighborhood polynomial of a graph is the generatingfunction of subsets of its vertices that have a common neighbor. We introduce aparameter for chordal graphs called anchor width and an algorithm to computethe neighborhood polynomial which runs in polynomial time if the anchor widthis polynomially bounded. The anchor width is the maximal number of differentsub-cliques of a clique which appear as a common neighborhood. Furthermore westudy the anchor width for chordal graphs and some subclasses such as chordalcomparability graphs and chordal graphs with bounded leafage. the leafage of achordal graphs is the minimum number of leaves in the host tree of a subtreerepresentation. We show that the anchor width of a chordal graph is at most$n^{\ell}$ where $\ell$ denotes the leafage. This shows that for somesubclasses computing the neighborhood polynomial is possible in polynomial timewhile it is NP-hard for general chordal graphs.

We study Maker--Breaker total domination game played by two players,Dominator and Staller, on the connected cubic graphs. Staller (playing the roleof Maker) wins if she manages to claim an open neighbourhood of a vertex.Dominator wins otherwise (i.e.\ if he can claim a total dominating set of agraph). For certain graphs on $n\geq 6$ vertices, we give the characterizationon those which are Dominator's win and those which are Staller's win.

We consider a non-monotone activation process $(X_t)_{t\in\{ 0,1,2,\ldots\}}$on a graph $G$, where $X_0\subseteq V(G)$, $X_t=\{ u\in V(G):|N_G(u)\capX_{t-1}|\geq \tau(u)\}$ for every positive integer $t$, and $\tau:V(G)\to\mathbb{Z}$ is a threshold function. The set $X_0$ is a so-called non-monotonetarget set for $(G,\tau)$ if there is some $t_0$ such that $X_t=V(G)$ for every$t\geq t_0$. Ben-Zwi, Hermelin, Lokshtanov, and Newman [Discrete Optimization 8(2011) 87-96] asked whether a target set of minimum order can be determinedefficiently if $G$ is a tree. We answer their question in the affirmative forthreshold functions $\tau$ satisfying $\tau(u)\in \{ 0,1,d_G(u)\}$ for everyvertex~$u$. For such restricted threshold functions, we give a characterizationof target sets that allows to show that the minimum target set problem remainsNP-hard for planar graphs of maximum degree $3$ but is efficiently solvable forgraphs of bounded treewidth.

For a non-negative integer $s\le |V(G)|-3$, a graph $G$ is $s$-Hamiltonian ifthe removal of any $k\le s$ vertices results in a Hamiltonian graph. Given aconnected simple graph $G$ that is not isomorphic to a path, a cycle, or a$K_{1,3}$, let $\delta(G)$ denote the minimum degree of $G$, let $h_s(G)$denote the smallest integer $i$ such that the iterated line graph $L^{i}(G)$ is$s$-Hamiltonian, and let $\ell(G)$ denote the length of the longest non-closedpath $P$ in which all internal vertices have degree 2 such that $P$ is not bothof length 2 and in a $K_3$. For a simple graph $G$, we establish better upperbounds for $h_s(G)$ as follows. \begin{equation*} h_s(G)\le \left\{\begin{aligned} & \ell(G)+1, &&\mbox{ if }\delta(G)\le 2 \mbox{ and }s=0;\\ &\widetilde d(G)+2+\lceil \lg (s+1)\rceil, &&\mbox{ if }\delta(G)\le 2 \mbox{and }s\ge 1;\\ & 2+\left\lceil\lg\frac{s+1}{\delta(G)-2}\right\rceil, && \mbox{if } 3\le\delta(G)\le s+2;\\ & 2, &&{\rm otherwise}, \end{aligned} \right.\end{equation*} where $\widetilde d(G)$ is the smallest integer $i$ such that$\delta(L^i(G))\ge 3$. Consequently, when $s \ge 6$, this new upper bound forthe $s$-hamiltonian index implies that $h_s(G) = o(\ell(G)+s+1)$ as $s \to\infty$. This sharpens the result, $h_s(G)\le\ell(G)+s+1$, obtained by Zhang etal. in [Discrete Math., 308 (2008) 4779-4785].

We define and study positional marked patterns, permutations $\tau$ where oneof elements in $\tau$ is underlined. Given a permutation $\sigma$, we say that$\sigma$ has a $\tau$-match at position $i$ if $\tau$ occurs in $\sigma$ insuch a way that $\sigma_i$ plays the role of the underlined element in theoccurrence. We let $pmp_\tau(\sigma)$ denote the number of positions $i$ which$\sigma$ has a $\tau$-match. This defines a new class of statistics onpermutations, where we study such statistics and prove a number of results. Inparticular, we prove that two positional marked patterns $1\underline{2}3$ and$1\underline{3}2$ give rise to two statistics that have the same distribution.The equidistibution phenomenon also occurs in other several collections ofpatterns like $\left \{1\underline{2}3 , 1\underline{3}2 \right \}$, and $\left\{ 1\underline234, 1\underline243, \underline2134, \underline2 1 4 3 \right\}$, as well as two positional marked patterns of any length $n$: $\left \{1\underline 2\tau , \underline 21\tau \right \}$.

Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjointtriangles, it suffices to delete at most 2k edges to obtain a triangle-freegraph. The conjecture holds for graphs with small treewidth or small maximumaverage degree, including planar graphs. However, for dense graphs that areneither cliques nor 4-colorable, only asymptotic results are known. Here, weconfirm the conjecture for threshold graphs, i.e. graphs that are both splitgraphs and cographs, and for co-chain graphs with both sides of the same sizedivisible by 4.

The $n$th term of an automatic sequence is the output of a deterministicfinite automaton fed with the representation of $n$ in a suitable numerationsystem. In this paper, instead of considering automatic sequences built on anumeration system with a regular numeration language, we consider those builton languages associated with trees having periodic labeled signatures and, inparticular, rational base numeration systems. We obtain two maincharacterizations of these sequences. The first one is concerned with $r$-blocksubstitutions where $r$ morphisms are applied periodically. In particular, weprovide examples of such sequences that are not morphic. The secondcharacterization involves the factors, or subtrees of finite height, of thetree associated with the numeration system and decorated by the terms of thesequence.