An extension of the Lyndon-Schützenberger result to pseudoperiodic words

One of the particularities of information encoded as DNA strands is that a string u contains basically the same information as its Watson-Crick complement, denoted here as θ(u). Thus, any expression consisting of repetitions of u and θ(u) can be considered in some sense periodic. In this paper, we give a generalization of Lyndon and Schützenberger’s classical result about equations of the form u^l=vⁿw^m, to cases where both sides involve repetitions of words as well as their complements. Our main results show that, for such extended equations, if l?5,n,m?3, then all three words involved can be expressed in terms of a common word t and its complement θ(t). Moreover, if l?5, then n=m=3 is an optimal bound. These results are established based on a complete characterization of all possible overlaps between two expressions that involve only some word u and its complement θ(u), which is also obtained in this paper.     

Birth and growth of multicyclic components in random hypergraphs

Define an ?-component to be a connected b-uniform hypergraph with k edges and k(b−1)−? vertices. In this paper, we investigate the growth of size and complexity of connected components of a random hypergraph process. We prove that the expected number of creations of ?-components during a random hypergraph process tends to 1 as b is fixed and ? tends to infinity with the total number of vertices n while remaining ?=o(n^1/3). We also show that the expected number of vertices that ever belong to an ?-component is ∼12^1/3?^1/3n^2/3(b−1)^−1/3. We prove that the expected number of times hypertrees are swallowed by ?-components is ∼2^1/33^−1/3n^1/3?^−1/3(b−1)^−5/3. It follows that with high probability the largest ?-component during the process is of size of order O(?^1/3n^2/3(b−1)^−1/3). Our results give insight into the size of giant components inside the phase transition of random hypergraphs and generalize previous results about graphs.     

Ring embedding in faulty pancake graphs

In this paper, we consider the fault hamiltonicity and the fault hamiltonian connectivity of the pancake graph P_n. Assume that F⊆V(P_n)∪E(P_n). For n?4, we prove that P_n−F is hamiltonian if |F|?(n−3) and P_n−F is hamiltonian connected if |F|?(n−4). Moreover, all the bounds are optimal.     

The super laceability of the hypercubes

A k-containerC(u,v) of a graph G is a set of k disjoint paths joining u to v. A k-container C(u,v) is a k∗-container if every vertex of G is incident with a path in C(u,v). A bipartite graph G is k∗-laceable if there exists a k∗-container between any two vertices u, v from different partite set of G. A bipartite graph G with connectivity k is super laceable if it is i∗-laceable for all i?k. A bipartite graph G with connectivity k is f-edge fault-tolerant super laceable if G−F is i∗-laceable for any 1?i?k−f and for any edge subset F with |F|=f<k−1. In this paper, we prove that the hypercube graph Q_r is super laceable. Moreover, Q_r is f-edge fault-tolerant super laceable for any f?r−2.     

Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs

A bipartite graph G is bipancyclic if G has a cycle of length l for every even 4?l?|V(G)|. For a bipancyclic graph G and any edge e, G is edge-bipancyclic if e lies on a cycle of any even length l of G. In this paper, we show that the bubble-sort graph Bn is bipancyclic for n?4 and also show that it is edge-bipancyclic for n?5. Assume that F is a subset of E(Bn). We prove that Bn−F is bipancyclic, when n?4 and |F|?n−3. Since Bn is a (n−1)-regular graph, this result is optimal in the worst case.     

Cycles passing through a prescribed path in a hypercube with faulty edges

Let Qn denote an n-dimensional hypercube with n?2, P be a path of length h in Qn and F⊂E(Qn)\E(P). Recently, Tsai proved that if 1?h?n−1 and |F|?n−1−h, then in the graph Qn−F the path P lies on a cycle of every even length from 2h+2 to n², and P also lies on a cycle of length 2h if |F|?h−2. In this paper, we show that if 1?h?2n−3 and |F|?n−2−⌊h/2⌋, then in Qn−F the path P lies on a cycle of every even length from 2h+2 to n², and P also lies on a cycle of length 2h if P contains two edges of the same dimension or P is a shortest path and |F∩E(Qh)|?h−2, where Qh is the h-dimensional subcube containing the path P. Moreover, the upper bound 2n−3 of h is sharp and the upper bound n−2−⌊h/2⌋ of |F| is sharp for any given h with 1?h?2n−3.     

Hamiltonian properties of twisted hypercube-like networks with more faulty elements

Twisted hypercube-like networks (THLNs) are a large class of network topologies, which subsume some well-known hypercube variants. This paper is concerned with the longest cycle in an n-dimensional (n-D) THLN with up to 2n−9 faulty elements. Let G be an n-D THLN, n≥7. Let F be a subset of V(G)?E(G), |F|≤2n−9. We prove that G−F contains a Hamiltonian cycle if δ(G−F)≥2, and G−F contains a near Hamiltonian cycle if δ(G−F)≤1. Our work extends some previously known results.     

On edge connectivity of direct products of graphs

Let λ(G) be the edge connectivity of G. The direct product of graphs G and H is the graph with vertex set V(G×H)=V(G)×V(H), where two vertices (u₁,v₁) and (u₂,v₂) are adjacent in G×H if u₁u₂∈E(G) and v₁v₂∈E(H). We prove that λ(G×Kn)=min{n(n−1)λ(G),(n−1)δ(G)} for every nontrivial graph G and n?3. We also prove that for almost every pair of graphs G and H with n vertices and edge probability p, G×H is k-connected, where k=O(²(n/logn)).     

Edge-fault-tolerant diameter and bipanconnectivity of hypercubes

Let n(?3) be a given integer and . And let Qn be an n-dimensional hypercube and F⊂E(Qn), such that every vertex of the graph Qn−F is incident with at least two edges. Assume x and y are any two vertices with Hamming distance H(x,y)=h. In this paper, we obtain the following results: (1) If h?2 and |F|?min{n+h−1,2n−5}, then in Qn−F there exists an xy-path of each length l∈Ωh+2, and the upper bound n+h−1 on |F| is sharp when 2?h?n−4, and the upper bound 2n−5 on |F| is sharp when n−4?h?n−1 and h=2. (2) If |F|?2n−5, then in Qn−F there exists an xy-path of each length l∈Ωs, where s=h if n−1?h?n, and s=h+2 if n−4?h?n−2 and h?2, and s=h+4 otherwise. Hence, the diameter of the graph Qn−F is n. Our results improve some previous results.     

The spanning connectivity of folded hypercubes

A k-container of a graph G is a set of k internally disjoint paths between u and v. A k-container of G is a k∗-container if it contains all vertices of G. A graph G is k∗-connected if there exists a k∗-container between any two distinct vertices, and a bipartite graph G is k∗-laceable if there exists a k∗-container between any two vertices u and v from different partite sets of G for a given k. A k-connected graph (respectively, bipartite graph) G is f-edge fault-tolerant spanning connected (respectively, laceable) if G − F is w∗-connected for any w with 1 ? w ? k − f and for any set F of f faulty edges in G. This paper shows that the folded hypercube FQ_n is f-edge fault-tolerant spanning laceable if n(?3) is odd and f ? n − 1, and f-edge fault-tolerant spanning connected if n (?2) is even and f ? n − 2.     

Paths in Möbius cubes and crossed cubes

The Möbius cube MQn and the crossed cube CQn are two important variants of the hypercube Qn. This paper shows that for any two different vertices u and v in G∈{MQn,CQn} with n?3, there exists a uv-path of every length from dG(u,v)+2 to n²−1 except for a shortest uv-path, where dG(u,v) is the distance between u and v in G. This result improves some known results.     

Conditional fault hamiltonian connectivity of the complete graph

A path in G is a hamiltonian path if it contains all vertices of G. A graph G is hamiltonian connected if there exists a hamiltonian path between any two distinct vertices of G. The degree of a vertex u in G is the number of vertices of G adjacent to u. We denote by δ(G) the minimum degree of vertices of G. A graph G is conditional k edge-fault tolerant hamiltonian connected if G−F is hamiltonian connected for every F⊂E(G) with |F|?k and δ(G−F)?3. The conditional edge-fault tolerant hamiltonian connectivity is defined as the maximum integer k such that G is k edge-fault tolerant conditional hamiltonian connected if G is hamiltonian connected and is undefined otherwise. Let n?4. We use Kn to denote the complete graph with n vertices. In this paper, we show that for n∉{4,5,8,10}, , , , and .     

On embedding cycles into faulty dual-cubes

A dual-cube uses low-dimensional hypercubes as basic components such that keeps the main desired properties of the hypercube. Each hypercube component is referred as a cluster. A (n+1)-connected dual-cube DC(n) has ²2n+1 nodes and the number of nodes in a cluster is n². There are two classes with each class consisting of n² clusters. Each node is incident with exactly n+1 links where n is the degree of a cluster, one more link is used for connecting to a node in another cluster. In this paper, we show that every node of DC(n) lies on a cycle of every even length from 4 to ²2n+1 inclusive for n?3, that is, DC(n) is node-bipancyclic for n?3. Furthermore, we show that DC(n), n?3, is bipancyclic even if it has up to n−1 edge faults. The result is optimal with respect to the number of edge faults tolerant.     

Bandwidth on AT-free graphs

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G=(V,E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β:{1,…,∣V∣}→V such that for every edge uv∈E, ∣β⁻¹(u)−β⁻¹(v)∣≤k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)n^O(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n⋅2^O(klogk) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete.     

Improved Constructions for Non-adaptive Threshold Group Testing

The basic goal in combinatorial group testing is to identify a set of up to d defective items within a large population of size n?d using a pooling strategy. Namely, the items can be grouped together in pools, and a single measurement would reveal whether there are one or more defectives in the pool. The threshold model is a generalization of this idea where a measurement returns positive if the number of defectives in the pool reaches a fixed threshold u>0, negative if this number is no more than a fixed lower threshold ?<u, and may behave arbitrarily otherwise. We study non-adaptive threshold group testing (in a possibly noisy setting) and show that, for this problem, O(d ^g+2(logd)log(n/d)) measurements (where g:=u???1 and u is any fixed constant) suffice to identify the defectives, and also present almost matching lower bounds. This significantly improves the previously known (non-constructive) upper bound O(d ^u+1log(n/d)). Moreover, we obtain a framework for explicit construction of measurement schemes using lossless condensers. The number of measurements resulting from this scheme is ideally bounded by O(d ^g+3(logd)logn). Using state-of-the-art constructions of lossless condensers, however, we obtain explicit testing schemes with O(d ^g+3(logd)quasipoly(logn)) and O(d ^g+3+β poly(logn)) measurements, for arbitrary constant β>0.     

A study of fault tolerance in star graph

The bounds on f(n,k), the number of faulty nodes to make every (n−k)-dimensional substar Sn−k in an n-dimensional star network Sn, have been derived. The exact value for f(n,k) is determined when n is prime and k=2, or when n−2?k?n. For 2<k<n−2, a general method is presented to derive a set of faulty nodes which damage all Sn−k's in Sn.     

A fault-free Hamiltonian cycle passing through prescribed edges in a hypercube with faulty edges

In this paper, we consider the problem of a fault-free Hamiltonian cycle passing through prescribed edges in an n-dimensional hypercube Qn with some faulty edges. We obtain the following result: Let n?2, F⊂E(Qn), E₀⊂E(Qn)\F with 1?|E₀|?2n−3, |F|<n−(⌊|E₀|/2⌋+1). If the subgraph induced by E₀ is a linear forest (i.e., pairwise vertex-disjoint paths), then in the graph Qn−F all edges of E₀ lie on a Hamiltonian cycle.     

Fault-tolerant hamiltonian laceability of hypercubes

It is known that every hypercube Q_n is a bipartite graph. Assume that n?2 and F is a subset of edges with |F|?n−2. We prove that there exists a hamiltonian path in Q_n−F between any two vertices of different partite sets. Moreover, there exists a path of length 2ⁿ−2 between any two vertices of the same partite set. Assume that n?3 and F is a subset of edges with |F|?n−3. We prove that there exists a hamiltonian path in Q_n−{v}−F between any two vertices in the partite set without v. Furthermore, all bounds are tight.     

Lower bounds on the rotation distance of binary trees

The rotation distanced(S,T) between two binary trees S, T of n vertices is the minimum number of rotations to transform S into T. While it is known that d(S,T)?2n−6, a well-known conjecture states that there are trees for which this bound is sharp for any value of n?11. We are unable to prove the conjecture, but we give here some simple criteria for lower bound evaluation, leading for example to individuate some “regular” tree structures for which d(S,T)=3n/2−O(1), or d(S,T)=5n/3−O(1).     

On Word Equations in One Variable

For a word equation E of length n in one variable x occurring # _x times in E a resolution algorithm of O(n+# _x log n) time complexity is presented here. This is the best result known and for the equations that feature #_x < \fracnlogn\#_{x}<\frac{n}{\log n} it yields time complexity of O(n) which is optimal. Additionally it is proven here that the set of solutions of any one-variable word equation is either of the form F or of the form F∪(uv)⁺ u where F is a set of O(log n) words and u, v are some words such that uv is a primitive word.