Jérémy Omer ; Tangi Migot.
In this paper, we study the complexity of the selection of a graph discretization order with a stepwise linear cost function. Finding such vertex ordering has been proved to be an essential step to solve discretizable distance geometry problems (DDGPs). DDGPs constitute a class of graph realization problems where the vertices can be ordered in such a way that the search space of possible positions becomes discrete, usually represented by a binary tree. In particular, it is useful to find discretization orders that minimize an indicator of the size of the search tree. Our stepwise linear cost function generalizes this situation and allows to discriminate the vertices into three categories depending on the number of adjacent predecessors of each vertex in the order and on two parameters K and U. We provide a complete study of NP-completeness for fixed values of K and U. Our main result is that the problem is NP-complete in general for all values of K and U such that U ≥ K + 1 and U ≥ 2. A consequence of this result is that the minimization of vertices with exactly K adjacent predecessors in a discretization order is also NP-complete.
Section:
Discrete Algorithms
Julien Bensmail ; François Dross ; Hervé Hocquard ; Eric Sopena.
A strong edge-colouring of an undirected graph $G$ is an edge-colouring where every two edges at distance at most~$2$ receive distinct colours. The strong chromatic index of $G$ is the least number of colours in a strong edge-colouring of $G$. A conjecture of Erdős and Nešet\v{r}il, stated back in the $80$'s, asserts that every graph with maximum degree $\Delta$ should have strong chromatic index at most roughly $1.25 \Delta^2$. Several works in the last decades have confirmed this conjecture for various graph classes. In particular, lots of attention have been dedicated to planar graphs, for which the strong chromatic index decreases to roughly $4\Delta$, and even to smaller values under additional structural requirements.In this work, we initiate the study of the strong chromatic index of $1$-planar graphs, which are those graphs that can be drawn on the plane in such a way that every edge is crossed at most once. We provide constructions of $1$-planar graphs with maximum degree~$\Delta$ and strong chromatic index roughly $6\Delta$. As an upper bound, we prove that the strong chromatic index of a $1$-planar graph with maximum degree $\Delta$ is at most roughly $24\Delta$ (thus linear in $\Delta$). The proof of this result is based on the existence of light edges in $1$-planar graphs with minimum degree at least~$3$.
Section:
Graph Theory
Tim Smith.
A morphic word is obtained by iterating a morphism to generate an infinite
word, and then applying a coding. We characterize morphic words with polynomial
growth in terms of a new type of infinite word called a $\textit{zigzag word}$.
A zigzag word is represented by an initial string, followed by a finite list of
terms, each of which repeats for each $n \geq 1$ in one of three ways: it grows
forward [$t(1)\ t(2)\ \dotsm\ t(n)]$, backward [$t(n)\ \dotsm\ t(2)\ t(1)$], or
just occurs once [$t$]. Each term can recursively contain subterms with their
own forward and backward repetitions. We show that an infinite word is morphic
with growth $\Theta(n^k)$ iff it is a zigzag word of depth $k$. As corollaries,
we obtain that the morphic words with growth $O(n)$ are exactly the ultimately
periodic words, and the morphic words with growth $O(n^2)$ are exactly the
multilinear words.
Section:
Automata, Logic and Semantics
Winfried Hochstättler ; Felix Schröder ; Raphael Steiner.
It has been shown by Bokal et al. that deciding 2-colourability of digraphs
is an NP-complete problem. This result was later on extended by Feder et al. to
prove that deciding whether a digraph has a circular $p$-colouring is
NP-complete for all rational $p>1$. In this paper, we consider the complexity
of corresponding decision problems for related notions of fractional colourings
for digraphs and graphs, including the star dichromatic number, the fractional
dichromatic number and the circular vertex arboricity. We prove the following
results:
Deciding if the star dichromatic number of a digraph is at most $p$ is
NP-complete for every rational $p>1$.
Deciding if the fractional dichromatic number of a digraph is at most $p$ is
NP-complete for every $p>1, p \neq 2$.
Deciding if the circular vertex arboricity of a graph is at most $p$ is
NP-complete for every rational $p>1$.
To show these results, different techniques are required in each case. In
order to prove the first result, we relate the star dichromatic number to a new
notion of homomorphisms between digraphs, called circular homomorphisms, which
might be of independent interest. We provide a classification of the
computational complexities of the corresponding homomorphism colouring problems
similar to the one derived by Feder et al. for acyclic homomorphisms.
Section:
Graph Theory
H. Amjadi ; N. Soltankhah.
The flower at a point x in a Steiner triple system (X; B) is the set of all
triples containing x. Denote by J3F(r) the set of all integers k such that
there exists a collection of three STS(2r+1) mutually intersecting in the same
set of k + r triples, r of them being the triples of a common flower.
In this article we determine the set J3F(r) for any positive integer r = 0, 1
(mod 3) (only some cases are left undecided for r = 6, 7, 9, 24), and establish
that J3F(r) = I3F(r) for r = 0, 1 (mod 3) where I3F(r) = {0, 1,...,
2r(r-1)/3-8, 2r(r-1)/3-6, 2r(r-1)/3}.
Section:
Combinatorics
James D. Currie ; Lucas Mol ; Narad Rampersad.
A word of length $n$ is rich if it contains $n$ nonempty palindromic factors.
An infinite word is rich if all of its finite factors are rich. Baranwal and
Shallit produced an infinite binary rich word with critical exponent
$2+\sqrt{2}/2$ ($\approx 2.707$) and conjectured that this was the least
possible critical exponent for infinite binary rich words (i.e., that the
repetition threshold for binary rich words is $2+\sqrt{2}/2$). In this article,
we give a structure theorem for infinite binary rich words that avoid
$14/5$-powers (i.e., repetitions with exponent at least 2.8). As a consequence,
we deduce that the repetition threshold for binary rich words is
$2+\sqrt{2}/2$, as conjectured by Baranwal and Shallit. This resolves an open
problem of Vesti for the binary alphabet; the problem remains open for larger
alphabets.
Section:
Analysis of Algorithms
Raheel Anwar ; Muhammad Irfan Yousuf ; Muhammad Abid.
It is commonly believed that real networks are scale-free and fraction of
nodes $P(k)$ with degree $k$ satisfies the power law $P(k) \propto k^{-\gamma}
\text{ for } k > k_{min} > 0$. Preferential attachment is the mechanism that
has been considered responsible for such organization of these networks. In
many real networks, degree distribution before the $k_{min}$ varies very slowly
to the extent of being uniform as compared with the degree distribution for $k
> k_{min}$ . In this paper, we proposed a model that describe this particular
degree distribution for the whole range of $k>0$. We adopt a two step approach.
In the first step, at every time stamp we add a new node to the network and
attach it with an existing node using preferential attachment method. In the
second step, we add edges between existing pairs of nodes with the node
selection based on the uniform probability distribution. Our approach generates
weakly scale-free networks that closely follow the degree distribution of
real-world networks. We perform comprehensive mathematical analysis of the
model in the discrete domain and compare the degree distribution generated by
these models with that of real-world networks.
Alizée Gagnon ; Alexander Hassler ; Jerry Huang ; Aaron Krim-Yee ; Fionn Mc Inerney ; Andrés Zacarías ; Ben Seamone ; Virgélot Virgile.
In the eternal domination game, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices and no more than one guard may occupy a vertex. The goal is to determine the eternal domination number of a graph which is the minimum number of guards required to defend the graph against an infinite sequence of attacks. In this paper, we continue the study of the eternal domination game on strong grids. Cartesian grids have been vastly studied with tight bounds for small grids such as 2×n, 3×n, 4×n, and 5×n grids, and recently it was proven in [Lamprou et al., CIAC 2017, 393-404] that the eternal domination number of these grids in general is within O(m + n) of their domination number which lower bounds the eternal domination number. Recently, Finbow et al. proved that the eternal domination number of strong grids is upper bounded by mn 6 + O(m + n). We adapt the techniques of [Lamprou et al., CIAC 2017, 393-404] to prove that the eternal domination number of strong grids is upper bounded by mn 7 + O(m + n). While this does not improve upon a recently announced bound of ⎡m/3⎤ x⎡n/3⎤ + O(m √ n) [Mc Inerney, Nisse, Pérennes, HAL archives, 2018; Mc Inerney, Nisse, Pérennes, CIAC 2019] in the general case, we show that our bound is an improvement in the case where the smaller of the two dimensions is at most 6179.
Section:
Graph Theory
Pascal Caron ; Edwin Hamel-De le court ; Jean-Gabriel Luque ; Bruno Patrou.
A monster is an automaton in which every function from states to states is
represented by at least one letter. A modifier is a set of functions allowing
one to transform a set of automata into one automaton. We revisit some language
transformation algorithms in terms of modifier and monster. These new
theoretical concepts allow one to find easily some state complexities. We
illustrate this by retrieving the state complexity of the Star of Intersection
and the one of the Square root operation.
Section:
Automata, Logic and Semantics
Wady Naanaa.
Finding a solution to a Constraint Satisfaction Problem (CSP) is known to be an NP-hard task. This has motivatedthe multitude of works that have been devoted to developing techniques that simplify CSP instances before or duringtheir resolution.The present work proposes rigidly enforced schemes for simplifying binary CSPs that allow the narrowing of valuedomains, either via value merging or via value suppression. The proposed schemes can be viewed as parametrizedgeneralizations of two widely studied CSP simplification techniques, namely, value merging and neighbourhoodsubstitutability. Besides, we show that both schemes may be strengthened in order to allow variable elimination,which may result in more significant simplifications. This work contributes also to the theory of tractable CSPs byidentifying a new tractable class of binary CSP.
Section:
Discrete Algorithms
Ruy Fabila-Monroy ; Carlos Hidalgo-Toscano ; Jesús Leaños ; Mario Lomelí-Haro.
Let $P$ be a set of $n\geq 4$ points in general position in the plane.
Consider all the closed straight line segments with both endpoints in $P$.
Suppose that these segments are colored with the rule that disjoint segments
receive different colors. In this paper we show that if $P$ is the point
configuration known as the double chain, with $k$ points in the upper convex
chain and $l \ge k$ points in the lower convex chain, then $k+l- \left\lfloor
\sqrt{2l+\frac{1}{4}} - \frac{1}{2}\right\rfloor$ colors are needed and that
this number is sufficient.
Section:
Graph Theory
Gülnaz Boruzanlı Ekinci ; John Baptist Gauci.
For positive integers $n,k$ and $t$, the uniform subset graph $G(n, k, t)$
has all $k$-subsets of $\{1,2,\ldots, n\}$ as vertices and two $k$-subsets are
joined by an edge if they intersect at exactly $t$ elements. The Johnson graph
$J(n,k)$ corresponds to $G(n,k,k-1)$, that is, two vertices of $J(n,k)$ are
adjacent if the intersection of the corresponding $k$-subsets has size $k-1$. A
super vertex-cut of a connected graph is a set of vertices whose removal
disconnects the graph without isolating a vertex and the super-connectivity is
the size of a minimum super vertex-cut. In this work, we fully determine the
super-connectivity of the family of Johnson graphs $J(n,k)$ for $n\geq k\geq
1$.
Section:
Graph Theory
Aleksejs Naumovs ; Maksims Dimitrijevs ; Abuzer Yakaryılmaz.
It is known that 2-state binary and 3-state unary probabilistic finite
automata and 2-state unary quantum finite automata recognize uncountably many
languages with cutpoints. These results have been obtained by associating each
recognized language with a cutpoint and then by using the fact that there are
uncountably many cutpoints. In this note, we prove the same results for fixed
cutpoints: each recognized language is associated with an automaton (i.e.,
algorithm), and the proofs use the fact that there are uncountably many
automata. For each case, we present a new construction.
Section:
Automata, Logic and Semantics
Xinwei He ; A. J. Hildebrand ; Yuchen Li ; Yunyi Zhang.
Let $S_{a,b}$ denote the sequence of leading digits of $a^n$ in base $b$. It
is well known that if $a$ is not a rational power of $b$, then the sequence
$S_{a,b}$ satisfies Benford's Law; that is, digit $d$ occurs in $S_{a,b}$ with
frequency $\log_{b}(1+1/d)$, for $d=1,2,\dots,b-1$.
In this paper, we investigate the \emph{complexity} of such sequences. We
focus mainly on the \emph{block complexity}, $p_{a,b}(n)$, defined as the
number of distinct blocks of length $n$ appearing in $S_{a,b}$. In our main
result we determine $p_{a,b}(n)$ for all squarefree bases $b\ge 5$ and all
rational numbers $a>0$ that are not integral powers of $b$. In particular, we
show that, for all such pairs $(a,b)$, the complexity function $p_{a,b}(n)$ is
\emph{affine}, i.e., satisfies $p_{a,b}(n)=c_{a,b} n + d_{a,b}$ for all
$n\ge1$, with coefficients $c_{a,b}\ge1$ and $d_{a,b}\ge0$, given explicitly in
terms of $a$ and $b$. We also show that the requirement that $b$ be squarefree
cannot be dropped: If $b$ is not squarefree, then there exist integers $a$ with
$1<a<b$ for which $p_{a,b}(n)$ is not of the above form.
We use this result to obtain sharp upper and lower bounds for $p_{a,b}(n)$,
and to determine the asymptotic behavior of this function as $b\to\infty$
through squarefree values. We also consider the question which linear functions
$p(n)=cn+d$ arise as the complexity function $p_{a,b}(n)$ of some leading digit
sequence $S_{a,b}$.
We conclude with a discussion of other […]
Section:
Automata, Logic and Semantics
Łukasz Merta.
A formal inverse of a given automatic sequence (the sequence of coefficients
of the composition inverse of its associated formal power series) is also
automatic. The comparison of properties of the original sequence and its formal
inverse is an interesting problem. Such an analysis has been done before for
the Thue{Morse sequence. In this paper, we describe arithmetic properties of
formal inverses of the generalized Thue-Morse sequences and formal inverses of
two modifications of the Rudin{Shapiro sequence. In each case, we give the
recurrence relations and the automaton, then we analyze the lengths of strings
of consecutive identical letters as well as the frequencies of letters. We also
compare the obtained results with the original sequences.
Section:
Automata, Logic and Semantics
Hongliang Lu ; Wei Wang ; Juan Yan.
Let $G=(X,Y;E)$ be a bipartite graph, where $X$ and $Y$ are color classes and
$E$ is the set of edges of $G$. Lovász and Plummer \cite{LoPl86} asked
whether one can decide in polynomial time that a given bipartite graph $G=(X,Y;
E)$ admits a 1-anti-factor, that is subset $F$ of $E$ such that $d_F(v)=1$ for
all $v\in X$ and $d_F(v)\neq 1$ for all $v\in Y$. Cornuéjols \cite{CHP}
answered this question in the affirmative. Yu and Liu \cite{YL09} asked
whether, for a given integer $k\geq 3$, every $k$-regular bipartite graph
contains a 1-anti-factor. This paper answers this question in the affirmative.
Section:
Graph Theory
János Balogh ; Cosmin Bonchiş ; Diana Diniş ; Gabriel Istrate ; Ioan Todinca.
We investigate the partitioning of partial orders into a minimal number of
heapable subsets. We prove a characterization result reminiscent of the proof
of Dilworth's theorem, which yields as a byproduct a flow-based algorithm for
computing such a minimal decomposition. On the other hand, in the particular
case of sets and sequences of intervals we prove that this minimal
decomposition can be computed by a simple greedy-type algorithm. The paper ends
with a couple of open problems related to the analog of the Ulam-Hammersley
problem for decompositions of sets and sequences of random intervals into
heapable sets.
Section:
Combinatorics
Ümit Işlak ; Alperen Y. Özdemir.
The purpose of this paper is to study a statistic that is used to compare the
similarity between two strings, which is first introduced by Michael Steele in
1982. It was proposed as an alternative to the length of the longest common
subsequences, for which the variance problem is still open. Our results include
moment asymptotics and distributional asymptotics for Steele's statistic and a
variation of it in random words and random permutations.
Section:
Combinatorics
Claudson F. Bornstein ; Martin Charles Golumbic ; Tanilson D. Santos ; Uéverton S. Souza ; Jayme L. Szwarcfiter.
Golumbic, Lipshteyn, and Stern defined in 2009 the class of EPG graphs, the
intersection graph class of edge paths on a grid. An EPG graph $G$ is a graph
that admits a representation where its vertices correspond to paths in a grid
$Q$, such that two vertices of $G$ are adjacent if and only if their
corresponding paths in $Q$ have a common edge. If the paths in the
representation have at most $k$ bends, we say that it is a $B_k$-EPG
representation. A collection $C$ of sets satisfies the Helly property when
every sub-collection of $C$ that is pairwise intersecting has at least one
common element. In this paper, we show that given a graph $G$ and an integer
$k$, the problem of determining whether $G$ admits a $B_k$-EPG representation
whose edge-intersections of paths satisfy the Helly property, so-called
Helly-$B_k$-EPG representation, is in NP, for every $k$ bounded by a polynomial
function of $|V(G)|$. Moreover, we show that the problem of recognizing
Helly-$B_1$-EPG graphs is NP-complete, and it remains NP-complete even when
restricted to 2-apex and 3-degenerate graphs.
Section:
Graph Theory
Lubomíra Dvořáková ; Kateřina Medková ; Edita Pelantová.
We determine the critical exponent and the recurrence function of
complementary symmetric Rote sequences. The formulae are expressed in terms of
the continued fraction expansions associated with the S-adic representations of
the corresponding standard Sturmian sequences. The results are based on a
thorough study of return words to bispecial factors of Sturmian sequences.
Using the formula for the critical exponent, we describe all complementary
symmetric Rote sequences with the critical exponent less than or equal to 3,
and we show that there are uncountably many complementary symmetric Rote
sequences with the critical exponent less than the critical exponent of the
Fibonacci sequence. Our study is motivated by a~conjecture on sequences rich in
palindromes formulated by Baranwal and Shallit. Its recent solution by Curie,
Mol, and Rampersad uses two particular complementary symmetric Rote sequences.
Section:
Combinatorics
Hui Rao ; Lei Ren ; Yang Wang.
We study the dissection of a square into congruent convex polygons. Yuan
\emph{et al.} [Dissecting the square into five congruent parts, Discrete Math.
\textbf{339} (2016) 288-298] asked whether, if the number of tiles is a prime
number $\geq 3$, it is true that the tile must be a rectangle.
We conjecture that the same conclusion still holds even if the number of
tiles is an odd number $\geq 3$.
Our conjecture has been confirmed for triangles in earlier works. We prove
that the conjecture holds if either the tile is a convex $q$-gon with $q\geq 6$
or it is a right-angle trapezoid.
Section:
Combinatorics
Jonathan Klawitter.
A rearrangement operation makes a small graph-theoretical change to a
phylogenetic network to transform it into another one. For unrooted
phylogenetic trees and networks, popular rearrangement operations are tree
bisection and reconnection (TBR) and prune and regraft (PR) (called subtree
prune and regraft (SPR) on trees). Each of these operations induces a metric on
the sets of phylogenetic trees and networks. The TBR-distance between two
unrooted phylogenetic trees $T$ and $T'$ can be characterised by a maximum
agreement forest, that is, a forest with a minimum number of components that
covers both $T$ and $T'$ in a certain way. This characterisation has
facilitated the development of fixed-parameter tractable algorithms and
approximation algorithms. Here, we introduce maximum agreement graphs as a
generalisations of maximum agreement forests for phylogenetic networks. While
the agreement distance -- the metric induced by maximum agreement graphs --
does not characterise the TBR-distance of two networks, we show that it still
provides constant-factor bounds on the TBR-distance. We find similar results
for PR in terms of maximum endpoint agreement graphs.
Section:
Graph Theory
Chunyan Yan ; Zhicong Lin.
The enumeration of inversion sequences avoiding a single pattern was
initiated by Corteel--Martinez--Savage--Weselcouch and Mansour--Shattuck
independently. Their work has sparked various investigations of generalized
patterns in inversion sequences, including patterns of relation triples by
Martinez and Savage, consecutive patterns by Auli and Elizalde, and vincular
patterns by Lin and Yan. In this paper, we carried out the systematic study of
inversion sequences avoiding two patterns of length $3$. Our enumerative
results establish further connections to the OEIS sequences and some classical
combinatorial objects, such as restricted permutations, weighted ordered trees
and set partitions. Since patterns of relation triples are some special
multiple patterns of length $3$, our results complement the work by Martinez
and Savage. In particular, one of their conjectures regarding the enumeration
of $(021,120)$-avoiding inversion sequences is solved.
Section:
Combinatorics