Disjoint Hamilton cycles in the star graph

In 1987, Akers, Harel and Krishnamurthy proposed the star graph Σ(n) as a new topology for interconnection networks. Hamiltonian properties of these graphs have been investigated by several authors. In this paper, we prove that Σ(n) contains ⌊n/8⌋ pairwise edge-disjoint Hamilton cycles when n is prime, and Ω(n/loglogn) such cycles for arbitrary n.     

Restricted compositions and permutations: From old to new Gray codes

Any Gray code for a set of combinatorial objects defines a total order relation on this set: x is less than y if and only if y occurs after x in the Gray code list. Let ? denote the order relation induced by the classical Gray code for the product set (the natural extension of the Binary Reflected Gray Code to k-ary tuples). The restriction of ? to the set of compositions and bounded compositions gives known Gray codes for those sets. Here we show that ? restricted to the set of bounded compositions of an interval yields still a Gray code. An n-composition of an interval is an n-tuple of integers whose sum lies between two integers; and the set of bounded n-compositions of an interval simultaneously generalizes product set and compositions of an integer, and so ? put under a single roof all these Gray codes.As a byproduct we obtain Gray codes for permutations with a number of inversions lying between two integers, and with even/odd number of inversions or cycles. Such particular classes of permutations are used to solve some computational difficult problems.     

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.     

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.     

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.     

Component connectivity of generalized Petersen graphs

Let G be a simple non-complete graph of order n. The r-component edge connectivity of G denoted as λ_r (G) is the minimum number of edges that must be removed from G in order to obtain a graph with (at least) r connected components. The concept of r-component edge connectivity generalizes that of edge connectivity by taking into account the number of components of the resulting graph. In this paper we establish bounds of the r component edge connectivity of an important family of interconnection network models, the generalized Petersen graphs GP(n, k) in which n and k are relatively prime integers.     

Some results on graphs without long induced paths

Many NP-hard graph problems remain difficult on P_k-free graphs for certain values of k. Our goal is to distinguish subclasses of P_k-free graphs where several important graph problems can be solved in polynomial time. In particular, we show that the independent set problem is polynomial-time solvable in the class of (P_k,K_1,n)-free graphs for any positive integers k and n, thereby generalizing several known results.     

The n-tangle of odd n qubits

Coffman et al. presented the 3-tangle of three qubits in Phys Rev A 61, 052306 (2000). Wong and Christensen (Phys Rev A 63, 044301, 2001) extended the standard form of the 3-tangle to even number of qubits, known as n-tangle. In this paper, we propose a generalization of the standard form of the 3-tangle to any odd n-qubit pure states and call it the n-tangle of odd n qubits. We show that the n-tangle of odd n qubits is invariant under permutations of the qubits, and is an entanglement monotone. The n-tangle of odd n qubits can be considered as a natural entanglement measure of any odd n-qubit pure states, and used for stochastic local operations and classical communication classification.     

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.     

Random Walks,Bisections and Gossiping in Circulant Graphs

Circulant graphs are regular graphs based on Cayley graphs defined on the Abelian group \(\mathbb{Z}_{n}\) . They are popular network topologies that arise in distributed computing. Using number theoretical tools, we first prove two main results for random directed k-regular circulant graphs with n vertices, when n is sufficiently large and k is fixed. First, for any fixed ε>0, n=p prime and L≥p ^1/k (logp)^1+1/k+ε , walks of length at most L terminate at every vertex with asymptotically the same probability. Second, for any n, there is a polynomial time algorithm that for almost all undirected 2r-regular circulant graphs finds a vertex bisector and an edge bisector, both of size less than n ^1?1/r+o(1). We then prove that the latter result also holds for all (rather than for almost all) 2r-regular circulant graphs with n=p, prime, vertices, while, in general, it does not hold for composite n. Using the bisection results, we provide lower bounds on the number of rounds required by any gossiping algorithms for any n. We introduce generic distributed algorithms to solve the gossip problem in any circulant graphs. We illustrate the efficiency of these algorithms by giving nearly matching upper bounds of the number of rounds required by these algorithms in the vertex-disjoint and the edge-disjoint paths communication models in particular circulant graphs.     

Hardness and approximation results for packing steiner trees

We study approximation algorithms and hardness of approximation for several versions of the problem of packing Steiner trees. For packing edge-disjoint Steiner trees of undirected graphs, we show APX-hardness for four terminals. For packing Steiner-node-disjoint Steiner trees of undirected graphs, we show a logarithmic hardness result, and give an approximation guarantee ofO (√n logn), wheren denotes the number of nodes. For the directed setting (packing edge-disjoint Steiner trees of directed graphs), we show a hardness result of Θ(m ^1/3/−ɛ) and give an approximation guarantee ofO(m ^1/2/+ɛ), wherem denotes the number of edges. We have similar results for packing Steiner-node-disjoint priority Steiner trees of undirected graphs. Supported by NSERC Grant No. OGP0138432. Supported by an NSERC postdoctoral fellowship, Department of Combinatorics and Optimization at University of Waterloo, and a University start-up fund at University of Alberta.     

Independence and k-domination in graphs

A subset S of vertices of a graph G is k-dominating if every vertex not in S has at least k neighbours in S. The k-domination number γ _k (G) is the minimum cardinality of a k-dominating set of G, and α(G) denotes the cardinality of a maximum independent set of G. Brook's well-known bound for the chromatic number χ and the inequality α(G)≥n(G)/χ(G) for a graph G imply that α(G)≥n(G)/Δ(G) when G is non-regular and α(G)≥n(G)/(Δ(G)+1) otherwise. In this paper, we present a new proof of this property and derive some bounds on γ _k (G). In particular, we show that, if G is connected with δ(G)≥k then γ _k (G)≤(Δ(G)?1)α(G) with the exception of G being a cycle of odd length or the complete graph of order k+1. Finally, we characterize the connected non-regular graphs G satisfying equality in these bounds and present a conjecture for the regular case.     

One-to-one communication in twisted cubes under restricted connectivity

The dimensions of twisted cubes are only limited to odd integers. In this paper, we first extend the dimensions of twisted cubes to all positive integers. Then, we introduce the concept of the restricted faulty set into twisted cubes. We further prove that under the condition that each node of the n-dimensional twisted cube TQ _n has at least one fault-free neighbor, its restricted connectivity is 2n − 2, which is almost twice as that of TQ _n under the condition of arbitrary faulty nodes, the same as that of the n-dimensional hypercube. Moreover, we provide an O(NlogN) fault-free unicast algorithm and simulations result of the expected length of the fault-free path obtained by our algorithm, where N denotes the node number of TQ _n . Finally, we propose a polynomial algorithm to check whether the faulty node set satisfies the condition that each node of the n-dimensional twisted cube TQ _n has at least one fault-free neighbor.     

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.     

Finding Edge-Disjoint Paths in Partial k -Trees

For a given graph G and p pairs (s _i ,t _i ) , , of vertices in G , the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P _i , , connecting s _i and t _i . Many combinatorial problems can be efficiently solved for partial k -trees (graphs of treewidth bounded by a fixed integer k ), but the edge-disjoint paths problem is NP-complete even for partial 3 -trees. This paper gives two algorithms for the edge-disjoint paths problem on partial k -trees. The first one solves the problem for any partial k -tree G and runs in polynomial time if p=O( log n) and in linear time if p=O(1) , where n is the number of vertices in G . The second one solves the problem under some restriction on the location of terminal pairs even if . Received January 21, 1977; revised September 19, 1997.     

AN ALGORITHM FOR FINDING ALL FUNCTIONS EMBEDDED IN A RELATION

The problem is posed: find an algorithm which for any given n-dimensional relation R ? A₁ × A₂ × ? × A_n, defined on a set family A = { A₁, A₂, ?, A_nrcub;, n = 1,2, ?, determines all functional dependences between disjoint subsets of A which are embedded in R. A solution algorithm is presented, a theorem is proved that allows a simplification in the algorithm, and an efficient computer implementation (available through the General Systems Depository) is demonstrated.     

A new matrix approach to real FFTs and convolutions of length 2<Superscript><Emphasis Type="Italic">k</Emphasis></Superscript>

A new matrix, scaled odd tail, SOT, is introduced. This new matrix is used to derive real and complex FFT algorithms for lengths n = 2 ^k . A compromise is reached between Fourier transform and polynomial transform methods for computing the action of cyclic convolutions. Both of these methods lead to arithmetic operation counts that are better than previously published results. A minor improvement is also demonstrated that enables us to compute the actions of Fermat prime order FFTs in fewer additions than previously available algorithms.     

Design and analysis of the rotational binary graph as an alternative to hypercube and Torus

Network cost is equal to degree?×?diameter and is one of the important measurements when evaluating graphs. Torus and hypercube are very well-known graphs. When these graphs expand, a Torus has an advantage in that its degree does not increase. A hypercube has a shorter diameter than that of other graphs, because when the graph expands, the diameter increases by 1. Hypercube Q_n has 2ⁿ nodes, and its diameter is n. We propose the rotational binary graph (RBG), which has the advantages of both hypercube and Torus. RBG_n has 2ⁿ nodes and a degree of 4. The diameter of RBG_n would be 1.5n?+?1. In this paper, we first examine the topology properties of RBG. Second, we construct a binary spanning tree in RBG. Third, we compare other graphs to RBG considering network cost specifically. Fourth, we suggest a broadcast algorithm with a time complexity of 2n???2. Finally, we prove that RBG_n embedded into hypercube Q_n results in dilation n, and expansion 1, and congestion 7.

     

ON MAX CUT IN CUBIC GRAPHS

Abstract

This paper is concerned with the maximum cut problem in parallel on cubic graphs. New theoretical results characterizing the cardinality of the cut are presented. These results make it possible to design a simple combinatorial O(log n) time parallel algorithm, running on a CRCW P-RAM with O(n) processors. The approximation ratio achieved by the algorithm is 1·3 and improves the best known parallel approximation ratio, i.e. 2, in the special class of cubic graphs. The algorithm also guarantees that the size of the returned cut is at least ((9g ?3)/8?g)n, where g is the odd girth of the input graph. Experimental results round off the paper, showing that the solutions obtained in practice are likely to be much better than the theoretical lower bound.