Abstract: Let $\gamma(G)$ and $\gamma_t(G)$ denote the domination number and the totaldomination number, respectively, of a graph $G$ with no isolated vertices. Itis well-known that $\gamma_t(G) \leq 2\gamma(G)$. We provide a characterizationof a large family of graphs (including chordal graphs) satisfying $\gamma_t(G)=2\gamma(G)$, strictly generalizing the results of Henning (2001) and Hou et al.(2010), and partially answering an open question of Henning (2009). PubDate: Mon, 04 Jun 2018 10:37:11 +020

Abstract: A path in an edge-colored graph $G$ is rainbow if no two edges of it arecolored the same. The graph $G$ is rainbow-connected if there is a rainbow pathbetween every pair of vertices. If there is a rainbow shortest path betweenevery pair of vertices, the graph $G$ is strongly rainbow-connected. Theminimum number of colors needed to make $G$ rainbow-connected is known as therainbow connection number of $G$, and is denoted by $\text{rc}(G)$. Similarly,the minimum number of colors needed to make $G$ strongly rainbow-connected isknown as the strong rainbow connection number of $G$, and is denoted by$\text{src}(G)$. We prove that for every $k \geq 3$, deciding whether$\text{src}(G) \leq k$ is NP-complete for split graphs, which form a subclassof chordal graphs. Furthermore, there exists no polynomial-time algorithm forapproximating the strong rainbow connection number of an $n$-vertex split graphwith a factor of $n^{1/2-\epsilon}$ for any $\epsilon> 0$ unless P = NP. Wethen turn our attention to block graphs, which also form a subclass of chordalgraphs. We determine the strong rainbow connection number of block graphs, andshow it can be computed in linear time. Finally, we provide a polynomial-timecharacterization of bridgeless block graphs with rainbow connection number atmost 4. PubDate: Mon, 04 Jun 2018 10:30:35 +020

Abstract: Let $S$ be a set of integers. A graph G is said to have the S-property ifthere exists an S-edge-weighting $w : E(G) \rightarrow S$ such that any twoadjacent vertices have different sums of incident edge-weights. In this paperwe characterise all bridgeless bipartite graphs and all trees without the$\{0,1\}$-property. In particular this problem belongs to P for these graphswhile it is NP-complete for all graphs. PubDate: Mon, 04 Jun 2018 10:27:12 +020

Abstract: We show that the permutation complexity of the image of a Sturmian word by abinary marked morphism is $n+k$ for some constant $k$ and all lengths $n$sufficiently large. PubDate: Mon, 04 Jun 2018 10:22:33 +020

Abstract: In this paper, we characterize the sets $\mathcal{H}$ of connected graphssuch that there exists a constant $c=c(\mathcal{H})$ satisfying $\gamma (G)\leqc$ for every connected $\mathcal{H}$-free graph $G$, where $\gamma (G)$ is thedomination number of $G$. PubDate: Mon, 04 Jun 2018 10:19:22 +020

Abstract: An antimagic labelling of a graph $G$ is a bijection$f:E(G)\to\{1,\ldots,E(G)\}$ such that the sums $S_v=\sum_{e\ni v}f(e)$distinguish all vertices. A well-known conjecture of Hartsfield and Ringel(1994) is that every connected graph other than $K_2$ admits an antimagiclabelling. Recently, two sets of authors (Arumugam, Premalatha, Ba\v{c}a \&Semani\v{c}ov\'a-Fe\v{n}ov\v{c}\'ikov\'a (2017), and Bensmail, Senhaji \&Lyngsie (2017)) independently introduced the weaker notion of a local antimagiclabelling, where only adjacent vertices must be distinguished. Both sets ofauthors conjectured that any connected graph other than $K_2$ admits a localantimagic labelling. We prove this latter conjecture using the probabilisticmethod. Thus the parameter of local antimagic chromatic number, introduced byArumugam et al., is well-defined for every connected graph other than $K_2$ . PubDate: Mon, 04 Jun 2018 10:15:49 +020

Abstract: We define a weakly threshold sequence to be a degree sequence$d=(d_1,\dots,d_n)$ of a graph having the property that $\sum_{i \leq k} d_i\geq k(k-1)+\sum_{i> k} \min\{k,d_i\} - 1$ for all positive $k \leq\max\{i:d_i \geq i-1\}$. The weakly threshold graphs are the realizations ofthe weakly threshold sequences. The weakly threshold graphs properly includethe threshold graphs and satisfy pleasing extensions of many properties ofthreshold graphs. We demonstrate a majorization property of weakly thresholdsequences and an iterative construction algorithm for weakly threshold graphs,as well as a forbidden induced subgraph characterization. We conclude byexactly enumerating weakly threshold sequences and graphs. PubDate: Mon, 04 Jun 2018 10:08:17 +020

Abstract: We generalize the notion of the toggle group, as defined in [P. Cameron-D.Fon-der-Flaass '95] and further explored in [J. Striker-N. Williams '12], fromthe set of order ideals of a poset to any family of subsets of a finite set. Weprove structure theorems for certain finite generalized toggle groups, similarto the theorem of Cameron and Fon-der-Flaass in the case of order ideals. Weapply these theorems and find other results on generalized toggle groups in thefollowing settings: chains, antichains, and interval-closed sets of a poset;independent sets, vertex covers, acyclic subgraphs, and spanning subgraphs of agraph; matroids and convex geometries. We generalize rowmotion, an actionstudied on order ideals in [P. Cameron-D. Fon-der-Flaass '95] and [J.Striker-N. Williams '12], to a map we call cover-closure on closed sets of aclosure operator. We show that cover-closure is bijective if and only if theset of closed sets is isomorphic to the set of order ideals of a poset, whichimplies rowmotion is the only bijective cover-closure map. PubDate: Fri, 25 May 2018 17:04:47 +020

Abstract: A thrackle is a drawing of a graph in which each pair of edges meetsprecisely once. Conway's Thrackle Conjecture asserts that a thrackle drawing ofa graph on the plane cannot have more edges than vertices. We prove theConjecture for thrackle drawings all of whose vertices lie on the boundaries of$d \le 3$ connected domains in the complement of the drawing. We also give adetailed description of thrackle drawings corresponding to the cases when $d=2$(annular thrackles) and $d=3$ (pants thrackles). PubDate: Fri, 25 May 2018 16:59:37 +020

Abstract: A total dominating set of a graph $G=(V,E)$ is a subset $D \subseteq V$ suchthat every vertex in $V$ is adjacent to some vertex in $D$. Finding a totaldominating set of minimum size is NP-hard on planar graphs and W[2]-complete ongeneral graphs when parameterized by the solution size. By the meta-theorem ofBodlaender et al. [J. ACM, 2016], there exists a linear kernel for TotalDominating Set on graphs of bounded genus. Nevertheless, it is not clear howsuch a kernel can be effectively constructed, and how to obtain explicitreduction rules with reasonably small constants. Following the approach ofAlber et al. [J. ACM, 2004], we provide an explicit kernel for Total DominatingSet on planar graphs with at most $410k$ vertices, where $k$ is the size of thesolution. This result complements several known constructive linear kernels onplanar graphs for other domination problems such as Dominating Set, EdgeDominating Set, Efficient Dominating Set, Connected Dominating Set, or Red-BlueDominating Set. PubDate: Wed, 16 May 2018 16:19:58 +020

Abstract: Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4-regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by $in_{cc} (G)$, is the minimum cardinality of a set S ⊆ V (G) such that every vertex w ∈ V (G) \ S has two distinct neighbors u, v ∈ S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S.In this work, first we provide bounds on $in_{cc} (G)$ and its relations to other graph convexity parameters, and explore its behavior on grids. Then, we present some hardness results by showing that deciding whether $in_{cc} (G)$ ≤ k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[2]-hard in bipartite graphs when k is the parameter. As a consequence, we obtainthat $in_{cc} (G)$ cannot be approximated up to a constant factor in the classes of split graphs and bipartite graphs (unless P = N P ).On the positive side, we present polynomial-time algorithms to compute $in_{cc} (G)$ for outerplanar graphs, cobipartite graphs and interval graphs. We also present fixed-parameter tractable (FPT) algorithms to compute it for (q, q − 4)-graphs when q is the parameter and for general graphs G when parameterized either by the treewidth or the neighborhood diversity of G.Some of our hardness results and positive results are not known to hold for related graph convexities and domination problems. We hope that the design of our new reductions and polynomial-time algorithms can be helpful in order to advance in the study of related graph problems. PubDate: Mon, 07 May 2018 10:26:53 +020

Abstract: We study the number of occurrences of any fixed vincular permutation pattern.We show that this statistics on uniform random permutations is asymptoticallynormal and describe the speed of convergence. To prove this central limittheorem, we use the method of dependency graphs. The main difficulty is then toestimate the variance of our statistics. We need a lower bound on the variance,for which we introduce a recursive technique based on the law of totalvariance. PubDate: Mon, 26 Mar 2018 11:21:09 +020

Abstract: Grebinski and Kucherov (1998) and Alon et al. (2004-2005) study the problemof learning a hidden graph for some especial cases, such as hamiltonian cycle,cliques, stars, and matchings. This problem is motivated by problems inchemical reactions, molecular biology and genome sequencing. In this paper, we present a generalization of this problem. Precisely, weconsider a graph G and a subgraph H of G and we assume that G contains exactlyone defective subgraph isomorphic to H. The goal is to find the defectivesubgraph by testing whether an induced subgraph contains an edge of thedefective subgraph, with the minimum number of tests. We present an upper boundfor the number of tests to find the defective subgraph by using the symmetricand high probability variation of Lov\'asz Local Lemma. PubDate: Mon, 26 Mar 2018 11:13:44 +020

Abstract: In a rooted tree, protected nodes are neither leaves nor parents of any leaves. They have some practical motivations, e.g., in organizational schemes, security models and social-network models. Protected node profile measures the number of protected nodes with the same distance from the root in rooted trees. For no rooted tree, protected node profile has been investigated so far. Here, we present the asymptotic expectations, variances, covariance and limiting bivariate distribution of protected node profile and non-protected internal node profile in random tries, an important data structure on words in computer science. Also we investigate the fraction of these expectations asymptotically. These results are derived by the methods of analytic combinatorics such as generating functions, Mellin transform, Poissonization and depoissonization, saddle point method and singularity analysis. PubDate: Mon, 26 Mar 2018 11:04:02 +020

Abstract: We establish asymptotic bounds for the number of partitions of $[n]$ avoidinga given partition in Klazar's sense, obtaining the correct answer to within anexponential for the block case. This technique also enables us to establish ageneral lower bound. Additionally, we consider a graph theoretic restatement ofpartition avoidance problems, and propose several conjectures. PubDate: Mon, 19 Mar 2018 11:02:07 +010

Abstract: Every rational number p/q defines a rational base numeration system in whichevery integer has a unique finite representation, up to leading zeroes. Thiswork is a contribution to the study of the set of the representations ofintegers. This prefix-closed subset of the free monoid is naturally representedas a highly non-regular tree. Its nodes are the integers, its edges bear labelstaken in {0,1,...,p-1}, and its subtrees are all distinct. We associate with each subtree (or with its root n) three infinite words. Thebottom word of n is the lexicographically smallest word that is the label of abranch of the subtree. The top word of n is defined similarly. The span-word ofn is the digitwise difference between the latter and the former. First, we show that the set of all the span-words is accepted by an infiniteautomaton whose underlying graph is essentially the same as the tree itself.Second, we study the function that computes for all n the bottom wordassociated with n+1 from the one associated with n, and show that it isrealised by an infinite sequential transducer whose underlying graph is onceagain essentially the same as the tree itself. An infinite word may be interpreted as an expansion in base p/q after theradix point, hence evaluated to a real number. If T is a subtree whose root isn, then the evaluations of the labels of the branches of T form an interval of$\mathbb{R}$. The length of this interval is called the span of n and is equalto the evaluation of the span-word of n. The set of all spans is then a subsetof R and we use the preceding construction to study its topological closure. Weshow that it is an interval when p is greater than or equal to 2q-1, and aCantor set of measure zero otherwise. PubDate: Mon, 05 Mar 2018 09:53:22 +010

Abstract: The construction of the random intersection graph model is based on a randomfamily of sets. Such structures, which are derived from intersections of sets,appear in a natural manner in many applications. In this article we study theproblem of finding a Hamilton cycle in a random intersection graph. To this endwe analyse a classical algorithm for finding Hamilton cycles in random graphs(algorithm HAM) and study its efficiency on graphs from a family of randomintersection graphs (denoted here by G(n,m,p)). We prove that the thresholdfunction for the property of HAM constructing a Hamilton cycle in G(n,m,p) isthe same as the threshold function for the minimum degree at least two. Untilnow, known algorithms for finding Hamilton cycles in G(n,m,p) were designed towork in very small ranges of parameters and, unlike HAM, used the structure ofthe family of random sets. PubDate: Mon, 05 Mar 2018 09:48:23 +010

Abstract: Stanley lists the class of Dyck paths where all returns to the axis are ofodd length as one of the many objects enumerated by (shifted) Catalan numbers.By the standard bijection in this context, these special Dyck paths correspondto a class of rooted plane trees, so-called Catalan-Stanley trees. This paper investigates a deterministic growth procedure for these trees bywhich any Catalan-Stanley tree can be grown from the tree of size one aftersome number of rounds; a parameter that will be referred to as the age of thetree. Asymptotic analyses are carried out for the age of a randomCatalan-Stanley tree of given size as well as for the "speed" of the growthprocess by comparing the size of a given tree to the size of its ancestors. PubDate: Wed, 28 Feb 2018 16:37:21 +010

Abstract: We review and extend what is known about the generating functions forconsecutive pattern-avoiding permutations of length 4, 5 and beyond, and theirasymptotic behaviour. There are respectively, seven length-4 and twenty-fivelength-5 consecutive-Wilf classes. D-finite differential equations are knownfor the reciprocal of the exponential generating functions for four of thelength-4 and eight of the length-5 classes. We give the solutions of some ofthese ODEs. An unsolved functional equation is known for one more class oflength-4, length-5 and beyond. We give the solution of this functionalequation, and use it to show that the solution is not D-finite. For threefurther length-5 c-Wilf classes we give recurrences for two and adifferential-functional equation for a third. For a fourth class we find a newalgebraic solution. We give a polynomial-time algorithm to generate thecoefficients of the generating functions which is faster than existingalgorithms, and use this to (a) calculate the asymptotics for all classes oflength 4 and length 5 to significantly greater precision than previously, and(b) use these extended series to search, unsuccessfully, for D-finite solutionsfor the unsolved classes, leading us to conjecture that the solutions are notD-finite. We have also searched, unsuccessfully, for differentially algebraicsolutions. PubDate: Mon, 26 Feb 2018 10:53:53 +010

Abstract: Two mesh patterns are coincident if they are avoided by the same set ofpermutations, and are Wilf-equivalent if they have the same number of avoidersof each length. We provide sufficient conditions for coincidence of meshpatterns, when only permutations also avoiding a longer classical pattern areconsidered. Using these conditions we completely classify coincidences betweenfamilies containing a mesh pattern of length 2 and a classical pattern oflength 3. Furthermore, we completely Wilf-classify mesh patterns of length 2inside the class of 231-avoiding permutations. PubDate: Fri, 09 Feb 2018 10:58:50 +010

Abstract: We consolidate what is currently known about packing densities of 4-pointpermutations and in the process improve the lower bounds for the packingdensities of 1324 and 1342. We also provide rigorous upper bounds for thepacking densities of 1324, 1342, and 2413. All our bounds are within $10^{-4}$of the true packing densities. Together with the known bounds, this gives us afairly complete picture of all 4-point packing densities. We also provide newupper bounds for several small permutations of length at least five. Our maintool for the upper bounds is the framework of flag algebras introduced byRazborov in 2007. PubDate: Tue, 06 Feb 2018 17:39:16 +010

Abstract: We examine $t$-colourings of oriented graphs in which, for a fixed integer $k\geq 1$, vertices joined by a directed path of length at most $k$ must beassigned different colours. A homomorphism model that extends the ideas ofSherk for the case $k=2$ is described. Dichotomy theorems for the complexity ofthe problem of deciding, for fixed $k$ and $t$, whether there exists such a$t$-colouring are proved. PubDate: Thu, 01 Feb 2018 14:42:05 +010

Abstract: The goal of this paper is to prove that several variants of deciding whethera poset can be (weakly) embedded into a small Boolean lattice, or to a fewconsecutive levels of a Boolean lattice, are NP-complete, answering a questionof Griggs and of Patkos. As an equivalent reformulation of one of theseproblems, we also derive that it is NP-complete to decide whether a given graphcan be embedded to the two middle levels of some hypercube. PubDate: Wed, 24 Jan 2018 14:06:55 +010

Abstract: Matchings are frequently used to model RNA secondary structures; however, notall matchings can be realized as RNA motifs. One class of matchings, called theL $\&$ P matchings, is the most restrictive model for RNA secondary structuresin the Largest Hairpin Family (LHF). The L $\&$ P matchings were enumerated in$2015$ by Jefferson, and they are equinumerous with the set ofnesting-similarity classes of matchings, enumerated by Klazar. We provide abijection between these two sets. This bijection preserves noncrossingmatchings, and preserves the sequence obtained reading left to right of whetheran edge begins or ends at that vertex. PubDate: Mon, 22 Jan 2018 08:55:56 +010

Abstract: The Erd\H{o}s-P\'osa property relates parameters of covering and packing ofcombinatorial structures and has been mostly studied in the setting ofundirected graphs. In this note, we use results of Chudnovsky, Fradkin, Kim,and Seymour to show that, for every directed graph $H$ (resp.strongly-connected directed graph $H$), the class of directed graphs thatcontain $H$ as a strong minor (resp. butterfly minor, topological minor) hasthe vertex-Erd\H{o}s-P\'osa property in the class of tournaments. We also provethat if $H$ is a strongly-connected directed graph, the class of directedgraphs containing $H$ as an immersion has the edge-Erd\H{o}s-P\'osa property inthe class of tournaments. PubDate: Wed, 17 Jan 2018 09:38:58 +010

Abstract: We introduce a natural variant of the parallel chip-firing game, called thediffusion game. Chips are initially assigned to vertices of a graph. At everystep, all vertices simultaneously send one chip to each neighbour with fewerchips. As the dynamics of the parallel chip-firing game occur on a finite setthe process is inherently periodic. However the diffusion game is not obviouslyperiodic: even if $2 E(G) $ chips are assigned to vertices of graph G, theremay exist time steps where some vertices have a negative number of chips. Weinvestigate the process, prove periodicity for a number of graph classes, andpose some questions for future research. PubDate: Wed, 17 Jan 2018 09:30:10 +010

Abstract: In connection with Fulkerson's conjecture on cycle covers, Fan and Raspaudproposed a weaker conjecture: For every bridgeless cubic graph $G$, there arethree perfect matchings $M_1$, $M_2$, and $M_3$ such that $M_1\cap M_2 \capM_3=\emptyset$. We call the property specified in this conjecture the threematching intersection property (and 3PM property for short). We study thisproperty on matching covered graphs. The main results are a necessary andsufficient condition and its applications to characterization of specialgraphs, such as the Halin graphs and 4-regular graphs. PubDate: Mon, 15 Jan 2018 11:43:15 +010

Abstract: We study the computational complexity of several problems connected withfinding a maximal distance-$k$ matching of minimum cardinality or minimumweight in a given graph. We introduce the class of $k$-equimatchable graphswhich is an edge analogue of $k$-equipackable graphs. We prove that therecognition of $k$-equimatchable graphs is co-NP-complete for any fixed $k \ge2$. We provide a simple characterization for the class of strongly chordalgraphs with equal $k$-packing and $k$-domination numbers. We also prove thatfor any fixed integer $\ell \ge 1$ the problem of finding a minimum weightmaximal distance-$2\ell$ matching and the problem of finding a minimum weight$(2 \ell - 1)$-independent dominating set cannot be approximated in polynomialtime in chordal graphs within a factor of $\delta \ln V(G) $ unless$\mathrm{P} = \mathrm{NP}$, where $\delta$ is a fixed constant (therebyimproving the NP-hardness result of Chang for the independent domination case).Finally, we show the NP-hardness of the minimum maximal induced matching andindependent dominating set problems in large-girth planar graphs. PubDate: Thu, 11 Jan 2018 14:10:17 +010

Abstract: Given a tree and a set P of non-trivial simple paths on it, VPT(P) is the VPTgraph (i.e. the vertex intersection graph) of the paths P, and EPT(P) is theEPT graph (i.e. the edge intersection graph) of P. These graphs have beenextensively studied in the literature. Given two (edge) intersecting paths in agraph, their split vertices is the set of vertices having degree at least 3 intheir union. A pair of (edge) intersecting paths is termed non-splitting ifthey do not have split vertices (namely if their union is a path). We definethe graph ENPT(P) of edge intersecting non-splitting paths of a tree, termedthe ENPT graph, as the graph having a vertex for each path in P, and an edgebetween every pair of vertices representing two paths that are bothedge-intersecting and non-splitting. A graph G is an ENPT graph if there is atree T and a set of paths P of T such that G=ENPT(P), and we say that isa representation of G. Our goal is to characterize the representation of chordless ENPT cycles(holes). To achieve this goal, we first assume that the EPT graph induced bythe vertices of an ENPT hole is given. In [2] we introduce three assumptions(P1), (P2), (P3) defined on EPT, ENPT pairs of graphs. In the same study, wedefine two problems HamiltonianPairRec, P3-HamiltonianPairRec and characterizethe representations of ENPT holes that satisfy (P1), (P2), (P3). In this work, we continue our work by relaxing these three assumptions one byone. We characterize the representations of ENPT holes satisfying (P3) byproviding a polynomial-time algorithm to solve P3-HamiltonianPairRec. We alsoshow that there does not exist a polynomial-time algorithm to solveHamiltonianPairRec, unless P=NP. PubDate: Thu, 11 Jan 2018 13:36:58 +010

Abstract: We study the following problem: Given $k$ paths that share the same vertex set, is there a simultaneous geometric embedding of these paths such that each individual drawing is monotone in some direction' We prove that for any dimension $d\geq 2$, there is a set of $d + 1$ paths that does not admit a monotone simultaneous geometric embedding. PubDate: Fri, 05 Jan 2018 11:41:38 +010