Christoph Brause ; Michael A. Henning ; Marcin Krzywkowski.
A set $S$ of vertices in a graph $G$ is a $2$-dominating set if every vertex
of $G$ not in $S$ is adjacent to at least two vertices in $S$, and $S$ is a
$2$-independent set if every vertex in $S$ is adjacent to at most one vertex of
$S$. The $2$-domination number $\gamma_2(G)$ is the minimum cardinality of a
$2$-dominating set in $G$, and the $2$-independence number $\alpha_2(G)$ is the
maximum cardinality of a $2$-independent set in $G$. Chellali and Meddah [{\it
Trees with equal $2$-domination and $2$-independence numbers,} Discussiones
Mathematicae Graph Theory 32 (2012), 263--270] provided a constructive
characterization of trees with equal $2$-domination and $2$-independence
numbers. Their characterization is in terms of global properties of a tree, and
involves properties of minimum $2$-dominating and maximum $2$-independent sets
in the tree at each stage of the construction. We provide a constructive
characterization that relies only on local properties of the tree at each stage
of the construction.
Section:
Graph Theory
Sylvain Gravier ; Kahina Meslem ; Simon Schmidt ; Souad Slimani.
The distinguishing number of a graph $G$ is a symmetry related graph
invariant whose study started two decades ago. The distinguishing number $D(G)$
is the least integer $d$ such that $G$ has a $d$-distinguishing coloring. A
distinguishing $d$-coloring is a coloring $c:V(G)\rightarrow\{1,...,d\}$
invariant only under the trivial automorphism. In this paper, we introduce a
game variant of the distinguishing number. The distinguishing game is a game
with two players, the Gentle and the Rascal, with antagonist goals. This game
is played on a graph $G$ with a set of $d\in\mathbb N^*$ colors. Alternately,
the two players choose a vertex of $G$ and color it with one of the $d$ colors.
The game ends when all the vertices have been colored. Then the Gentle wins if
the coloring is distinguishing and the Rascal wins otherwise. This game leads
to define two new invariants for a graph $G$, which are the minimum numbers of
colors needed to ensure that the Gentle has a winning strategy, depending on
who starts. These invariants could be infinite, thus we start by giving
sufficient conditions to have infinite game distinguishing numbers. We also
show that for graphs with cyclic automorphisms group of prime odd order, both
game invariants are finite. After that, we define a class of graphs, the
involutive graphs, for which the game distinguishing number can be
quadratically bounded above by the classical distinguishing number. The
definition of this class is closely related to imprimitive […]
Section:
Graph Theory
Colin Defant.
Given a set $Y$ of decreasing plane trees and a permutation $\pi$, how many
trees in $Y$ have $\pi$ as their postorder? Using combinatorial and geometric
constructions, we provide a method for answering this question for certain sets
$Y$ and all permutations $\pi$. We then provide applications of our results to
the study of the deterministic stack-sorting algorithm.
Section:
Combinatorics
Susan van Aardt ; Alewyn Petrus Burger ; Marietjie Frick.
A digraph is \emph{traceable} if it has a path that visits every vertex. A digraph $D$ is \emph{hypotraceable} if $D$ is not traceable but $D-v$ is traceable for every vertex $v\in V(D)$. It is known that there exists a planar hypotraceable digraph of order $n$ for every $n\geq 7$, but no examples of planar hypotraceable oriented graphs (digraphs without 2-cycles) have yet appeared in the literature. We show that there exists a planar hypotraceable oriented graph of order $n$ for every even $n \geq 10$, with the possible exception of $n = 14$.
Section:
Graph Theory
David Callan ; Toufik Mansour ; Mark Shattuck.
This is the first of two papers in which we determine all 242 Wilf classes of triples of 4-letter patterns by showing that there are 32 non-singleton Wilf classes. There are 317 symmetry classes of triples of 4-letter patterns and after computer calculation of initial terms, the problem reduces to showing that counting sequences that appear to be the same (agree in the first 16 terms) are in fact identical. This amounts to counting avoiders for 107 representative triples. The insertion encoding algorithm (INSENC) applies to many of them and some others have been previously counted. Thus there remain 36 triples. In this paper, we find the generating function for the first 18 of these triples and in a second paper, we treat the other 18. The generating function turns out to be algebraic in each case. Our methods are both combinatorial and analytic, including decompositions by left-right maxima and by initial letters. Sometimes this leads to an algebraic equation for the generating function, sometimes to a functional equation or a multi-index recurrence that succumbs to the kernel method. A bijection is used in one of the cases (Case 50).
Section:
Combinatorics
David Callan ; Toufik Mansour ; Mark Shattuck.
This is the second of two papers in which we determine all 242 Wilf classes of triples of 4-letter patterns by showing that there are 32 non-singleton Wilf classes. There are 317 symmetry classes of triples of 4-letter patterns and after computer calculation of initial terms, the problem reduces to showing that counting sequences that appear to be the same (agree in the first 16 terms) are in fact identical. This amounts to counting avoiders for 107 representative triples. The insertion encoding algorithm (INSENC) applies to many of them and some others have been previously counted. There remain 36 triples and the first paper dealt with the first 18. In this paper, we find the generating function for the last 18 triples which turns out to be algebraic in each case. Our methods are both combinatorial and analytic, including decomposi-tions by left-right maxima and by initial letters. Sometimes this leads to an algebraic equation for the generating function, sometimes to a functional equation or a multi-index recurrence that succumbs to the kernel method. A particularly nice so-called cell decomposition is used in one of the cases (Case 238).
Section:
Combinatorics
Jean Cardinal ; Jean-Paul Doignon ; Keno Merckx.
Chordal graph shelling antimatroids have received little attention with
regard to their combinatorial properties and related optimization problems, as
compared to the case of poset shelling antimatroids. Here we consider a special
case of these antimatroids, namely the split graph shelling antimatroids. We
show that the feasible sets of such an antimatroid relate to some poset
shelling antimatroids constructed from the graph. We discuss a few
applications, obtaining in particular a simple polynomial-time algorithm to
find a maximum weight feasible set. We also provide a simple description of the
circuits and the free sets.
Section:
Combinatorics
John Campbell.
Recent research on the combinatorics of finite sets has explored the structure of symmetric difference-closed sets, and recent research in combinatorial group theory has concerned the enumeration of commuting involutions in $S_{n}$ and $A_{n}$. In this article, we consider an interesting combination of these two subjects, by introducing classes of symmetric difference-closed sets of elements which correspond in a natural way to commuting involutions in $S_{n}$ and $A_{n}$. We consider the natural combinatorial problem of enumerating symmetric difference-closed sets consisting of subsets of sets consisting of pairwise disjoint $2$-subsets of $[n]$, and the problem of enumerating symmetric difference-closed sets consisting of elements which correspond to commuting involutions in $A_{n}$. We prove explicit combinatorial formulas for symmetric difference-closed sets of these forms, and we prove a number of conjectured properties related to such sets which had previously been discovered experimentally using the On-Line Encyclopedia of Integer Sequences.
Section:
Combinatorics
Behrouz Zolfaghari ; Mehran S. Fallah ; Mehdi Sedighi.
An S-restricted composition of a positive integer n is an ordered partition
of n where each summand is drawn from a given subset S of positive integers.
There are various problems regarding such compositions which have received
attention in recent years. This paper is an attempt at finding a closed- form
formula for the number of S-restricted compositions of n. To do so, we reduce
the problem to finding solutions to corresponding so-called interpreters which
are linear homogeneous recurrence relations with constant coefficients. Then,
we reduce interpreters to Diophantine equations. Such equations are not in
general solvable. Thus, we restrict our attention to those S-restricted
composition problems whose interpreters have a small number of coefficients,
thereby leading to solvable Diophantine equations. The formalism developed is
then used to study the integer sequences related to some well-known cases of
the S-restricted composition problem.
Section:
Combinatorics
Yasir Ali ; Asma Javaid.
This paper deals with two-sided matching market with two disjoint sets, i.e.
the set of buyers and the set of sellers. Each seller can trade with at most
with one buyer and vice versa. Money is transferred from sellers to buyers for
an indivisible goods that buyers own. Valuation functions, for participants of
both sides, are represented by strictly increasing functions with money
considered as discrete variable. An algorithm is devised to prove the existence
of stability for this model.
Section:
Discrete Algorithms
Włodzimierz Moczurad.
Codes with various kinds of decipherability, weaker than the usual unique
decipherability, have been studied since multiset decipherability was
introduced in mid-1980s. We consider decipherability of directed figure codes,
where directed figures are defined as labelled polyominoes with designated
start and end points, equipped with catenation operation that may use a merging
function to resolve possible conflicts. This is one of possible extensions
generalizing words and variable-length codes to planar structures. Here,
verification whether a given set is a code is no longer decidable in general.
We study the decidability status of figure codes depending on catenation type
(with or without a merging function), decipherability kind (unique, multiset,
set or numeric) and code geometry (several classes determined by relative
positions of start and end points of figures). We give decidability or
undecidability proofs in all but two cases that remain open.
Section:
Automata, Logic and Semantics
Huihui Zhang ; Jing Chen ; Shuchao Li.
Let $Sz(G),Sz^*(G)$ and $W(G)$ be the Szeged index, revised Szeged index and
Wiener index of a graph $G.$ In this paper, the graphs with the fourth, fifth,
sixth and seventh largest Wiener indices among all unicyclic graphs of order
$n\geqslant 10$ are characterized; as well the graphs with the first, second,
third, and fourth largest Wiener indices among all bicyclic graphs are
identified. Based on these results, further relation on the quotients between
the (revised) Szeged index and the Wiener index are studied. Sharp lower bound
on $Sz(G)/W(G)$ is determined for all connected graphs each of which contains
at least one non-complete block. As well the connected graph with the second
smallest value on $Sz^*(G)/W(G)$ is identified for $G$ containing at least one
cycle.
Section:
Graph Theory
Arman Boyacı ; Tınaz Ekim ; Mordechai Shalom ; Shmuel Zaks.
The families EPT (resp. EPG) Edge Intersection Graphs of Paths in a tree
(resp. in a grid) are well studied graph classes. Recently we introduced the
graph classes Edge-Intersecting and Non-Splitting Paths in a Tree ENPT, and in
a Grid (ENPG). It was shown that ENPG contains an infinite hierarchy of
subclasses that are obtained by restricting the number of bends in the paths.
Motivated by this result, in this work we focus on one bend {ENPG} graphs. We
show that one bend ENPG graphs are properly included in two bend ENPG graphs.
We also show that trees and cycles are one bend ENPG graphs, and characterize
the split graphs and co-bipartite graphs that are one bend ENPG. We prove that
the recognition problem of one bend ENPG split graphs is NP-complete even in a
very restricted subfamily of split graphs. Last we provide a linear time
recognition algorithm for one bend ENPG co-bipartite graphs.
Section:
Graph Theory
Luerbio Faria ; Sulamita Klein ; Ignasi Sau ; Rubens Sucupira.
A graph $G$ is signed if each edge is assigned $+$ or $-$. A signed graph is
balanced if there is a bipartition of its vertex set such that an edge has sign
$-$ if and only if its endpoints are in different parts. The Edwards-Erdös
bound states that every graph with $n$ vertices and $m$ edges has a balanced
subgraph with at least $\frac{m}{2}+\frac{n-1}{4}$ edges. In the Signed Max Cut
Above Tight Lower Bound (Signed Max Cut ATLB) problem, given a signed graph $G$
and a parameter $k$, the question is whether $G$ has a balanced subgraph with
at least $\frac{m}{2}+\frac{n-1}{4}+\frac{k}{4}$ edges. This problem
generalizes Max Cut Above Tight Lower Bound, for which a kernel with $O(k^5)$
vertices was given by Crowston et al. [ICALP 2012, Algorithmica 2015]. Crowston
et al. [TCS 2013] improved this result by providing a kernel with $O(k^3)$
vertices for the more general Signed Max Cut ATLB problem. In this article we
are interested in improving the size of the kernels for Signed Max Cut ATLB on
restricted graph classes for which the problem remains hard. For two integers
$r,\ell \geq 0$, a graph $G$ is an $(r,\ell)$-graph if $V(G)$ can be
partitioned into $r$ independent sets and $\ell$ cliques. Building on the
techniques of Crowston et al. [TCS 2013], we provide a kernel with $O(k^2)$
vertices on $(r,\ell)$-graphs for any fixed $r,\ell \geq 0$, and a simple
linear kernel on subclasses of split graphs for which we prove that the problem
is still NP-hard.
Section:
Discrete Algorithms
Jeffrey Remmel ; Sai-nan Zheng.
The study of patterns in permutations associated with forests of binary
shrubs was initiated by D. Bevan et al.. In this paper, we study five different
types of rise statistics that can be associated with such permutations and find
the generating functions for the distribution of such rise statistics.
Section:
Combinatorics
Herman Z. Q. Chen ; Sergey Kitaev ; Torsten Mütze ; Brian Y. Sun.
A universal word for a finite alphabet $A$ and some integer $n\geq 1$ is a
word over $A$ such that every word in $A^n$ appears exactly once as a subword
(cyclically or linearly). It is well-known and easy to prove that universal
words exist for any $A$ and $n$. In this work we initiate the systematic study
of universal partial words. These are words that in addition to the letters
from $A$ may contain an arbitrary number of occurrences of a special `joker'
symbol $\Diamond\notin A$, which can be substituted by any symbol from $A$. For
example, $u=0\Diamond 011100$ is a linear partial word for the binary alphabet
$A=\{0,1\}$ and for $n=3$ (e.g., the first three letters of $u$ yield the
subwords $000$ and $010$). We present results on the existence and
non-existence of linear and cyclic universal partial words in different
situations (depending on the number of $\Diamond$s and their positions),
including various explicit constructions. We also provide numerous examples of
universal partial words that we found with the help of a computer.
Section:
Combinatorics
Alessandra Cherubini ; Achille Frigeri ; Zuhua Liu.
A finite deterministic (semi)automaton A = (Q, Σ, δ) is k-compressible if there is some word w ∈ Σ + such that theimage of its state set Q under the natural action of w is reduced by at least k states. Such word w, if it exists, is calleda k-compressing word for A and A is said to be k-compressed by w. A word is k-collapsing if it is k-compressing foreach k-compressible automaton, and it is k-synchronizing if it is k-compressing for all k-compressible automata withk+1 states. We compute a set W of short words such that each 3-compressible automaton on a two-letter alphabetis 3-compressed at least by a word in W. Then we construct a shortest common superstring of the words in W and,with a further refinement, we obtain a 3-collapsing word of length 53. Moreover, as previously announced, we showthat the shortest 3-synchronizing word is not 3-collapsing, illustrating the new bounds 34 ≤ c(2, 3) ≤ 53 for the length c(2, 3) of the shortest 3-collapsing word on a two-letter alphabet.
Section:
Automata, Logic and Semantics
A. Kündgen ; T. Talbot.
A repetition is a sequence of symbols in which the first half is the same as
the second half. An edge-coloring of a graph is repetition-free or
nonrepetitive if there is no path with a color pattern that is a repetition.
The minimum number of colors so that a graph has a nonrepetitive edge-coloring
is called its Thue edge-chromatic number.
We improve on the best known general upper bound of $4\Delta-4$ for the Thue
edge-chromatic number of trees of maximum degree $\Delta$ due to Alon,
Grytczuk, Ha{\l}uszczak and Riordan (2002) by providing a simple nonrepetitive
edge-coloring with $3\Delta-2$ colors.
Section:
Graph Theory
Chuanan Wei ; Xiaoxia Wang.
Using $q$-series identities and series rearrangement, we establish several
extensions of $q$-Watson formulas with two extra integer parameters. Then they
and Sears' transformation formula are utilized to derive some generalizations
of $q$-Dixon formulas and $q$-Whipple formulas with two extra integer
parameters. As special cases of these results, many interesting evaluations of
series of $q$-Watson,$q$-Dixon, and $q$-Whipple type are displayed.
Section:
Combinatorics
Jessica Enright ; Lorna Stewart.
The overlap graphs of subtrees of a tree are equivalent to subtree filament
graphs, the overlap graphs of subtrees of a star are cocomparability graphs,
and the overlap graphs of subtrees of a caterpillar are interval filament
graphs. In this paper, we show the equivalence of many more classes of subtree
overlap and subtree filament graphs, and equate them to classes of complements
of cochordal-mixed graphs. Our results generalize the previously known results
mentioned above.
Section:
Graph Theory
Julien Bensmail ; Mohammed Senhaji ; Kasper Szabo Lyngsie.
This paper is dedicated to studying the following question: Is it always possible to injectively assign the weights 1, ..., |E(G)| to the edges of any given graph G (with no component isomorphic to K2) so that every two adjacent vertices of G get distinguished by their sums of incident weights? One may see this question as a combination of the well-known 1-2-3 Conjecture and the Antimagic Labelling Conjecture. Throughout this paper, we exhibit evidence that this question might be true. Benefiting from the investigations on the Antimagic Labelling Conjecture, we first point out that several classes of graphs, such as regular graphs, indeed admit such assignments. We then show that trees also do, answering a recent conjecture of Arumugam, Premalatha, Bača and Semaničová-Feňovčíková. Towards a general answer to the question above, we then prove that claimed assignments can be constructed for any graph, provided we are allowed to use some number of additional edge weights. For some classes of sparse graphs, namely 2-degenerate graphs and graphs with maximum average degree 3, we show that only a small (constant) number of such additional weights suffices.
Section:
Graph Theory
Silvia Businger.
Consider $ m $ copies of an irreducible, aperiodic Markov chain $ Y $ taking
values in a finite state space. The asymptotics as $ m $ tends to infinity, of
the first time from which on the trajectories of the $ m $ copies differ, have
been studied by Szpankowski (1991) in the setting of tries. We use a different
approach and model the $ m $ trajectories by a variant of the occupancy scheme,
where we consider a nested sequence of boxes. This approach will enable us to
extend the result to the case when the transition probabilities are random. We
moreover use the same techniques to study the asymptotics as $ m $ tends to
infinity of the time up to which we have observed all the possible trajectories
of $ Y $ in random and nonrandom scenery.
Section:
Analysis of Algorithms
Cyril Banderier ; Michael Wallner.
In queuing theory, it is usual to have some models with a "reset" of the
queue. In terms of lattice paths, it is like having the possibility of jumping
from any altitude to zero. These objects have the interesting feature that they
do not have the same intuitive probabilistic behaviour as classical Dyck paths
(the typical properties of which are strongly related to Brownian motion
theory), and this article quantifies some relations between these two types of
paths. We give a bijection with some other lattice paths and a link with a
continued fraction expansion. Furthermore, we prove several formulae for
related combinatorial structures conjectured in the On-Line Encyclopedia of
Integer Sequences. Thanks to the kernel method and via analytic combinatorics,
we provide the enumeration and limit laws of these "lattice paths with
catastrophes" for any finite set of jumps. We end with an algorithm to generate
such lattice paths uniformly at random.
Section:
Analysis of Algorithms
Isolde Adler ; Ngoc Khang Le ; Haiko Müller ; Marko Radovanović ; Nicolas Trotignon ; Kristina Vušković.
We present a class of (diamond, even hole)-free graphs with no clique cutset
that has unbounded rank-width. In general, even-hole-free graphs have unbounded
rank-width, because chordal graphs are even-hole-free. A.A. da Silva, A. Silva
and C. Linhares-Sales (2010) showed that planar even-hole-free graphs have
bounded rank-width, and N.K. Le (2016) showed that even-hole-free graphs with
no star cutset have bounded rank-width. A natural question is to ask, whether
even-hole-free graphs with no clique cutsets have bounded rank-width. Our
result gives a negative answer. Hence we cannot apply Courcelle and Makowsky's
meta-theorem which would provide efficient algorithms for a large number of
problems, including the maximum independent set problem, whose complexity
remains open for (diamond, even hole)-free graphs.
Section:
Graph Theory
Didem Gözüpek ; Ademir Hujdurović ; Martin Milanič.
A graph is said to be well-dominated if all its minimal dominating sets are
of the same size. The class of well-dominated graphs forms a subclass of the
well studied class of well-covered graphs. While the recognition problem for
the class of well-covered graphs is known to be co-NP-complete, the recognition
complexity of well-dominated graphs is open.
In this paper we introduce the notion of an irreducible dominating set, a
variant of dominating set generalizing both minimal dominating sets and minimal
total dominating sets. Based on this notion, we characterize the family of
minimal dominating sets in a lexicographic product of two graphs and derive a
characterization of the well-dominated lexicographic product graphs. As a side
result motivated by this study, we give a polynomially testable
characterization of well-dominated graphs with domination number two, and show,
more generally, that well-dominated graphs can be recognized in polynomial time
in any class of graphs with bounded domination number. Our results include a
characterization of dominating sets in lexicographic product graphs, which
generalizes the expression for the domination number of such graphs following
from works of Zhang et al. (2011) and of \v{S}umenjak et al. (2012).
Section:
Graph Theory