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.     

A new sufficient condition for Hamiltonicity of graphs

Rahman and Kaykobad proved the following theorem on Hamiltonian paths in graphs. Let G be a connected graph with n vertices. If d(u)+d(v)+δ(u,v)?n+1 for each pair of distinct non-adjacent vertices u and v in G, where δ(u,v) is the length of a shortest path between u and v in G, then G has a Hamiltonian path. It is shown that except for two families of graphs a graph is Hamiltonian if it satisfies the condition in Rahman and Kaykobad's theorem. The result obtained in this note is also an answer for a question posed by Rahman and Kaykobad.     

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 .     

Conditional edge-fault-tolerant Hamiltonicity of dual-cubes

The dual-cube is an interconnection network for linking a large number of nodes with a low node degree. It uses low-dimensional hypercubes as building blocks and keeps the main desired properties of the hypercube. A dual-cube DC(n) has n + 1 links per node where n is the degree of a cluster (n-cube), and one more link is used for connecting to a node in another cluster. In this paper, assuming each node is incident with at least two fault-free links, we show a dual-cube DC(n) contains a fault-free Hamiltonian cycle, even if it has up to 2n − 3 link faults. The result is optimal with respect to the number of tolerant edge faults.     

Hamiltonian paths and cycles passing through a prescribed path in hypercubes

Assume that P is any path in a bipartite graph G of length k with 2?k?h, G is said to be h-path bipancyclic if there exists a cycle C in G of every even length from 2k to |V(G)| such that P lies in C. In this paper, the following result is obtained: The n-dimensional hypercube Qn with n?3 is (2n−3)-path bipancyclic but is not (2n−2)-path bipancyclic, moreover, a path P of length k with 2?k?2n−3 lies in a cycle of length 2k−2 if and only if P contains two edges of the same dimension. In order to prove the above result we first show that any path of length at most 2n−1 is a subpath of a Hamiltonian path in Qn with n?2, moreover, the upper bound 2n−1 is sharp when n?4.     

Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes

A bipartite graph is bipancyclic if it contains a cycle of every even length from 4 to |V(G)| inclusive. It has been shown that Q_n is bipancyclic if and only if n?2. In this paper, we improve this result by showing that every edge of Q_n−E′ lies on a cycle of every even length from 4 to |V(G)| inclusive where E′ is a subset of E(Q_n) with |E′|?n−2. The result is proved to be optimal. To get this result, we also prove that there exists a path of length l joining any two different vertices x and y of Q_n when h(x,y)?l?|V(G)|−1 and l−h(x,y) is even where h(x,y) is the Hamming distance between x and y.     

An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs

A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to determine whether or not a graph contains a Hamiltonian cycle. The best result for the Hamiltonian cycle problem on circular-arc graphs is an O(n²logn)-time algorithm, where n is the number of vertices of the input graph. In fact, the O(n²logn)-time algorithm can be modified as a certifying algorithm although it was published before the term certifying algorithms appeared in the literature. However, whether there exists an algorithm whose time complexity is better than O(n²logn) for solving the Hamiltonian cycle problem on circular-arc graphs has been opened for two decades. In this paper, we present an O(Δn)-time certifying algorithm to solve this problem, where Δ represents the maximum degree of the input graph. The certificates provided by our algorithm can be authenticated in O(n) time.     

Binding number and Hamiltonian (g,f)-factors in graphs II

A (g, f)-factor F of a graph G is called a Hamiltonian (g, f)-factor if F contains a Hamiltonian cycle. For a subset X of V(G), let N _G (X)= gcup _x∈X N _G (x). The binding number of G is defined by bind(G)=min{| N _G (X) |/| X|| ?≠X?V(G), N _G (X)≠V(G)}. Let G be a connected graph of order n, 3≤a≤b be integers, and b≥4. Let g, f be positive integer-valued functions defined on V(G), such that a≤g(x)≤f(x)≤b for every x∈V(G). Suppose n≥(a+b?4)²/(a?2) and f(V(G)) is even, we shall prove that if bind(G)>((a+b?4)(n?1))/((a?2)n?(5/2)(a+b?4)) and for any independent set X?V(G), N _G (X)≥((b?3)n+(2a+2b?9)| X|)/(a+b?5), then G has a Hamiltonian (g, f)-factor.     

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 panpositionable panconnectedness of augmented cubes

A graph G is panconnected if, for any two distinct vertices x and y of G, it contains an [x, y]-path of length l for each integer l satisfying d_G(x, y) ? l ? ∣V(G)∣ − 1, where d_G(x, y) denotes the distance between vertices x and y in G, and V(G) denotes the vertex set of G. For insight into the concept of panconnectedness, we propose a more refined property, namely panpositionable panconnectedness. Let x, y, and z be any three distinct vertices in a graph G. Then G is said to be panpositionably panconnected if for any d_G(x, z) ? l₁ ? ∣V(G)∣ − d_G(y, z) − 1, it contains a path P such that x is the beginning vertex of P, z is the (l₁ + 1)th vertex of P, and y is the (l₁ + l₂ + 1)th vertex of P for any integer l₂ satisfying d_G(y, z) ? l₂ ? ∣V(G)∣ − l₁ − 1. The augmented cube, proposed by Choudum and Sunitha [6] to be an enhancement of the n-cube Q_n, not only retains some attractive characteristics of Q_n but also possesses many distinguishing properties of which Q_n lacks. In this paper, we investigate the panpositionable panconnectedness with respect to the class of augmented cubes. As a consequence, many topological properties related to cycle and path embedding in augmented cubes, such as pancyclicity, panconnectedness, and panpositionable Hamiltonicity, can be drawn from our results.     

On path bipancyclicity of hypercubes

Assume that P is any path in a bipartite graph G of length k with 2?k?h, G is said to be h-path bipancyclic if there exists a cycle C in G of every even length from 2k to |V(G)| such that P lies in C. Based on Lemma 5, the authors of [C.-H. Tsai, S.-Y. Jiang, Path bipancyclicity of hypercubes, Inform. Process. Lett. 101 (2007) 93-97] showed that the n-cube Qn with n?3 is (2n−4)-path bipancyclicity. In this paper, counterexamples to the lemma are given, therefore, their proof fails. And we show the following result: The n-cube Qn with n?3 is (2n−4)-path bipancyclicity but is not (2n−2)-path bipancyclicity, moreover, and a path P of length k with 2?k?2n−4 lies in a cycle of length 2k−2 if and only if P contains two edges of dimension i for some i, 1?i?n. We conjecture that if 2n−4 is replaced by 2n−3, then the above result also holds.     

Hamiltonian laceability of bubble-sort graphs with edge faults

It is known that the n-dimensional bubble-sort graph B_n is bipartite, (n − 1)-regular, and has n! vertices. We first show that, for any vertex v, B_n − v has a hamiltonian path between any two vertices in the same partite set without v. Let F be a subset of edges of B_n. We next show that B_n − F has a hamiltonian path between any two vertices of different partite sets if ∣F∣ is at most n − 3. Then we also prove that B_n − F has a path of length n! − 2 between any pair of vertices in the same partite set.     

Hamiltonian paths and cycles with prescribed edges in the 3-ary n-cube

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. Given a set P of at most 2n − 2 (n ? 2) prescribed edges and two vertices u and v, we show that the 3-ary n-cube contains a Hamiltonian path between u and v passing through all edges of P if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as end-vertices. As an immediate result, the 3-ary n-cube contains a Hamiltonian cycle passing through a set P of at most 2n − 1 prescribed edges if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths.     

Fault-free Hamiltonian cycles in crossed cubes with conditional link faults

The crossed cube, which is a variation of the hypercube, possesses some properties superior to the hypercube. In this paper, assuming that each node is incident with at least two fault-free links, we show that an n-dimensional crossed cube contains a fault-free Hamiltonian cycle, even if there are up to 2n − 5 link faults. The result is optimal with respect to the number of link faults tolerated. We also verify that the assumption is practically meaningful by evaluating its occurrence probability, which is very close to 1.     

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.     

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.     

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.     

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)).     

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.     

Vertex fault tolerance of optimal-κ graphs and super-κ graphs

A connected graph G is optimal-κ if κ(G)=δ(G). It is super-κ if every minimum vertex cut isolates a vertex. An optimal-κ graph G is m-optimal-κ if for any vertex set S⊆V(G) with |S|?m, G−S is still optimal-κ. We define the vertex fault tolerance with respect to optimal-κ, denoted by Oκ(G), as the maximum integer m such that G is m-optimal-κ. The concept of vertex fault tolerance with respect to super-κ, denoted by Sκ(G), is defined in a similar way. In this paper, we show that min{κ₁(G)−δ(G),δ(G)−1}?Oκ(G)?δ(G)−1 and min{κ₁(G)−δ(G)−1,δ(G)−1}?Sκ(G)?δ(G)−1, where κ₁(G) is the 1-extra connectivity of G. Furthermore, when the graph is triangle free, more refined lower bound can be derived for Oκ(G).