Search

Given a set system (also well-known as a hypergraph) H = {U, X}, where U is a set of elements and X is a set of subsets of U, an exact hitting set S is a subset of U such that each subset in X contains exactly one element in S. We refer to a set system as exactly hittable if it has an exact hitting set. In this paper, we study interval graphs which have intersection models that are exactly hittable. We refer to these interval graphs as Exactly Hittable Interval Graphs (EHIG). We present a forbidden structure characterization for EHIG. We also show that the class of proper interval graphs is a strict subclass of EHIG. Finally, we give an algorithm that runs in polynomial time to recognize graphs belonging to the class of EHIG. [ABSTRACT FROM AUTHOR]

We define a q-linear path in a hypergraph H as a sequence (e1,. . ., eL) of edges of H such that |ei nei+1| [[1, q]] and ei n ej = Ø if |i-j| > 1. In this paper, we study the connected components associated to these paths when q = k - 2 where k is the rank of H. If k = 3 then q = 1 which coincides with the well-known notion of linear path or loose path. We describe the structure of the connected components, using an algorithmic proof which shows that the connected components can be computed in polynomial time. We then mention two consequences of our algorithmic result. The first one is that deciding the winner of the Maker-Breaker game on a hypergraph of rank 3 can be done in polynomial time. The second one is that tractable cases for the NP-complete problem of "Paths Avoiding Forbidden Pairs" in a graph can be deduced from the recognition of a special type of line graph of a hypergraph. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of gossiping with interference constraint in radio ring networks. Gossiping (or total exchange information) is a protocol where each node in the network has a message and is expected to distribute its own message to every other node in the network. The gossiping problem consists in finding the minimum running time (makespan) of a gossiping protocol and algorithms that attain this makespan. We focus on the case where the transmission network is a ring network. We consider synchronous protocols where it takes one unit of time (step) to transmit a unit-length message. During one step, a node receives at most one message only through one of its two neighbors. We also suppose that, during one step, a node cannot be both a sender and a receiver (half duplex model). Moreover communication is subject to interference constraints. We use a primary node interference model where, if a node receives a message from one of its neighbors, its other neighbor cannot send at the same time. With these assumptions we completely solve the problem for ring networks. We first show lower bounds and then give gossiping algorithms which meet these lower bounds and so are optimal. The number of rounds depends on the congruences of n modulo 12. [ABSTRACT FROM AUTHOR]

The (bitwise) complement x of a binary word x is obtained by changing each 0 in x to 1 and vice versa. An antisquare is a nonempty word of the form x x. In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is (5 +√5)/2. We also study repetition thresholds for related classes, where "two" in the previous sentence is replaced by a larger number. We say a binary word is good if the only antisquares it contains are 01 and 10. We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the growth rate of the number of good words of length n and determine the repetition threshold between polynomial and exponential growth for the number of good words. [ABSTRACT FROM AUTHOR]

We generalize the familiar notion of periodicity in sequences to a new kind of pseudoperiodicity, and we prove some basic results about it. We revisit the results of a 2012 paper of Shevelev and reprove his results in a simpler and more unified manner, and provide a complete answer to one of his previously unresolved questions. We consider finding words with specific pseudoperiod and having the smallest possible critical exponent. Finally, we consider the problem of determining whether a finite word is pseudoperiodic of a given size, and show that it is NP-complete. [ABSTRACT FROM AUTHOR]

Mixed graphs have both directed and undirected edges. We consider mixed graphs that are regular in both directed and undirected degree and with given girth. Araujo-Pardo, Hern'andez-Cruz, andMontellano-Ballesteros recently established a lower bound for regular mixed graphs with directed degree one that generalizes the Moore bound. In this paper we show that, in at least one non-trivial case, their bound can be achieved. For a few other specific values of direct degree, undirected degree and girth we are able to identify graphs (mixed cages) of minimum possible order. We also obtain some fairly tight bounds for a few other cases. [ABSTRACT FROM AUTHOR]

The analysis of strings of n random variables with geometric distribution has recently attracted renewed interest: Archibald et al. consider the number of distinct adjacent pairs in geometrically distributed words. They obtain the asymptotic (n → ∞) mean of this number in the cases of different and identical pairs. In this paper we are interested in all asymptotic moments in the identical case, in the asymptotic variance in the different case and in the asymptotic distribution in both cases. We use two approaches: the first one, the probabilistic approach, leads to variances in both cases and to some conjectures on all moments in the identical case and on the distribution in both cases. The second approach, the combinatorial one, relies on multivariate pattern matching techniques, yielding exact formulas for first and second moments. We use such tools as Mellin transforms, Analytic Combinatorics, Markov Chains. [ABSTRACT FROM AUTHOR]