An approximation algorithm for sorting by reversals and transpositions

Genome rearrangement algorithms are powerful tools to analyze gene orders in molecular evolution. Analysis of genomes evolving by reversals and transpositions leads to a combinatorial problem of sorting by reversals and transpositions, the problem of finding a shortest sequence of reversals and transpositions that sorts one genome into the other. In this paper we present a 2k-approximation algorithm for sorting by reversals and transpositions for unsigned permutations where k is the approximation ratio of the algorithm used for cycle decomposition. For the best known value of k our approximation ratio becomes 2.8386+δ for any δ>0. We also derive a lower bound on reversal and transposition distance of an unsigned permutation.     

Edge-bipancyclicity of a hypercube with faulty vertices and edges

A bipartite graph G=(V,E) is said to be bipancyclic if it contains a cycle of every even length from 4 to |V|. Furthermore, a bipancyclic G is said to be edge-bipancyclic if every edge of G lies on a cycle of every even length. Let F_v (respectively, F_e) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Q_n. In this paper, we show that every edge of Q_n-F_v-F_e lies on a cycle of every even length from 4 to 2ⁿ-2|F_v| even if |F_v|+|F_e|?n-2, where n?3. Since Q_n is bipartite of equal-size partite sets and is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free cycle obtained are worst-case optimal.     

Note on cycle double covers of graphs

Kriesell [M. Kriesell, Contractions, cycle double covers and cyclic colorings in locally connected graphs, J. Combin. Theory Ser. B 96 (2006) 881-900] proved the cycle double cover conjecture for locally connected graphs. In this note, we give much shorter proofs for two stronger results.     

The Euclidean dimension of the join of two cycles

The Euclidean dimension of a graph G is the smallest integer p such that the vertices of G can be represented by points in the Euclidean space R^p with two points being 1 unit distance apart if and only if they represent adjacent vertices. We show that dim(C_m+C_n)=5 except that dim(C₄+C₄)=4, dim(C₅+C₅)=4, and dim(C₆+C₆)=6.     

On deletions of largest bonds in graphs

A well-known conjecture of Scott Smith is that any two distinct longest cycles of a k-connected graph must meet in at least k vertices when k≥2. We provide a dual version of this conjecture for two distinct largest bonds in a graph. This dual conjecture is established for k?6.     

Cycles of the second kind for uncertain pendulum-like systems with several nonlinearities

The existence of cycles of the second kind was considered for uncertain pendulum-like systems with several nonlinearities. On the basis of the Kalman–Yakubovich–Popov (KYP) lemma, linear matrix inequality (LMI) conditions guaranteeing the existence of cycles of the second kind for such nonlinear systems under parameter uncertainties are established. By virtue of these results, an interesting conclusion is reached: that the synthesis problem ensuring the existence of cycles of the second kind for such an uncertain nonlinear system can be converted into a synthesis problem for a system without uncertainties. A concrete application to a synchronous machine demonstrates the validity of the proposed approach.     

Graphical approach for complex PSA cycle scheduling

A simple graphical approach for complex pressure swing adsorption (PSA) cycle scheduling has been developed. This new methodology involves a priori specifying the cycle steps, their sequence, and the number of beds, and then following a systematic procedure that requires filling in a 2-D grid based on a few simple rules, some heuristics and some experience. The outcome or solution is a grid comprised of columns that represent the total cycle time, rows that represent the total number of beds, and cells that represent the duration of each cycle step, i.e., the complete cycle schedule. This new approach has been tested successfully against several cycle schedules taken from the literature, including a two-bed four-step Skarstrom cycle, a four-bed nine-step process with two equalization steps, a nine-bed eleven-step process with three pressure equalization steps, and a six-bed thirteen-step process with four pressure equalization steps and four idle steps. This approach also revealed the existence of numerous cycle schedules for each bed and cycle step combination examined. Although it cannot identify the total number of permutations or which one is better, it does provide a very straightforward way to determine some of the possible cycle schedules of virtually any PSA process that can be conceived.     

A note on semiextensions of stable circuits

A semiextension of a circuit C in a graph G provides a possible means of finding a cycle double cover of G with C as a prescribed circuit. Recently we conjectured [E.E. García Moreno, T.R. Jensen, On semiextensions and circuit double covers, J. Combin. Theory Ser. B 97 (2007) 474-482] that if G is cubic and 2-edge-connected, then a semiextension of C in G exists. If true, this would imply several long-standing conjectures.If there is a circuit C^′ in G with C^′≠C and V(C)⊆V(C^′), then C^′ is called an extension of C, a special case of a semiextension. If there is no such circuit, then C is said to be stable in G. Hence the existence question for semiextensions is easy except for stable circuits. Not many examples of graphs with stable circuits have been published. In this note we show that the members of a particular class of stable circuits described by M. Kochol have semiextensions.     

Edge choosability of planar graphs without 5-cycles with a chord

Let G be a plane graph having no 5-cycles with a chord. If either Δ≥6, or Δ=5 and G contains no 4-cycles with a chord or no 6-cycles with a chord, then G is edge-(Δ+1)-choosable, where Δ denotes the maximum degree of G.