Alex McDonough.
We provide a pair of ribbon graphs that have the same rotor routing and
Bernardi sandpile torsors, but different topological genus. This resolves a
question posed by M. Chan [Cha]. We also show that if we are given a graph, but
not its ribbon structure, along with the rotor routing sandpile torsors, we are
able to determine the ribbon graph's genus.
Section:
Combinatorics
Patryk Mikos.
Recently, Yamazaki et al. provided an algorithm that enumerates all
non-isomorphic interval graphs on $n$ vertices with an $O(n^4)$ time delay. In
this 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 all
non-isomorphic interval graphs for all $n$ up to $15$.
Section:
Graph Theory
Éva Czabarka ; Peter Dankelmann ; Trevor Olsen ; László A. Székely.
Let $G$ be a a connected graph. The Wiener index of a connected graph is the
sum of the distances between all unordered pairs of vertices. We provide
asymptotic formulae for the maximum Wiener index of simple triangulations and
quadrangulations with given connectivity, as the order increases, and make
conjectures for the extremal triangulations and quadrangulations based on
computational evidence. If $\overline{\sigma}(v)$ denotes the arithmetic mean
of 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 simple
triangulations and quadrangulations of given order and connectivity.
Section:
Graph Theory
Julien Bensmail ; Foivos Fioravantes.
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.
Section:
Graph Theory
Marisa Gaetz.
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)} \cdots
w^{(k)}$, where $w^{(1)}, w^{(2)}, \ldots, w^{(k)}$ are distinct words of the
same 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} \cdots
w_{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 positive
integer. 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 nonnegative
integer $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 show
that $\displaystyle \liminf_{k \rightarrow \infty} (\Gamma_j(k)/k) = 3/2$ and
$\displaystyle \limsup_{k \rightarrow \infty} (\Gamma_j(k)/k) = 3$.
Section:
Analysis of Algorithms
Christopher Duffy ; Sonja Linghui Shan.
We consider non-trivial homomorphisms to reflexive oriented graphs in which
some pair of adjacent vertices have the same image. Using a notion of convexity
for oriented graphs, we study those oriented graphs that do not admit such
homomorphisms. We fully classify those oriented graphs with tree-width $2$ that
do not admit such homomorphisms and show that it is NP-complete to decide if a
graph admits an orientation that does not admit such homomorphisms. We prove
analogous results for $2$-edge-coloured graphs. We apply our results on
oriented graphs to provide a new tool in the study of chromatic number of
orientations of planar graphs -- a long-standing open problem.
Section:
Graph Theory
Travis Dillon ; Attila Sali.
The forbidden number $\mathrm{forb}(m,F)$, which denotes the maximum number
of unique columns in an $m$-rowed $(0,1)$-matrix with no submatrix that is a
row and column permutation of $F$, has been widely studied in extremal set
theory. Recently, this function was extended to $r$-matrices, whose entries lie
in $\{0,1,\dots,r-1\}$. The combinatorics of the generalized forbidden number
is 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 also
prove a stability result for the $2\times 2$ identity matrix. Along the way, we
expose some interesting qualitative differences between the cases $r=2$, $r =
3$, and $r > 3$.
Section:
Combinatorics
Robert A. Proctor ; Matthew J. Willis.
Let $\lambda$ be a partition with no more than $n$ parts. Let $\beta$ be a
weakly increasing $n$-tuple with entries from $\{ 1, ... , n \}$. The flagged
Schur 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 for
the semistandard Young tableaux of shape $\lambda$ whose values are row-wise
bounded by the entries of $\beta$. Gessel and Viennot gave a determinant
expression 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 of
lattice paths that they used to model the tableaux. We generalize flagged Schur
functions by dropping the requirement that $\beta$ be weakly increasing. Then
for 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 accordingly
group the bounding $\beta$ into equivalence classes and identify the most
efficient $\beta$ in each class for the determinant computation. We recently
showed 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 these
counts "parabolic Catalan […]
Section:
Combinatorics
Louis Dublois ; Michael Lampis ; Vangelis Th. Paschos.
A mixed dominating set is a collection of vertices and edges that dominates
all vertices and edges of a graph. We study the complexity of exact and
parameterized algorithms for \textsc{Mixed Dominating Set}, resolving some open
questions. In particular, we settle the problem's complexity parameterized by
treewidth 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 showing
that our algorithm cannot be improved under the Strong Exponential Time
Hypothesis (SETH), even if parameterized by pathwidth (improving a lower bound
of $O^*((2 - \varepsilon)^{pw})$). Furthermore, by using a simple but so far
overlooked observation on the structure of minimal solutions, we obtain
branching algorithms which improve both the best known FPT algorithm for this
problem, from $O^*(4.172^k)$ to $O^*(3.510^k)$, and the best known
exponential-time exact algorithm, from $O^*(2^n)$ and exponential space, to
$O^*(1.912^n)$ and polynomial space.
Section:
Discrete Algorithms
Peter Dankelmann ; Alex Alochukwu.
Let $G$ be a connected graph of order $n$.The Wiener index $W(G)$ of $G$ is
the sum of the distances between all unordered pairs of vertices of $G$. In
this 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 of
order $n$ and minimum degree $\delta$ [M. Kouider, P. Winkler, Mean distance
and minimum degree. J. Graph Theory 25 no. 1 (1997)] can be improved
significantly 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 Wiener
index 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 determine
a bound on the Wiener index of $C_4$-free graphs of given order, minimum and
maximum degree and show that it is, in some sense, best possible.
Section:
Graph Theory
Thomas Kahl.
This paper introduces a notion of equivalence for higher-dimensional
automata, called weak equivalence. Weak equivalence focuses mainly on a
traditional trace language and a new homology language, which captures the
overall independence structure of an HDA. It is shown that weak equivalence is
compatible with both the tensor product and the coproduct of HDAs and that,
under certain conditions, HDAs may be reduced to weakly equivalent smaller ones
by merging and collapsing cubes.
Section:
Automata, Logic and Semantics
Marc Hellmuth ; Carsten R. Seemann ; Peter F. Stadler.
Binary relations derived from labeled rooted trees play an import role in
mathematical biology as formal models of evolutionary relationships. The
(symmetrized) Fitch relation formalizes xenology as the pairs of genes
separated by at least one horizontal transfer event. As a natural
generalization, 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 with
subsets 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 case
and then give a characterization of symmetrized Fitch maps in terms of
compatibility of a certain set of quartets. We show that recognition of
symmetrized Fitch maps is NP-complete. In the restricted case where
$|\varepsilon(x,y)|\leq 1$ the problem becomes polynomial, since such maps
coincide with class of monochromatic Fitch maps whose graph-representations
form precisely the class of complete multi-partite graphs.
Section:
Graph Theory
Niels Grüttemeier ; Christian Komusiewicz ; Jannik Schestag ; Frank Sommer.
We introduce and study the Bicolored $P_3$ Deletion problem defined as
follows. The input is a graph $G=(V,E)$ where the edge set $E$ is partitioned
into a set $E_r$ of red edges and a set $E_b$ of blue edges. The question is
whether we can delete at most $k$ edges such that $G$ does not contain a
bicolored $P_3$ as an induced subgraph. Here, a bicolored $P_3$ is a path on
three 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 on
bounded-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 a
polynomial-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 it
admits a kernel with $ O(k\Delta\min(k,\Delta))$ vertices, where $\Delta$ is
the maximum degree of $G$.
Section:
Graph Theory
Darij Grinberg.
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 each
edge 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 that
the 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 a
sign-reversing involution, and discuss variants, generalizations and
refinements, revealing connections to abstract convexity (the notion of an
antimatroid) and discrete Morse theory.
Section:
Combinatorics
Xiao Zhao ; Sheng Chen.
Edmonds, Lovász, and Pulleyblank showed that if a matching covered graph
has a nontrivial tight cut, then it also has a nontrivial ELP-cut. Carvalho et
al. gave a stronger conjecture: if a matching covered graph has a nontrivial
tight 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 paper
of Carvalho et al. We give a simplified proof of the conjecture, and prove the
following result which is slightly stronger than the conjecture: if a
nontrivial 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 covered
graphs, 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$.
Section:
Graph Theory
Zoltán Fülöp ; Dávid Kószó ; Heiko Vogler.
We consider weighted tree automata (wta) over strong bimonoids and their
initial algebra semantics and their run semantics. There are wta for which
these semantics are different; however, for bottom-up deterministic wta and for
wta over semirings, the difference vanishes. A wta is crisp-deterministic if it
is bottom-up deterministic and each transition is weighted by one of the unit
elements of the strong bimonoid. We prove that the class of weighted tree
languages recognized by crisp-deterministic wta is the same as the class of
recognizable step mappings. Moreover, we investigate the following two
crisp-determinization problems: for a given wta ${\cal A}$, (a) does there
exist a crisp-deterministic wta which computes the initial algebra semantics of
${\cal A}$ and (b) does there exist a crisp-deterministic wta which computes
the run semantics of ${\cal A}$? We show that the finiteness of the Nerode
algebra ${\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 ${\cal
N}({\cal A})$ and a sufficient condition which guarantees the finite order
property of ${\cal A}$. Also, we provide an algorithm for the construction of
the 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 it
is undecidable whether an arbitrary […]
Section:
Automata, Logic and Semantics
Michael A. Henning ; Arti Pandey ; Vikash Tripathi.
A dominating set $D$ of a graph $G$ without isolated vertices is called
semipaired dominating set if $D$ can be partitioned into $2$-element subsets
such that the vertices in each set are at distance at most $2$. The semipaired
domination number, denoted by $\gamma_{pr2}(G)$ is the minimum cardinality of a
semipaired dominating set of $G$. Given a graph $G$ with no isolated vertices,
the \textsc{Minimum Semipaired Domination} problem is to find a semipaired
dominating set of $G$ of cardinality $\gamma_{pr2}(G)$. The decision version of
the \textsc{Minimum Semipaired Domination} problem is already known to be
NP-complete for chordal graphs, an important graph class. In this paper, we
show that the decision version of the \textsc{Minimum Semipaired Domination}
problem remains NP-complete for split graphs, a subclass of chordal graphs. On
the positive side, we propose a linear-time algorithm to compute a minimum
cardinality semipaired dominating set of block graphs. In addition, we prove
that the \textsc{Minimum Semipaired Domination} problem is APX-complete for
graphs with maximum degree $3$.
Section:
Discrete Algorithms