Vol. 15 no. 2

1. Descent variation of samples of geometric random variables

Brennan, Charlotte ; Knopfmacher, Arnold.
In this paper, we consider random words ω1ω2ω3⋯ωn of length n, where the letters ωi ∈ℕ are independently generated with a geometric probability such that Pωi=k=pqk-1 where p+q=1 . We have a descent at position i whenever ωi+1 < ωi. The size of such a descent is ωi-ωi+1 and the descent variation […]
Section: Combinatorics

2. On the enumeration of d-minimal permutations

Bouvel, Mathilde ; Ferrari, Luca.
We suggest an approach for the enumeration of minimal permutations having d descents which uses skew Young tableaux. We succeed in finding a general expression for the number of such permutations in terms of (several) sums of determinants. We then generalize the class of skew Young tableaux under […]

3. Operations on partially ordered sets and rational identities of type A

Boussicault, Adrien.
We consider the family of rational functions ψw= ∏( xwi - xwi+1 )-1 indexed by words with no repetition. We study the combinatorics of the sums ΨP of the functions ψw when w describes the linear extensions of a given poset P. In particular, we point out the connexions between some transformations on […]
Section: Combinatorics

4. Efficient repeat finding in sets of strings via suffix arrays

Barenbaum, Pablo ; Becher, Verónica ; Deymonnaz, Alejandro ; Halsband, Melisa ; Heiber, Pablo Ariel.
We consider two repeat finding problems relative to sets of strings: (a) Find the largest substrings that occur in every string of a given set; (b) Find the maximal repeats in a given string that occur in no string of a given set. Our solutions are based on the suffix array construction, requiring […]
Section: Discrete Algorithms

5. Bipartite powers of k-chordal graphs

Chandran, Sunil,  ; Mathew, Rogers.
Let k be an integer and k ≥3. A graph G is k-chordal if G does not have an induced cycle of length greater than k. From the definition it is clear that 3-chordal graphs are precisely the class of chordal graphs. Duchet proved that, for every positive integer m, if Gm is chordal then so is Gm+2. […]
Section: Graph Theory

6. Connectivity for line-of-sight networks in higher dimensions

Devroye, Luc ; Farczadi, Linda.
Let T be a d-dimensional toroidal grid of n^d points. For a given range parameter ω, and a positive integer k ≤q d, we say that two points in T are mutually visible if they differ in at most k coordinates and are a distance at most ω apart, where distance is measured using the \ellₚ norm. We obtain […]
Section: Analysis of Algorithms

7. Improved bounds on the crossing number of butterfly network

Manuel, Paul D. ; Rajan, Bharati ; Rajasingh, Indra ; Beulah, P. Vasanthi.
We draw the r-dimensional butterfly network with 1 / 44r+O(r2r) crossings which improves the previous estimate given by Cimikowski (1996). We also give a lower bound which matches the upper bound obtained in this paper.
Section: Graph Theory

8. A stronger recognizability condition for two-dimensional languages

Anselmo, Marcella ; Madonia, Maria.
The paper presents a condition necessarily satisfied by (tiling system) recognizable two-dimensional languages. The new recognizability condition is compared with all the other ones known in the literature (namely three conditions), once they are put in a uniform setting: they are stated as bounds […]
Section: Automata, Logic and Semantics

9. The complexity of 2-coloring and strong coloring in uniform hypergraphs of high minimum degree

Szymańska, Edyta.
In this paper we consider the problem of deciding whether a given r-uniform hypergraph H with minimum vertex degree at least c\binom|V(H)|-1r-1, or minimum degree of a pair of vertices at least c\binom|V(H)|-2r-2, has a vertex 2-coloring. Motivated by an old result of Edwards for graphs, we obtain […]
Section: Discrete Algorithms

10. Derivatives of approximate regular expressions

Champarnaud, Jean-Marc ; Jeanne, Hadrien ; Mignot, Ludovic.
Our aim is to construct a finite automaton recognizing the set of words that are at a bounded distance from some word of a given regular language. We define new regular operators, the similarity operators, based on a generalization of the notion of distance and we introduce the family of regular […]
Section: Automata, Logic and Semantics

11. Removable edges in near-bricks

Wang, Xiumei ; He, Cheng ; Lin, Yixun.
For a brick apart from a few small graphs, Lovász (1987) proposed a conjecture on the existence of an edge whose deletion results in a graph with only one brick in its tight cut decomposition. Carvalho, Lucchesi, and Murty (2002) confirmed this conjecture by showing the existence of such two edges. […]
Section: Graph Theory

12. Topological structuring of the digital plane

Šlapal, Josef.
We discuss an Alexandroff topology on ℤ2 having the property that its quotient topologies include the Khalimsky and Marcus-Wyse topologies. We introduce a further quotient topology and prove a Jordan curve theorem for it.
Section: Combinatorics

13. Probe interval graphs and probe unit interval graphs on superclasses of cographs

Bonomo, Flavia ; Durán, Guillermo ; Grippo, Luciano N. ; Safe, Martın D..
A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of […]
Section: Graph Theory

14. On-line ranking of split graphs

Borowiecki, Piotr ; Dereniowski, Dariusz.
A vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line […]
Section: Graph and Algorithms

15. A note on contracting claw-free graphs

Fiala, Jiří ; Kamiński, Marcin ; Paulusma, Daniël.
A graph containment problem is to decide whether one graph called the host graph can be modified into some other graph called the target graph by using a number of specified graph operations. We consider edge deletions, edge contractions, vertex deletions and vertex dissolutions as possible graph […]
Section: Discrete Algorithms

16. Cyclic partitions of complete nonuniform hypergraphs and complete multipartite hypergraphs

Gosselin, Shonda ; Szymański, Andrzej ; Wojda, Adam Pawel.
A \em cyclic q-partition of a hypergraph (V,E) is a partition of the edge set E of the form \F,F^θ,F^θ², \ldots, F^θ^q-1\ for some permutation θ of the vertex set V. Let Vₙ = \ 1,2,\ldots,n\. For a positive integer k, Vₙ\choose k denotes the set of all k-subsets of Vₙ. For a nonempty subset K of […]
Section: Combinatorics

17. A note on the NP-hardness of two matching problems in induced subgrids

Demange, Marc ; Ekim, Tınaz.
Given a graph, finding the maximal matching of minimum size (MMM) and the induced matching of maximum size (MIM) have been very popular research topics during the last decades. In this paper, we give new complexity results, namely the NP-hardness of MMM and MIM in induced subgrids and we point out […]
Section: Graph Theory

18. Coupon collecting and transversals of hypergraphs

Wild, Marcel ; Janson, Svante ; Wagner, Stephan ; Laurie, Dirk.
The classic Coupon-Collector Problem (CCP) is generalized. Only basic probability theory is used. Centerpiece rather is an algorithm that efficiently counts all k-element transversals of a set system.
Section: Analysis of Algorithms

19. Maximal independent sets in bipartite graphs with at least one cycle

Li, Shuchao ; Zhang, Huihui ; Zhang, Xiaoyan.
A maximal independent set is an independent set that is not a proper subset of any other independent set. Liu [J.Q. Liu, Maximal independent sets of bipartite graphs, J. Graph Theory, 17 (4) (1993) 495-507] determined the largest number of maximal independent sets among all n-vertex bipartite […]
Section: Graph Theory