Discrete Mathematics & Theoretical Computer Science |

We provide a pair of ribbon graphs that have the same rotor routing andBernardi sandpile torsors, but different topological genus. This resolves aquestion posed by M. Chan [Cha]. We also show that if we are given a graph, butnot its ribbon structure, along with the rotor routing sandpile torsors, we areable to determine the ribbon graph's genus.

Recently, Yamazaki et al. provided an algorithm that enumerates allnon-isomorphic interval graphs on $n$ vertices with an $O(n^4)$ time delay. Inthis paper, we improve their algorithm and achieve $O(n^3 \log n)$ time delay.We also extend the catalog of these graphs providing a list of allnon-isomorphic interval graphs for all $n$ up to $15$.

Let $G$ be a a connected graph. The Wiener index of a connected graph is thesum of the distances between all unordered pairs of vertices. We provideasymptotic formulae for the maximum Wiener index of simple triangulations andquadrangulations with given connectivity, as the order increases, and makeconjectures for the extremal triangulations and quadrangulations based oncomputational evidence. If $\overline{\sigma}(v)$ denotes the arithmetic meanof the distances from $v$ to all other vertices of $G$, then the remoteness of$G$ is defined as the largest value of $\overline{\sigma}(v)$ over all vertices$v$ of $G$. We give sharp upper bounds on the remoteness of simpletriangulations and quadrangulations of given order and connectivity.

In a recent work, Bensmail, Blanc, Cohen, Havet and Rocha, motivated by applications for TDMA scheduling problems, have introduced the notion of BMRN*-colouring of digraphs, which is a type of arc-colouring with particular colouring constraints. In particular, they gave a special focus to planar digraphs. They notably proved that every planar digraph can be 8-BMRN*-coloured, while there exist planar digraphs for which 7 colours are needed in a BMRN*-colouring. They also proved that the problem of deciding whether a planar digraph can be 3-BMRN*-coloured is NP-hard. In this work, we pursue these investigations on planar digraphs, in particular by answering some of the questions left open by the authors in that seminal work. We exhibit planar digraphs needing 8 colours to be BMRN*-coloured, thus showing that the upper bound of Bensmail, Blanc, Cohen, Havet and Rocha cannot be decreased in general. We also generalize their complexity result by showing that the problem of deciding whether a planar digraph can be k-BMRN*-coloured is NP-hard for every k ∈ {3,...,6}. Finally, we investigate the connection between the girth of a planar digraphs and the least number of colours in its BMRN*-colourings.

Recently, Fici, Restivo, Silva, and Zamboni introduced the notion of a$k$-anti-power, which is defined as a word of the form $w^{(1)} w^{(2)} \cdotsw^{(k)}$, where $w^{(1)}, w^{(2)}, \ldots, w^{(k)}$ are distinct words of thesame length. For an infinite word $w$ and a positive integer $k$, define$AP_j(w,k)$ to be the set of all integers $m$ such that $w_{j+1} w_{j+2} \cdotsw_{j+km}$ is a $k$-anti-power, where $w_i$ denotes the $i$-th letter of $w$.Define also $\mathcal{F}_j(k) = (2 \mathbb{Z}^+ - 1) \cap AP_j(\mathbf{t},k)$,where $\mathbf{t}$ denotes the Thue-Morse word. For all $k \in \mathbb{Z}^+$,$\gamma_j(k) = \min (AP_j(\mathbf{t},k))$ is a well-defined positive integer,and for $k \in \mathbb{Z}^+$ sufficiently large, $\Gamma_j(k) = \sup ((2\mathbb{Z}^+ -1) \setminus \mathcal{F}_j(k))$ is a well-defined odd positiveinteger. In his 2018 paper, Defant shows that $\gamma_0(k)$ and $\Gamma_0(k)$grow linearly in $k$. We generalize Defant's methods to prove that$\gamma_j(k)$ and $\Gamma_j(k)$ grow linearly in $k$ for any nonnegativeinteger $j$. In particular, we show that $\displaystyle 1/10 \leq \liminf_{k\rightarrow \infty} (\gamma_j(k)/k) \leq 9/10$ and $\displaystyle 1/5 \leq\limsup_{k \rightarrow \infty} (\gamma_j(k)/k) \leq 3/2$. Additionally, we showthat $\displaystyle \liminf_{k \rightarrow \infty} (\Gamma_j(k)/k) = 3/2$ and$\displaystyle \limsup_{k \rightarrow \infty} (\Gamma_j(k)/k) = 3$.

We consider non-trivial homomorphisms to reflexive oriented graphs in whichsome pair of adjacent vertices have the same image. Using a notion of convexityfor oriented graphs, we study those oriented graphs that do not admit suchhomomorphisms. We fully classify those oriented graphs with tree-width $2$ thatdo not admit such homomorphisms and show that it is NP-complete to decide if agraph admits an orientation that does not admit such homomorphisms. We proveanalogous results for $2$-edge-coloured graphs. We apply our results onoriented graphs to provide a new tool in the study of chromatic number oforientations of planar graphs -- a long-standing open problem.

The forbidden number $\mathrm{forb}(m,F)$, which denotes the maximum numberof unique columns in an $m$-rowed $(0,1)$-matrix with no submatrix that is arow and column permutation of $F$, has been widely studied in extremal settheory. Recently, this function was extended to $r$-matrices, whose entries liein $\{0,1,\dots,r-1\}$. The combinatorics of the generalized forbidden numberis less well-studied. In this paper, we provide exact bounds for many$(0,1)$-matrices $F$, including all $2$-rowed matrices when $r > 3$. We alsoprove a stability result for the $2\times 2$ identity matrix. Along the way, weexpose some interesting qualitative differences between the cases $r=2$, $r =3$, and $r > 3$.

A subset $A \subset \mathbb R^2$ is said to avoid distance $1$ if: $\forallx,y \in A, \left\| x-y \right\|_2 \neq 1.$ In this paper we study the number$m_1(\mathbb R^2)$ which is the supremum of the upper densities of measurablesets avoiding distance 1 in the Euclidean plane. Intuitively, $m_1(\mathbbR^2)$ represents the highest proportion of the plane that can be filled by aset avoiding distance 1. This parameter is related to the fractional chromaticnumber $\chi_f(\mathbb R^2)$ of the plane. We establish that $m_1(\mathbb R^2) \leq 0.25647$ and $\chi_f(\mathbb R^2)\geq 3.8991$.

Let $\lambda$ be a partition with no more than $n$ parts. Let $\beta$ be aweakly increasing $n$-tuple with entries from $\{ 1, ... , n \}$. The flaggedSchur function in the variables $x_1, ... , x_n$ that is indexed by $\lambda$and $\beta$ has been defined to be the sum of the content weight monomials forthe semistandard Young tableaux of shape $\lambda$ whose values are row-wisebounded by the entries of $\beta$. Gessel and Viennot gave a determinantexpression for the flagged Schur function indexed by $\lambda$ and $\beta$;this could be done since the pair $(\lambda, \beta)$ satisfied their"nonpermutable" condition for the sequence of terminals of an $n$-tuple oflattice paths that they used to model the tableaux. We generalize flagged Schurfunctions by dropping the requirement that $\beta$ be weakly increasing. Thenfor each $\lambda$ we give a condition on the entries of $\beta$ for the pair$(\lambda, \beta)$ to be nonpermutable that is both necessary and sufficient.When the parts of $\lambda$ are not distinct there will be multiple row bound$n$-tuples $\beta$ that will produce the same set of tableaux. We accordinglygroup the bounding $\beta$ into equivalence classes and identify the mostefficient $\beta$ in each class for the determinant computation. We recentlyshowed that many other sets of objects that are indexed by $n$ and $\lambda$are enumerated by the number of these efficient $n$-tuples. We called thesecounts "parabolic Catalan numbers". It is […]

A mixed dominating set is a collection of vertices and edges that dominatesall vertices and edges of a graph. We study the complexity of exact andparameterized algorithms for \textsc{Mixed Dominating Set}, resolving some openquestions. In particular, we settle the problem's complexity parameterized bytreewidth and pathwidth by giving an algorithm running in time $O^*(5^{tw})$(improving the current best $O^*(6^{tw})$), as well as a lower bound showingthat our algorithm cannot be improved under the Strong Exponential TimeHypothesis (SETH), even if parameterized by pathwidth (improving a lower boundof $O^*((2 - \varepsilon)^{pw})$). Furthermore, by using a simple but so faroverlooked observation on the structure of minimal solutions, we obtainbranching algorithms which improve both the best known FPT algorithm for thisproblem, from $O^*(4.172^k)$ to $O^*(3.510^k)$, and the best knownexponential-time exact algorithm, from $O^*(2^n)$ and exponential space, to$O^*(1.912^n)$ and polynomial space.

Let $G$ be a connected graph of order $n$.The Wiener index $W(G)$ of $G$ isthe sum of the distances between all unordered pairs of vertices of $G$. Inthis paper we show that the well-known upper bound $\big(\frac{n}{\delta+1}+2\big) {n \choose 2}$ on the Wiener index of a graph oforder $n$ and minimum degree $\delta$ [M. Kouider, P. Winkler, Mean distanceand minimum degree. J. Graph Theory 25 no. 1 (1997)] can be improvedsignificantly if the graph contains also a vertex of large degree.Specifically, we give the asymptotically sharp bound $W(G) \leq{n-\Delta+\delta \choose 2} \frac{n+2\Delta}{\delta+1}+ 2n(n-1)$ on the Wienerindex of a graph $G$ of order $n$, minimum degree $\delta$ and maximum degree$\Delta$. We prove a similar result for triangle-free graphs, and we determinea bound on the Wiener index of $C_4$-free graphs of given order, minimum andmaximum degree and show that it is, in some sense, best possible.

This paper introduces a notion of equivalence for higher-dimensionalautomata, called weak equivalence. Weak equivalence focuses mainly on atraditional trace language and a new homology language, which captures theoverall independence structure of an HDA. It is shown that weak equivalence iscompatible with both the tensor product and the coproduct of HDAs and that,under certain conditions, HDAs may be reduced to weakly equivalent smaller onesby merging and collapsing cubes.

Binary relations derived from labeled rooted trees play an import role inmathematical biology as formal models of evolutionary relationships. The(symmetrized) Fitch relation formalizes xenology as the pairs of genesseparated by at least one horizontal transfer event. As a naturalgeneralization, we consider symmetrized Fitch maps, that is, symmetric maps$\varepsilon$ that assign a subset of colors to each pair of vertices in $X$and that can be explained by a tree $T$ with edges that are labeled withsubsets of colors in the sense that the color $m$ appears in $\varepsilon(x,y)$if and only if $m$ appears in a label along the unique path between $x$ and $y$in $T$. We first give an alternative characterization of the monochromatic caseand then give a characterization of symmetrized Fitch maps in terms ofcompatibility of a certain set of quartets. We show that recognition ofsymmetrized Fitch maps is NP-complete. In the restricted case where$|\varepsilon(x,y)|\leq 1$ the problem becomes polynomial, since such mapscoincide with class of monochromatic Fitch maps whose graph-representationsform precisely the class of complete multi-partite graphs.

We introduce and study the Bicolored $P_3$ Deletion problem defined asfollows. The input is a graph $G=(V,E)$ where the edge set $E$ is partitionedinto a set $E_r$ of red edges and a set $E_b$ of blue edges. The question iswhether we can delete at most $k$ edges such that $G$ does not contain abicolored $P_3$ as an induced subgraph. Here, a bicolored $P_3$ is a path onthree vertices with one blue and one red edge. We show that Bicolored $P_3$Deletion is NP-hard and cannot be solved in $2^{o(|V|+|E|)}$ time onbounded-degree graphs if the ETH is true. Then, we show that Bicolored $P_3$Deletion is polynomial-time solvable when $G$ does not contain a bicolored$K_3$, that is, a triangle with edges of both colors. Moreover, we provide apolynomial-time algorithm for the case that $G$ contains no blue $P_3$, red$P_3$, blue $K_3$, and red $K_3$. Finally, we show that Bicolored $P_3$Deletion can be solved in $ O(1.84^k\cdot |V| \cdot |E|)$ time and that itadmits a kernel with $ O(k\Delta\min(k,\Delta))$ vertices, where $\Delta$ isthe maximum degree of $G$.

Fix a finite undirected graph $\Gamma$ and a vertex $v$ of $\Gamma$. Let $E$be the set of edges of $\Gamma$. We call a subset $F$ of $E$ pandemic if eachedge of $\Gamma$ has at least one endpoint that can be connected to $v$ by an$F$-path (i.e., a path using edges from $F$ only). In 1984, Elser showed thatthe sum of $\left(-1\right)^{\left| F\right|}$ over all pandemic subsets $F$ of$E$ is $0$ if $E\neq \varnothing$. We give a simple proof of this result via asign-reversing involution, and discuss variants, generalizations andrefinements, revealing connections to abstract convexity (the notion of anantimatroid) and discrete Morse theory.

Edmonds, Lovász, and Pulleyblank showed that if a matching covered graphhas a nontrivial tight cut, then it also has a nontrivial ELP-cut. Carvalho etal. gave a stronger conjecture: if a matching covered graph has a nontrivialtight cut $C$, then it also has a nontrivial ELP-cut that does not cross $C$.Chen, et al gave a proof of the conjecture. This note is inspired by the paperof Carvalho et al. We give a simplified proof of the conjecture, and prove thefollowing result which is slightly stronger than the conjecture: if anontrivial tight cut $C$ of a matching covered graph $G$ is not an ELP-cut,then there is a sequence $G_1=G, G_2,\ldots,G_r, r\geq2$ of matching coveredgraphs, such that for $i=1, 2,\ldots, r-1$, $G_i$ has an ELP-cut $C_i$, and$G_{i+1}$ is a $C_i$-contraction of $G_i$, and $C$ is a $2$-separation cut of$G_r$.

The dynamics of certain combinatorial actions and their liftings to actionsat the piecewise-linear and birational level have been studied lately with aneye towards questions of periodicity, orbit structure, and invariants. One keyproperty enjoyed by the rowmotion operator on certain finite partially-orderedsets is homomesy, where the average value of a statistic is the same for allorbits. To prove refined versions of homomesy in the product of two chainposets, J. Propp and the second author used an equivariant bijection discovered(less formally) by R. Stanley and H. Thomas. We explore the lifting of this "Stanley--Thomas word" to thepiecewise-linear, birational, and noncommutative realms. Although the map is nolonger a bijection, so cannot be used to prove periodicity directly, it stillgives enough information to prove the homomesy at the piecewise-linear andbirational levels (a result previously shown by D. Grinberg, S. Hopkins, and S.Okada). Even at the noncommutative level, the Stanley--Thomas word of a posetlabeling rotates cyclically with the lifting of antichain rowmotion. Along theway we give some formulas for noncommutative antichain rowmotion that we hopewill be first steps towards proving the conjectured periodicity at this level.

We consider weighted tree automata (wta) over strong bimonoids and theirinitial algebra semantics and their run semantics. There are wta for whichthese semantics are different; however, for bottom-up deterministic wta and forwta over semirings, the difference vanishes. A wta is crisp-deterministic if itis bottom-up deterministic and each transition is weighted by one of the unitelements of the strong bimonoid. We prove that the class of weighted treelanguages recognized by crisp-deterministic wta is the same as the class ofrecognizable step mappings. Moreover, we investigate the following twocrisp-determinization problems: for a given wta ${\cal A}$, (a) does thereexist a crisp-deterministic wta which computes the initial algebra semantics of${\cal A}$ and (b) does there exist a crisp-deterministic wta which computesthe run semantics of ${\cal A}$? We show that the finiteness of the Nerodealgebra ${\cal N}({\cal A})$ of ${\cal A}$ implies a positive answer for (a),and that the finite order property of ${\cal A}$ implies a positive answer for(b). We show a sufficient condition which guarantees the finiteness of ${\calN}({\cal A})$ and a sufficient condition which guarantees the finite orderproperty of ${\cal A}$. Also, we provide an algorithm for the construction ofthe crisp-deterministic wta according to (a) if ${\cal N}({\cal A})$ is finite,and similarly for (b) if ${\cal A}$ has finite order property. We prove that itis undecidable whether an arbitrary wta ${\cal A}$ is […]

A dominating set $D$ of a graph $G$ without isolated vertices is calledsemipaired dominating set if $D$ can be partitioned into $2$-element subsetssuch that the vertices in each set are at distance at most $2$. The semipaireddomination number, denoted by $\gamma_{pr2}(G)$ is the minimum cardinality of asemipaired dominating set of $G$. Given a graph $G$ with no isolated vertices,the \textsc{Minimum Semipaired Domination} problem is to find a semipaireddominating set of $G$ of cardinality $\gamma_{pr2}(G)$. The decision version ofthe \textsc{Minimum Semipaired Domination} problem is already known to beNP-complete for chordal graphs, an important graph class. In this paper, weshow that the decision version of the \textsc{Minimum Semipaired Domination}problem remains NP-complete for split graphs, a subclass of chordal graphs. Onthe positive side, we propose a linear-time algorithm to compute a minimumcardinality semipaired dominating set of block graphs. In addition, we provethat the \textsc{Minimum Semipaired Domination} problem is APX-complete forgraphs with maximum degree $3$.