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.     

Crown graphs and subdivision of ladders are odd graceful

A graph G of size q is odd graceful, if there is an injection φ from V(G) to {0, 1, 2, …, 2q?1} such that, when each edge xy is assigned the label or weight |f(x)?f(y)|, the resulting edge labels are {1, 3, 5, …, 2q?1}. This definition was introduced in 1991 by Gnanajothi [3], who proved that the graphs obtained by joining a single pendant edge to each vertex of C _n are odd graceful, if n is even. In this paper, we generalize Gnanajothi's result on cycles by showing that the graphs obtained by joining m pendant edges to each vertex of C _n are odd graceful if n is even. We also prove that the subdivision of ladders S(L _n ) (the graphs obtained by subdividing every edge of L _n exactly once) is odd graceful.     

Improving the panconnectedness property of locally twisted cubes

The n-dimensional locally twisted cube LTQ_n is a promising alternative to the hypercube because of its great properties. Not only is LTQ_n n-connected, but also meshes, torus, and edge-disjoint Hamiltonian cycles can embed in it. Ma and Xu [Panconnectivity of locally twisted cubes, Appl. Math. Lett. 19 (2006), pp. 681–685] investigated the panconnectivity of LTQ_n for flexible routing. In this paper, we combine panconnectivity with Hamiltonian connectedness to define Hamiltonian r-panconnectedness: a graph G of m vertices, m≥3, is Hamiltonian r-panconnected if for any three distinct vertices x, y, and z of G there exists a Hamiltonian path P of G such that P(1)=x, P(l+1)=y, and P(m)=z for every r≤l≤m?1?r, where P(i) denotes the ith vertex of P for 1≤i≤m. Then, we show that LTQ_n is Hamiltonian n-panconnected for n≥5. This property admits the path embedding via an intermediate node at any prescribed position, and our result achieves an improvement over that of Ma and Xu.     

Independent spanning trees on twisted cubes

Multiple independent spanning trees have applications to fault tolerance and data broadcasting in distributed networks. There are two versions of the n independent spanning trees conjecture. The vertex (edge) conjecture is that any n-connected (n-edge-connected) graph has n vertex-independent spanning trees (edge-independent spanning trees) rooted at an arbitrary vertex. Note that the vertex conjecture implies the edge conjecture. The vertex and edge conjectures have been confirmed only for n-connected graphs with n≤4, and they are still open for arbitrary n-connected graph when n≥5. In this paper, we confirm the vertex conjecture (and hence also the edge conjecture) for the n-dimensional twisted cube TQ_n by providing an O(NlogN) algorithm to construct n vertex-independent spanning trees rooted at any vertex, where N denotes the number of vertices in TQ_n. Moreover, all independent spanning trees rooted at an arbitrary vertex constructed by our construction method are isomorphic and the height of each tree is n+1 for any integer n≥2.     

Star graph automorphisms and disjoint Hamilton cycles

The search for edge-disjoint Hamilton cycles in star graphs is important for the design of interconnection network topologies. We define automorphisms for star graphs St _n of degree n?1, for every positive odd integer n, which yield permutations of labels for the edges of St _n taken from the set of integers between 1 and ? n/2 ?. By decomposing these permutations into permutation cycles, we are able to identify edge-disjoint Hamilton cycles that are automorphic images of a known Hamilton cycle in St _n . Our method produces a better than two-fold improvement from ? ? (n)/10 ? to ? 2? (n)/9 ?, where ? is the Euler function, for the known number of edge-disjoint Hamilton cycles in St _n for all odd integers n. For prime n, the improvement is from ? n/8 ? to ? n/5 ?, and we can extend this result to the case when n is the power of a prime greater than 7.     

Edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition-generating trees

The Cayley graphs on the symmetric group plays an important role in the study of Cayley graphs as interconnection networks. Let Cay(S_n, B) be the Cayley graphs generated by transposition-generating trees. It is known that for any F?E(Cay(S_n, B)), if |F|≤n?3 and n≥4, then there exists a hamiltonian cycle in Cay(Sn, B)?F. In this paper, we show that Cay(S_n, B)?F is bipancyclic if Cay(S_n, B) is not a star graph, for n≥4 and |F|≤n?3.     

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.     

Inverse degree and super edge-connectivity

Let G be a connected graph of order n, minimum degree δ(G) and edge connectivity λ(G). The graph G is called maximally edge-connected if λ(G)=δ(G), and super edge-connected if every minimum edge-cut consists of edges incident with a vertex of minimum degree. Define the inverse degree of G with no isolated vertices as R(G)=∑ _v∈V(G)1/d(v), where d(v) denotes the degree of the vertex v. We show that if R(G)<2+(n?2δ)/(n?δ) (n?δ?1), then G is super edge-connected. We also give an analogous result for triangle-free graphs.     

Many-to-many disjoint paths in faulty hypercubes

This paper considers the problem of many-to-many disjoint paths in the hypercube Q_n with f_v faulty vertices and f_e faulty edges, and obtains the following result. For any integer k with 1?k?n-1, any two sets S and T of k fault-free vertices in different parts, if f_v+f_e?n-k-1, then there exist k disjoint fault-free (S,T)-paths in Q_n which contains at least 2ⁿ-2f_v vertices. This result is optimal in the worst case.     

Mutually independent Hamiltonian cycles in alternating group graphs

The alternating group graph has been used as the underlying topology for many practical multicomputers, and has been extensively studied in the past. In this article, we will show that any alternating group graph AG _n , where n??3 is an integer, contains 2n?4 mutually independent Hamiltonian cycles. More specifically, let N=|V(AG _n )|, v _i ??V(AG _n ) for 1??i??N, and ??v ₁,v ₂,??,v _N ,v ₁?? be a Hamiltonian cycle of AG _n . We show that AG _n contains 2n?4 Hamiltonian cycles, denoted by $C_{l}=\langle v_{1},v_{2}^{l},\ldots,v_{N}^{l},v_{1}\rangle$ for 1??l??2n?4, such that $v_{i}^{l} \ne v_{i}^{l'}$ for all 2??i??N whenever l??l??. The result is optimal since each vertex of AG _n has exactly 2n?4 neighbors.     

On the locatic number of graphs

A vertex v of a connected graph G distinguishes a pair u, w of vertices of G if d(v, u)≠d(v, w), where d(·,·) denotes the length of a shortest path between two vertices in G. A k-partition Π={S ₁, S ₂, …, S _k } of the vertex set of G is said to be a locatic partition if for every pair of distinct vertices v and w of G, there exists a vertex s∈S _i for all 1≤i≤k that distinguishes v and w. The cardinality of a largest locatic partition is called the locatic number of G. In this paper, we study the locatic number of paths, cycles and characterize all the connected graphs of order n having locatic number n, n?1 and n?2. Some realizable results are also given in this paper.     

Informative labeling schemes for graphs

This paper introduces the notion of informative labeling schemes for arbitrary graphs. Let f(W) be a function on subsets of vertices W. An f labeling scheme labels the vertices of a weighted graph G in such a way that f(W) can be inferred (or at least approximated) efficiently for any vertex subset W of G by merely inspecting the labels of the vertices of W, without having to use any additional information sources.A number of results illustrating this notion are presented in the paper. We begin by developing f labeling schemes for three functions f over the class of n-vertex trees. The first function, SepLevel, gives the separation level of any two vertices in the tree, namely, the depth of their least common ancestor. The second, LCA, provides the least common ancestor of any two vertices. The third, Center, yields the center of any three given vertices v₁,v₂,v₃ in the tree, namely, the unique vertex z connected to them by three edge-disjoint paths. All of these three labeling schemes use O-bit labels, which is shown to be asymptotically optimal.Our main results concern the function Steiner(W), defined for weighted graphs. For any vertex subset W in the weighted graph G, Steiner(W) represents the weight of the Steiner tree spanning the vertices of W in G. Considering the class of n-vertex trees with M-bit edge weights, it is shown that for this class there exists a Steiner labeling scheme using O((M+logn)logn) bit labels, which is asymptotically optimal. It is then shown that for the class of arbitrary n-vertex graphs with M-bit edge weights, there exists an approximate-Steiner labeling scheme, providing an estimate (up to a factor of O(logn)) for the Steiner weight Steiner(W) of a given set of vertices W, using O bit labels.     

Cyclic bundle Hamiltonicity

Cyclic bundle Hamiltonicity cbH(G) of a graph G is the minimal n for which there is an automorphism α of G such that the graph bundle C _n □^α G is Hamiltonian. We define an invariant I that is related to the maximal vertex degree of spanning trees suitably involving the symmetries of G and prove cbH(G)≤I≤cbH(G)+1 for any non-trivial connected graph G.     

Bounded dilation maps of hypercubes into Cayley graphs on the symmetric group

LetG andH be graphs with |V(G)≤ |V(H)|. Iff:V(G) →V(H) is a one-to-one map, we letdilation(f) be the maximum of dist _H (f x),f(y)) over all edgesxy inG where dist _H denotes distance inH. The construction of maps fromG toH of small dilation is motivated by the problem of designing small slowdown simulations onH of algorithms that were originally designed for the networkG. LetS(n), thestar network of dimension n, be the graph whose vertices are the elements of the symmetric group of degreen, two verticesx andy being adjacent ifx o (1,i) =y for somei. That is,xy is an edge ifx andy are related by a transposition involving some fixed symbol (which we take to be 1). Also letP(n), thepancake network of dimension n, be the graph whose vertices are the elements of the symmetric group of degreen, two verticesx andy being adjacent if one can be obtained from the other by reversing some prefix. That is,xy is an edge ifx andy are related byx o (1,i(2,i-1) ⋯ ([i/2], [i/2]) =y. The star network (introduced in [AHK]) has nice symmetry properties, and its degree and diameter are sublogarithmic as functions of the number of vertices, making it compare favorably with the hypercube network. These advantages ofS(n) motivate the study of how well it can simulate other parallel computation networks, in particular, the hypercube. The concern of this paper is to construct low dilation maps of hypercube networks into star or pancake networks. Typically in such problems, there is a tradeoff between keeping the dilationsmall and simulating alarge hypercube. Our main result shows that at the cost ofO (1) dilation asn→ ∞, one can embed a hypercube of near optimum dimension into the star or pancake networksS(n) orP(n). More precisely, lettingQ (d) be the hypercube of dimensiond, our main theorem is stated below. For simplicity, we state it only in the special case when the star network dimension is a power of 2. A more general result (applying to star networks of arbitrary dimension) is obtained by a simple interpolation. This author's research was done during the Spring Semester 1991, as a visiting professor in the Department of Mathematics and Statistics at Miami University.     

Robustness of star graph network under link failure

The star graph is an attractive underlying topology for distributed systems. Robustness of the star graph under link failure model is addressed. Specifically, the minimum number of faulty links, f(n, k), that make every (n − k)-dimensional substar S_n−k faulty in an n-dimensional star network S_n, is studied. It is shown that f(n,1)=n+2. Furthermore, an upper bound is given for f(n, 2) with complexity of O(n³) which is an improvement over the straightforward upper bound of O(n⁴) derived in this paper.     

Fault-Tolerant Embedding of Pairwise Independent Hamiltonian Paths on a Faulty Hypercube with Edge Faults

A Hamiltonian path in G is a path which contains every vertex of G exactly once. Two Hamiltonian paths P ₁=〈u ₁,u ₂,…,u _n 〉 and P ₂=〈v ₁,v ₂,…,v _n 〉 of G are said to be independent if u ₁=v ₁, u _n =v _n , and u _i ≠v _i for all 1<i<n; and both are full-independent if u _i ≠v _i for all 1≤i≤n. Moreover, P ₁ and P ₂ are independent starting at u ₁, if u ₁=v ₁ and u _i ≠v _i for all 1<i≤n. A set of Hamiltonian paths {P ₁,P ₂,…,P _k } of G are pairwise independent (respectively, pairwise full-independent, pairwise independent starting at u ₁) if any two different Hamiltonian paths in the set are independent (respectively, full-independent, independent starting at u ₁). A bipartite graph G is Hamiltonian-laceable if there exists a Hamiltonian path between any two vertices from different partite sets. It is well known that an n-dimensional hypercube Q _n is bipartite with two partite sets of equal size. Let F be the set of faulty edges of Q _n . In this paper, we show the following results:

Pancyclicity and bipancyclicity of conditional faulty folded hypercubes

A graph is said to be pancyclic if it contains cycles of every length from its girth to its order inclusive; and a bipartite graph is said to be bipancyclic if it contains cycles of every even length from its girth to its order. The pancyclicity or the bipancyclicity of a given network is an important factor in determining whether the network’s topology can simulate rings of various lengths. An n-dimensional folded hypercube FQ_n is an attractive variant of an n-dimensional hypercube Q_n that is obtained by establishing some extra edges between the vertices of Q_n. FQ_n for any odd n is known to be bipartite. In this paper, we explore the pancyclicity and bipancyclicity of FQ_n. For any FQ_n (n ? 2) with at most 2n − 3 faulty edges, where each vertex is incident to at least two fault-free edges, we prove that there exists a fault-free cycle of every even length from 4 to 2ⁿ; and when n ? 2 is even, we prove there also exists a fault-free cycle of every odd length from n + 1 to 2ⁿ − 1. The result is optimal with respect to the number of faulty edges tolerated.     

Fault-tolerant edge-pancyclicity of locally twisted cubes

The n-dimensional locally twisted cube LTQ_n is a new variant of the hypercube, which possesses some properties superior to the hypercube. This paper investigates the fault-tolerant edge-pancyclicity of LTQ_n, and shows that if LTQ_n (n ? 3) contains at most n − 3 faulty vertices and/or edges then, for any fault-free edge e and any integer ? with 6 ? ? ? 2ⁿ − f_v, there is a fault-free cycle of length ? containing the edge e, where f_v is the number of faulty vertices. The result is optimal in some senses. The proof is based on the recursive structure of LTQ_n.     

On a generalized k-out-of-n system and its reliability

A consecutive-k-out-of-n system is a system with n components arranged either linearly or circularly, which fails if and only if at least k consecutive components fail. An (n,?f,?k) system further requires that the total number of failed components is less than f for the system to be working. Here we consider a more general system consisting of N modules with the ith module-composed of n _i components in parallel; the system fails if and only if there exist at least f failed components or at least k consecutive failed modules. In this paper, some formulae for the reliability of such a generalized k-out-of-n system are derived for both the linear and the circular cases. The recursive formulae established here can be easily computed. Many existing results are also shown to be special cases of the results obtained in this paper. Furthermore, we investigate some component importance properties.     

Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes

The n-dimensional hypercube network Q_n is one of the most popular interconnection networks since it has simple structure and is easy to implement. The n-dimensional locally twisted cube LTQ_n, an important variation of the hypercube, has the same number of nodes and the same number of connections per node as Q_n. One advantage of LTQ_n is that the diameter is only about half of the diameter of Q_n. Recently, some interesting properties of LTQ_n have been investigated in the literature. The presence of edge-disjoint Hamiltonian cycles provides an advantage when implementing algorithms that require a ring structure by allowing message traffic to be spread evenly across the interconnection network. The existence of two edge-disjoint Hamiltonian cycles in locally twisted cubes has remained unknown. In this paper, we prove that the locally twisted cube LTQ_n with n?4 contains two edge-disjoint Hamiltonian cycles. Based on the proof of existence, we further provide an O(n2ⁿ)-linear time algorithm to construct two edge-disjoint Hamiltonian cycles in an n-dimensional locally twisted cube LTQ_n with n?4, where LTQ_n contains 2ⁿ nodes and n2ⁿ⁻¹ edges.