Hongliang Lu ; Qinglin Yu.
A connected graph $G$ with at least $2m + 2n + 2$ vertices which contains a
perfect matching is $E(m, n)$-{\it extendable}, if for any two sets of disjoint
independent edges $M$ and $N$ with $|M| = m$ and $|N|= n$, there is a perfect
matching $F$ in $G$ such that $M\subseteq F$ and $N\cap F=\emptyset$.
Similarly, a connected graph with at least $n+2k+2$ vertices is called
$(n,k)$-{\it extendable} if for any vertex set $S$ of size $n$ and any matching
$M$ of size $k$ of $G-S$, $G-S-V(M)$ contains a perfect matching. Let
$\varepsilon$ be a small positive constant, $b(G)$ and $t(G)$ be the binding
number and toughness of a graph $G$. The two main theorems of this paper are:
for every graph $G$ with sufficiently large order, 1) if $b(G)\geq
4/3+\varepsilon$, then $G$ is $E(m,n)$-extendable and also $(n,k)$-extendable;
2) if $t(G)\geq 1+\varepsilon$ and $G$ has a high connectivity, then $G$ is
$E(m,n)$-extendable and also $(n,k)$-extendable. It is worth to point out that
the binding number and toughness conditions for the existence of the general
matching extension properties are almost same as that for the existence of
perfect matchings.
Section:
Graph Theory
Ville Junnila ; Tero Laihonen ; Gabrielle Paris.
Identifying and locating-dominating codes have been widely studied in
circulant graphs of type $C_n(1,2, \ldots, r)$, which can also be viewed as
power graphs of cycles. Recently, Ghebleh and Niepel (2013) considered
identification and location-domination in the circulant graphs $C_n(1,3)$. They
showed that the smallest cardinality of a locating-dominating code in
$C_n(1,3)$ is at least $\lceil n/3 \rceil$ and at most $\lceil n/3 \rceil + 1$
for all $n \geq 9$. Moreover, they proved that the lower bound is strict when
$n \equiv 0, 1, 4 \pmod{6}$ and conjectured that the lower bound can be
increased by one for other $n$. In this paper, we prove their conjecture.
Similarly, they showed that the smallest cardinality of an identifying code in
$C_n(1,3)$ is at least $\lceil 4n/11 \rceil$ and at most $\lceil 4n/11 \rceil +
1$ for all $n \geq 11$. Furthermore, they proved that the lower bound is
attained for most of the lengths $n$ and conjectured that in the rest of the
cases the lower bound can improved by one. This conjecture is also proved in
the paper. The proofs of the conjectures are based on a novel approach which,
instead of making use of the local properties of the graphs as is usual to
identification and location-domination, also manages to take advantage of the
global properties of the codes and the underlying graphs.
Section:
Graph Theory
Michael A. Henning ; Elena Mohr ; Dieter Rautenbach.
We propose the conjecture that every tree with order $n$ at least $2$ and
total domination number $\gamma_t$ has at most
$\left(\frac{n-\frac{\gamma_t}{2}}{\frac{\gamma_t}{2}}\right)^{\frac{\gamma_t}{2}}$
minimum total dominating sets. As a relaxation of this conjecture, we show that
every forest $F$ with order $n$, no isolated vertex, and total domination
number $\gamma_t$ has at most $\min\left\{\left(8\sqrt{e}\,
\right)^{\gamma_t}\left(\frac{n-\frac{\gamma_t}{2}}{\frac{\gamma_t}{2}}\right)^{\frac{\gamma_t}{2}},
(1+\sqrt{2})^{n-\gamma_t},1.4865^n\right\}$ minimum total dominating sets.
Section:
Graph Theory
Christof Löding ; Christopher Spinrath.
We consider decision problems for relations over finite and infinite words
defined by finite automata. We prove that the equivalence problem for binary
deterministic rational relations over infinite words is undecidable in contrast
to the case of finite words, where the problem is decidable. Furthermore, we
show that it is decidable in doubly exponential time for an automatic relation
over infinite words whether it is a recognizable relation. We also revisit this
problem in the context of finite words and improve the complexity of the
decision procedure to single exponential time. The procedure is based on a
polynomial time regularity test for deterministic visibly pushdown automata,
which is a result of independent interest.
Section:
Automata, Logic and Semantics
J. Almeida ; O. Klíma.
In algebraic terms, the insertion of $n$-powers in words may be modelled at
the language level by considering the pseudovariety of ordered monoids defined
by the inequality $1\le x^n$. We compare this pseudovariety with several other
natural pseudovarieties of ordered monoids and of monoids associated with the
Burnside pseudovariety of groups defined by the identity $x^n=1$. In
particular, we are interested in determining the pseudovariety of monoids that
it generates, which can be viewed as the problem of determining the Boolean
closure of the class of regular languages closed under $n$-power insertions. We
exhibit a simple upper bound and show that it satisfies all pseudoidentities
which are provable from $1\le x^n$ in which both sides are regular elements
with respect to the upper bound.
Section:
Automata, Logic and Semantics
Bernardo M. Ábrego ; Silvia Fernández-Merchant ; Mikio Kano ; David Orden ; Pablo Pérez-Lantero ; Carlos Seara ; Javier Tejel.
We say that a finite set of red and blue points in the plane in general
position can be $K_{1,3}$-covered if the set can be partitioned into subsets of
size $4$, with $3$ points of one color and $1$ point of the other color, in
such a way that, if at each subset the fourth point is connected by
straight-line segments to the same-colored points, then the resulting set of
all segments has no crossings. We consider the following problem: Given a set
$R$ of $r$ red points and a set $B$ of $b$ blue points in the plane in general
position, how many points of $R\cup B$ can be $K_{1,3}$-covered? and we prove
the following results:
(1) If $r=3g+h$ and $b=3h+g$, for some non-negative integers $g$ and $h$,
then there are point sets $R\cup B$, like $\{1,3\}$-equitable sets (i.e.,
$r=3b$ or $b=3r$) and linearly separable sets, that can be $K_{1,3}$-covered.
(2) If $r=3g+h$, $b=3h+g$ and the points in $R\cup B$ are in convex position,
then at least $r+b-4$ points can be $K_{1,3}$-covered, and this bound is tight.
(3) There are arbitrarily large point sets $R\cup B$ in general position,
with $r=b+1$, such that at most $r+b-5$ points can be $K_{1,3}$-covered.
(4) If $b\le r\le 3b$, then at least $\frac{8}{9}(r+b-8)$ points of $R\cup B$
can be $K_{1,3}$-covered. For $r>3b$, there are too many red points and at
least $r-3b$ of them will remain uncovered in any $K_{1,3}$-covering.
Furthermore, in all the cases we provide efficient algorithms to compute the
corresponding coverings.
Section:
Combinatorics
Danilo Korze ; Aleksander Vesel.
The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest
integer $c$ such that the vertex set $V(G)$ can be partitioned into sets $X_1,
. . . , X_c$, with the condition that vertices in $X_i$ have pairwise distance
greater than $i$. In this paper, we consider the packing chromatic number of
several families of Sierpinski-type graphs. We establish the packing chromatic
numbers of generalized Sierpinski graphs $S^n_G$ where $G$ is a path or a cycle
(with exception of a cycle of length five) as well as a connected graph of
order four. Furthermore, we prove that the packing chromatic number in the
family of Sierpinski-triangle graphs $ST_4^n$ is bounded from above by 20.
Section:
Graph Theory
Sandi Klavžar ; Douglas F. Rall.
The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest
integer $k$ such that the vertex set of $G$ can be partitioned into sets $V_i$,
$i\in [k]$, where vertices in $V_i$ are pairwise at distance at least $i+1$.
Packing chromatic vertex-critical graphs, $\chi_{\rho}$-critical for short, are
introduced as the graphs $G$ for which $\chi_{\rho}(G-x) < \chi_{\rho}(G)$
holds for every vertex $x$ of $G$. If $\chi_{\rho}(G) = k$, then $G$ is
$k$-$\chi_{\rho}$-critical. It is shown that if $G$ is $\chi_{\rho}$-critical,
then the set $\{\chi_{\rho}(G) - \chi_{\rho}(G-x):\ x\in V(G)\}$ can be almost
arbitrary. The $3$-$\chi_{\rho}$-critical graphs are characterized, and
$4$-$\chi_{\rho}$-critical graphs are characterized in the case when they
contain a cycle of length at least $5$ which is not congruent to $0$ modulo
$4$. It is shown that for every integer $k\ge 2$ there exists a
$k$-$\chi_{\rho}$-critical tree and that a $k$-$\chi_{\rho}$-critical
caterpillar exists if and only if $k\le 7$. Cartesian products are also
considered and in particular it is proved that if $G$ and $H$ are
vertex-transitive graphs and ${\rm diam(G)} + {\rm diam}(H) \le
\chi_{\rho}(G)$, then $G\,\square\, H$ is $\chi_{\rho}$-critical.
Section:
Graph Theory
Geoffrey Exoo ; Jan Goedgebeur.
Let $n_g(k)$ denote the smallest order of a $k$-chromatic graph of girth at
least $g$. We consider the problem of determining $n_g(k)$ for small values of
$k$ and $g$. After giving an overview of what is known about $n_g(k)$, we
provide some new lower bounds based on exhaustive searches, and then obtain
several new upper bounds using computer algorithms for the construction of
witnesses, and for the verification of their correctness. We also present the
first examples of reasonably small order for $k = 4$ and $g > 5$. In
particular, the new bounds include: $n_4(7) \leq 77$, $26 \leq n_6(4) \leq 66$,
$30 \leq n_7(4) \leq 171$.
Section:
Graph Theory
Feodor F. Dragan ; Abdulhakeem Mohammed.
Slimness of a graph measures the local deviation of its metric from a tree
metric. In a graph $G=(V,E)$, a geodesic triangle $\bigtriangleup(x,y,z)$ with
$x, y, z\in V$ is the union $P(x,y) \cup P(x,z) \cup P(y,z)$ of three shortest
paths connecting these vertices. A geodesic triangle $\bigtriangleup(x,y,z)$ is
called $\delta$-slim if for any vertex $u\in V$ on any side $P(x,y)$ the
distance from $u$ to $P(x,z) \cup P(y,z)$ is at most $\delta$, i.e. each path
is contained in the union of the $\delta$-neighborhoods of two others. A graph
$G$ is called $\delta$-slim, if all geodesic triangles in $G$ are
$\delta$-slim. The smallest value $\delta$ for which $G$ is $\delta$-slim is
called the slimness of $G$. In this paper, using the layering partition
technique, we obtain sharp bounds on slimness of such families of graphs as (1)
graphs with cluster-diameter $\Delta(G)$ of a layering partition of $G$, (2)
graphs with tree-length $\lambda$, (3) graphs with tree-breadth $\rho$, (4)
$k$-chordal graphs, AT-free graphs and HHD-free graphs. Additionally, we show
that the slimness of every 4-chordal graph is at most 2 and characterize those
4-chordal graphs for which the slimness of every of its induced subgraph is at
most 1.
Section:
Graph Theory
C. J. Casselgren ; Petros A. Petrosyan.
Given a proper edge coloring $\varphi$ of a graph $G$, we define the palette
$S_{G}(v,\varphi)$ of a vertex $v \in V(G)$ as the set of all colors appearing
on edges incident with $v$. The palette index $\check s(G)$ of $G$ is the
minimum number of distinct palettes occurring in a proper edge coloring of $G$.
In this paper we give various upper and lower bounds on the palette index of
$G$ in terms of the vertex degrees of $G$, particularly for the case when $G$
is a bipartite graph with small vertex degrees. Some of our results concern
$(a,b)$-biregular graphs; that is, bipartite graphs where all vertices in one
part have degree $a$ and all vertices in the other part have degree $b$. We
conjecture that if $G$ is $(a,b)$-biregular, then $\check{s}(G)\leq
1+\max\{a,b\}$, and we prove that this conjecture holds for several families of
$(a,b)$-biregular graphs. Additionally, we characterize the graphs whose
palette index equals the number of vertices.
Section:
Graph Theory
Marwane Bouznif ; Julien Darlay ; Julien Moncel ; Myriam Preissmann.
In this paper we study three domination-like problems, namely identifying codes, locating-dominating codes, and locating-total-dominating codes. We are interested in finding the minimum cardinality of such codes in circular and infinite grid graphs of given height. We provide an alternate proof for already known results, as well as new results. These were obtained by a computer search based on a generic framework, that we developed earlier, for the search of a minimum labeling satisfying a pseudo-d-local property in rotagraphs.
Section:
Graph Theory
Matthew Drescher ; Guy Louchard ; Yvik Swan.
The problem of estimating the number n of distinct keys of a large collection of N data is well known in computer science. A classical algorithm is the adaptive sampling (AS). n can be estimated by R2 J , where R is the final bucket size and J is the final depth at the end of the process. Several new interesting questions can be asked about AS (some of them were suggested by P.Flajolet and popularized by J.Lumbroso). The distribution of W = log(R2 J /n) is known, we rederive this distribution in a simpler way. We provide new results on the moments of J and W. We also analyze the final cache size R distribution. We consider colored keys: assume also that among the n distinct keys, m do have color K We show how to estimate p = m n. We study keys with some multiplicity : we provide a way to estimate the total number M of some color K keys among the total number N of keys. We consider the case where we know a priori the multiplicities but not the colors. There we want to estimate the total number of keys N. An appendix is devoted to the case where the hashing function provides bits with probability different from 1/2.
Section:
Analysis of Algorithms
Christiane Frougny ; Marta Pavelka ; Edita Pelantova ; Milena Svobodova.
A positional numeration system is given by a base and by a set of digits. The
base is a real or complex number $\beta$ such that $|\beta|>1$, and the digit
set $A$ is a finite set of digits including $0$. Thus a number can be seen as a
finite or infinite string of digits. An on-line algorithm processes the input
piece-by-piece in a serial fashion. On-line arithmetic, introduced by Trivedi
and Ercegovac, is a mode of computation where operands and results flow through
arithmetic units in a digit serial manner, starting with the most significant
digit.
In this paper, we first formulate a generalized version of the on-line
algorithms for multiplication and division of Trivedi and Ercegovac for the
cases that $\beta$ is any real or complex number, and digits are real or
complex. We then define the so-called OL Property, and show that if $(\beta,
A)$ has the OL Property, then on-line multiplication and division are feasible
by the Trivedi-Ercegovac algorithms. For a real base $\beta$ and a digit set
$A$ of contiguous integers, the system $(\beta, A)$ has the OL Property if $\#
A > |\beta|$. For a complex base $\beta$ and symmetric digit set $A$ of
contiguous integers, the system $(\beta, A)$ has the OL Property if $\# A >
\beta\overline{\beta} + |\beta + \overline{\beta}|$. Provided that addition and
subtraction are realizable in parallel in the system $(\beta, A)$ and that
preprocessing of the denominator is possible, our on-line algorithms for
multiplication and […]
Section:
Discrete Algorithms
Rodrigo I. Silveira ; Bettina Speckmann ; Kevin Verbeek.
A geographic network is a graph whose vertices are restricted to lie in a
prescribed region in the plane. In this paper we begin to study the following
fundamental problem for geographic networks: can a given geographic network be
drawn without crossings? We focus on the seemingly simple setting where each
region is a vertical segment, and one wants to connect pairs of segments with a
path that lies inside the convex hull of the two segments. We prove that when
paths must be drawn as straight line segments, it is NP-complete to determine
if a crossing-free solution exists, even if all vertical segments have unit
length. In contrast, we show that when paths must be monotone curves, the
question can be answered in polynomial time. In the more general case of paths
that can have any shape, we show that the problem is polynomial under certain
assumptions.
Section:
Discrete Algorithms
Aijun Dong ; Jianliang Wu.
A graph $G$ is equitably $k$-choosable if, for any given $k$-uniform list
assignment $L$, $G$ is $L$-colorable and each color appears on at most
$\lceil\frac{|V(G)|}{k}\rceil$ vertices. A graph is equitably $k$-colorable if
the vertex set $V(G)$ can be partitioned into $k$ independent subsets $V_1$,
$V_2$, $\cdots$, $V_k$ such that $||V_i|-|V_j||\leq 1$ for $1\leq i, j\leq k$.
In this paper, we prove that if $G$ is a planar graph without chordal $4$- and
$6$-cycles, then $G$ is equitably $k$-colorable and equitably $k$-choosable
where $k\geq\max\{\Delta(G), 7\}$.
Section:
Graph Theory
Mélodie Lapointe.
A new recursive function on discrete interval exchange transformation
associated to a composition of length $r$, and the permutation $\sigma(i) = r
-i +1$ is defined. Acting on composition $c$, this recursive function counts
the number of orbits of the discrete interval exchange transformation
associated to the composition $c$. Moreover, minimal discrete interval
exchanges transformation i.e. the ones having only one orbit, are reduced to
the composition which label the root of the Raney tree. Therefore, we describe
a generalization of the Raney tree using our recursive function.
Section:
Combinatorics
Alexander Pilz.
In the Planar 3-SAT problem, we are given a 3-SAT formula together with its
incidence graph, which is planar, and are asked whether this formula is
satisfiable. Since Lichtenstein's proof that this problem is NP-complete, it
has been used as a starting point for a large number of reductions. In the
course of this research, different restrictions on the incidence graph of the
formula have been devised, for which the problem also remains hard.
In this paper, we investigate the restriction in which we require that the
incidence graph can be augmented by the edges of a Hamiltonian cycle that first
passes through all variables and then through all clauses, in a way that the
resulting graph is still planar. We show that the problem of deciding
satisfiability of a 3-SAT formula remains NP-complete even if the incidence
graph is restricted in that way and the Hamiltonian cycle is given. This
complements previous results demanding cycles only through either the variables
or clauses.
The problem remains hard for monotone formulas, as well as for instances with
exactly three distinct variables per clause. In the course of this
investigation, we show that monotone instances of Planar 3-SAT with exactly
three distinct variables per clause are always satisfiable, thus settling the
question by Darmann, Döcker, and Dorn on the complexity of this problem
variant in a surprising way.
Section:
Discrete Algorithms
Jonathan Klawitter.
The minimal number of rooted subtree prune and regraft (rSPR) operations
needed to transform one phylogenetic tree into another one induces a metric on
phylogenetic trees - the rSPR-distance. The rSPR-distance between two
phylogenetic trees $T$ and $T'$ can be characterised by a maximum agreement
forest; a forest with a minimum number of components that covers both $T$ and
$T'$. The rSPR operation has recently been generalised to phylogenetic networks
with, among others, the subnetwork prune and regraft (SNPR) operation. Here, we
introduce maximum agreement graphs as an explicit representations of
differences of two phylogenetic networks, thus generalising maximum agreement
forests. We show that maximum agreement graphs induce a metric on phylogenetic
networks - the agreement distance. While this metric does not characterise the
distances induced by SNPR and other generalisations of rSPR, we prove that it
still bounds these distances with constant factors.
Section:
Graph Theory
Konstantinos Georgiou ; George Karakostas ; Evangelos Kranakis.
We initiate the study of a new problem on searching and fetching in a
distributed environment concerning treasure-evacuation from a unit disk. A
treasure and an exit are located at unknown positions on the perimeter of a
disk and at known arc distance. A team of two robots start from the center of
the disk, and their goal is to fetch the treasure to the exit. At any time the
robots can move anywhere they choose on the disk, independently of each other,
with the same speed. A robot detects an interesting point (treasure or exit)
only if it passes over the exact location of that point. We are interested in
designing distributed algorithms that minimize the worst-case
treasure-evacuation time, i.e. the time it takes for the treasure to be
discovered and brought (fetched) to the exit by any of the robots.
The communication protocol between the robots is either wireless, where
information is shared at any time, or face-to-face (i.e. non-wireless), where
information can be shared only if the robots meet. For both models we obtain
upper bounds for fetching the treasure to the exit. Our main technical
contribution pertains to the face-to-face model. More specifically, we
demonstrate how robots can exchange information without meeting, effectively
achieving a highly efficient treasure-evacuation protocol which is minimally
affected by the lack of distant communication. Finally, we complement our
positive results above by providing a lower bound in the face-to-face model.
Section:
Distributed Computing and Networking
M. Barnabei ; F. Bonetti ; N. Castronuovo ; M. Silimbani.
It is well-known that the set $\mathbf I_n$ of involutions of the symmetric
group $\mathbf S_n$ corresponds bijectively - by the Foata map $F$ - to the set
of $n$-permutations that avoid the two vincular patterns $\underline{123},$
$\underline{132}.$ We consider a bijection $\Gamma$ from the set $\mathbf S_n$
to the set of histoires de Laguerre, namely, bicolored Motzkin paths with
labelled steps, and study its properties when restricted to $\mathbf
S_n(1\underline{23},1\underline{32}).$ In particular, we show that the set
$\mathbf S_n(\underline{123},{132})$ of permutations that avoids the
consecutive pattern $\underline{123}$ and the classical pattern $132$
corresponds via $\Gamma$ to the set of Motzkin paths, while its image under $F$
is the set of restricted involutions $\mathbf I_n(3412).$ We exploit these
results to determine the joint distribution of the statistics des and inv over
$\mathbf S_n(\underline{123},{132})$ and over $\mathbf I_n(3412).$
Moreover, we determine the distribution in these two sets of every
consecutive pattern of length three. To this aim, we use a modified version of
the well-known Goulden-Jacson cluster method.
Section:
Combinatorics
Arnaud Mary ; Yann Strozecki.
In this paper we address the problem of generating all elements obtained by
the saturation of an initial set by some operations. More precisely, we prove
that we can generate the closure of a boolean relation (a set of boolean
vectors) by polymorphisms with a polynomial delay. Therefore we can compute
with polynomial delay the closure of a family of sets by any set of "set
operations": union, intersection, symmetric difference, subsets, supersets
$\dots$). To do so, we study the $Membership_{\mathcal{F}}$ problem: for a set
of operations $\mathcal{F}$, decide whether an element belongs to the closure
by $\mathcal{F}$ of a family of elements. In the boolean case, we prove that
$Membership_{\mathcal{F}}$ is in P for any set of boolean operations
$\mathcal{F}$. When the input vectors are over a domain larger than two
elements, we prove that the generic enumeration method fails, since
$Membership_{\mathcal{F}}$ is NP-hard for some $\mathcal{F}$. We also study the
problem of generating minimal or maximal elements of closures and prove that
some of them are related to well known enumeration problems such as the
enumeration of the circuits of a matroid or the enumeration of maximal
independent sets of a hypergraph. This article improves on previous works of
the same authors.
Section:
Discrete Algorithms
Laurent Beaudou ; Richard C. Brewster.
In 2001, Erwin introduced broadcast domination in graphs. It is a variant of
classical domination where selected vertices may have different domination
powers. The minimum cost of a dominating broadcast in a graph $G$ is denoted
$\gamma_b(G)$. The dual of this problem is called multipacking: a multipacking
is a set $M$ of vertices such that for any vertex $v$ and any positive integer
$r$, the ball of radius $r$ around $v$ contains at most $r$ vertices of $M$ .
The maximum size of a multipacking in a graph $G$ is denoted mp(G). Naturally
mp(G) $\leq \gamma_b(G)$. Earlier results by Farber and by Lubiw show that
broadcast and multipacking numbers are equal for strongly chordal graphs. In
this paper, we show that all large grids (height at least 4 and width at least
7), which are far from being chordal, have their broadcast and multipacking
numbers equal.
Section:
Graph Theory
Julien Bensmail ; Thibaut Blanc ; Nathann Cohen ; Frédéric Havet ; Leonardo Rocha.
We investigate graph colouring models for the purpose of optimizing TDMA link scheduling in Wireless Networks. Inspired by the BPRN-colouring model recently introduced by Rocha and Sasaki, we introduce a new colouring model, namely the BMRN-colouring model, which can be used to model link scheduling problems where particular types of collisions must be avoided during the node transmissions. In this paper, we initiate the study of the BMRN-colouring model by providing several bounds on the minimum number of colours needed to BMRN-colour digraphs, as well as several complexity results establishing the hardness of finding optimal colourings. We also give a special focus on these considerations for planar digraph topologies, for which we provide refined results.
Section:
Graph Theory