Mutually independent Hamiltonian cycles in dual-cubes

The hypercube family Q _n is one of the most well-known interconnection networks in parallel computers. With Q _n , dual-cube networks, denoted by DC _n , was introduced and shown to be a (n+1)-regular, vertex symmetric graph with some fault-tolerant Hamiltonian properties. In addition, DC _n ’s are shown to be superior to Q _n ’s in many aspects. In this article, we will prove that the n-dimensional dual-cube DC _n contains n+1 mutually independent Hamiltonian cycles for n≥2. More specifically, let v _i ∈V(DC _n ) for 0≤i≤|V(DC _n )|?1 and let \(\langle v_{0},v_{1},\ldots ,v_{|V(\mathit{DC}_{n})|-1},v_{0}\rangle\) be a Hamiltonian cycle of DC _n . We prove that DC _n contains n+1 Hamiltonian cycles of the form \(\langle v_{0},v_{1}^{k},\ldots,v_{|V(\mathit{DC}_{n})|-1}^{k},v_{0}\rangle\) for 0≤k≤n, in which v _i ^k ≠v _i ^k′ whenever k≠k′. The result is optimal since each vertex of DC _n has only n+1 neighbors.     

Embedding Hamiltonian cycles in alternating group graphs under conditional fault model

In this paper, assuming that each node is incident with two or more fault-free links, we show that an n-dimensional alternating group graph can tolerate up to 4n − 13 link faults, where n ? 4, while retaining a fault-free Hamiltonian cycle. The proof is computer-assisted. The result is optimal with respect to the number of link faults tolerated. Previously, without the assumption, at most 2n − 6 link faults can be tolerated for the same problem and the same graph.     

Fault-free mutually independent Hamiltonian cycles of faulty star graphs

The star graph interconnection network has been recognized as an attractive alternative to the hypercube for its nice topological properties. Unlike previous research concerning the issue of embedding exactly one Hamiltonian cycle into an injured star network, this paper addresses the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty star network. To be precise, let SG _n denote an n-dimensional star network in which f≤n?3 edges may fail accidentally. We show that there exist (n?2?f)-mutually independent Hamiltonian cycles rooted at any vertex in SG _n if n∈{3, 4}, and there exist (n?1?f)-mutually independent Hamiltonian cycles rooted at any vertex in SG _n if n≥5.     

The construction of mutually independent Hamiltonian cycles in bubble-sort graphs

A Hamiltonian cycle C=? u ₁, u ₂, …, u _n(G), u ₁ ? with n(G)=number of vertices of G, is a cycle C(u ₁; G), where u ₁ is the beginning and ending vertex and u _i is the ith vertex in C and u _i ≠u _j for any i≠j, 1≤i, j≤n(G). A set of Hamiltonian cycles {C ₁, C ₂, …, C _k } of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B _n )=n?1 if n≥4, where B _n is the n-dimensional bubble-sort graph.     

Fault-free Hamiltonian cycles in faulty arrangement graphs

The arrangement graph A_n,k, which is a generalization of the star graph (n-k=1), presents more flexibility than the star graph in adjusting the major design parameters: number of nodes, degree, and diameter. Previously, the arrangement graph has proved Hamiltonian. In this paper, we further show that the arrangement graph remains Hamiltonian even if it is faulty. Let |F_e| and |F_v| denote the numbers of edge faults and vertex faults, respectively. We show that A_n,k is Hamiltonian when 1) (k=2 and n-k⩾4, or k⩾3 and n-k⩾4+[k/2]), and |F_e|⩽k(n-k)-2, or 2) k⩾2, n-k⩾2+[k/2], and |F_e|⩽k(n-k-3)-1, or 3) k⩾2, n-k⩾3, and |F_e |⩽k, or 4) n-k⩾3 and |F_v|⩽n-3, or 5) n-k⩾3 and |F_v|+|F_e|⩽k. Besides, for A_n,k with n-k=2, we construct a cycle of length at least 1) [n!/(n-k!)]-2 if |F_e|⩽k-1, or 2) [n!/(n-k)!]-|F_v |-2(k-1) if |F_v|⩽k-1, or 3) [n!/(n-k)!]-|F_v |-2(k-1) if |F_e|+|F_v|⩽k-1, where [n!/(n-k)!] is the number of nodes in A_n,k     

DNA physical mapping and alternating Eulerian cycles in colored graphs

Small-scale DNA physical mapping (such as the Double Digest Problem or DDP) is an important and difficult problem in computational molecular biology. When enzyme sites are modeled by a random process, the number of solutions to DDP is known to increase exponentially as the length of DNA increases. However, the overwhelming majority of solutions are very similar and can be transformed into each other by simple transformations. Recently, Schmitt and Waterman [SW] introduced equivalence classes on the set of DDP solutions and raised an open problem to completely characterize equivalent physical maps.We study the combinatorics of multiple solutions and the cassette transformations of Schmitt and Waterman. We demonstrate that the solutions to DDP are closely associated with alternating Eulerian cycles in colored graphs and study order transformations of alternating cycles. We prove that every two alternating Eulerian cycles in a bicolored graph can be transformed into each other by means of order transformations. Using this result we obtain a complete characterization of equivalent physical maps in the Schmitt-Waterman problem. It also allows us to prove Ukkonen's conjecture on word transformations preservingq-gram composition.This research was supported in part by the National Science Foundation under Grants DMS 90-05833 and CCR-93-08567 and the National Institute of Health under Grant GM-36230.     

A simple algorithm to find Hamiltonian cycles in proper interval graphs

We present an algorithm to find a Hamiltonian cycle in a proper interval graph in O(m+n) time, where m is the number of edges and n is the number of vertices in the graph. The algorithm is simpler and shorter than previous algorithms for the problem.     

Conditional matching preclusion for the alternating group graphs and split-stars

The matching preclusion number of a graph is the minimum number of edges the deletion of which results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges the deletion of which results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this article, we find this number and classify all optimal sets for the alternating group graphs, one of the most popular interconnection networks, and their companion graphs, the split-stars. Moreover, some general results on the conditional matching preclusion problems are also presented.     

A kind of conditional fault tolerance of alternating group graphs

A vertex subset F is a k-restricted vertex-cut of a connected graph G if G−F is disconnected and every vertex in G−F has at least k good neighbors in G−F. The cardinality of the minimum k-restricted vertex-cut of G is the k-restricted connectivity of G, denoted by κk(G). This parameter measures a kind of conditional fault tolerance of networks. In this paper, we show that for the n-dimensional alternating group graph AGn, κ²(AG₄)=4 and κ²(AGn)=6n−18 for n?5.     

On Hamiltonian cycles and Hamiltonian paths

A Hamiltonian cycle is a spanning cycle in a graph, i.e., a cycle through every vertex, and a Hamiltonian path is a spanning path. In this paper we present two theorems stating sufficient conditions for a graph to possess Hamiltonian cycles and Hamiltonian paths. The significance of the theorems is discussed, and it is shown that the famous Ore's theorem directly follows from our result.     

The pessimistic diagnosability of alternating group graphs under the PMC model

The process of identifying faulty processors is called the diagnosis of the system. Several diagnostic models have been proposed, the most popular is the PMC (Preparata, Metze and Chen) diagnostic model. The pessimistic diagnosis strategy is a classic strategy based on the PMC model in which isolates all faulty nodes within a set containing at most one fault-free node. A system is t/t$t/t$-diagnosable if, provided the number of faulty processors is bounded by t, all faulty processors can be isolated within a set of size at most t with at most one fault-free node mistaken as a faulty one. The pessimistic diagnosability of a system G  , denoted by _tp(G)$t_p(G)$, is the maximal number of faulty processors so that the system G   is t/t$t/t$-diagnosable. Jwo et al. [11] introduced the alternating group graph as an interconnection network topology for computing systems. The proposed graph has many advantages over hypercubes and star graphs. For example, for all alternating group graphs, every pair of vertices in the graph are connected by a Hamiltonian path and the graph can embed cycles with arbitrary length with dilation 1. In this article, we completely determine the pessimistic diagnosability of an n  -dimensional alternating group graph, denoted by _AGn${\mathit{AG}}_n$. Furthermore, _tp(_AGn)=4n−11$t_p({\mathit{AG}}_n)=4n-11$ for n≥4$n\ge 4$.     

A note on an optimal result on fault-tolerant cycle-embedding in alternating group graphs

In a recently published paper [Z.-J. Xue, S.-Y. Liu, An optimal result on fault-tolerant cycle-embedding in alternating group graphs, Inform. Process. Lett. 109 (21-22) (2009) 1197-1201], the authors showed that for a set of faulty vertices F in an n-dimensional alternating group graph AGn, AGn−F remains pancyclic if |F|≤2n−6. However, the proof of the result is flawed. We will prove the theorem again correcting the defects in the previous proof.     

A note on leader election in directed split-stars and directed alternating group graphs

A leader node is defined to be any node of the network unambiguously identified by some characteristics. In this paper, we first present a distributed algorithm for finding a leader node of a directed split-star. Moreover, an efficient self-stabilizing leader election algorithm that converges with linear rounds is proposed for directed split-stars. Actually, the distributed algorithm and the self-stabilizing algorithm are also applicable to the problem of directed alternating group graphs. As far as we know, no self-stabilizing leader election algorithm was known for the two graphs.     

Quantized consensus in Hamiltonian graphs

The main contribution of this paper is an algorithm to solve an extended version of the quantized consensus problem over networks represented by Hamiltonian graphs, i.e., graphs containing a Hamiltonian cycle, which we assume to be known in advance. Given a network of agents, we assume that a certain number of tokens should be assigned to the agents, so that the total number of tokens weighted by their sizes is the same for all the agents. The algorithm is proved to converge almost surely to a finite set containing the optimal solution. A worst case study of the expected convergence time is carried out, thus proving the efficiency of the algorithm with respect to other solutions recently presented in the literature. Moreover, the algorithm has a decentralized stop criterion once the convergence set is reached.     

On packing shortest cycles in graphs

We study the problems to find a maximum packing of shortest edge-disjoint cycles in a graph of given girth g (g-ESCP) and its vertex-disjoint analogue g-VSCP. In the case g=3, Caprara and Rizzi (2001) have shown that g-ESCP can be solved in polynomial time for graphs with maximum degree 4, but is APX-hard for graphs with maximum degree 5, while g-VSCP can be solved in polynomial time for graphs with maximum degree 3, but is APX-hard for graphs with maximum degree 4. For g∈{4,5}, we show that both problems allow polynomial time algorithms for instances with maximum degree 3, but are APX-hard for instances with maximum degree 4. For each g?6, both problems are APX-hard already for graphs with maximum degree 3.