A note on fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges

In the paper “Fault-free Mutually Independent Hamiltonian Cycles in Hypercubes with Faulty Edges” (J. Comb. Optim. 13:153–162, 2007), the authors claimed that an n-dimensional hypercube can be embedded with (n−1−f)-mutually independent Hamiltonian cycles when f≤n−2 faulty edges may occur accidentally. However, there are two mistakes in their proof. In this paper, we give examples to explain why the proof is deficient. Then we present a correct proof. This work was supported in part by the National Science Council of the Republic of China under Contract NSC 95-2221-E-233-002.     

On cubic 2-independent Hamiltonian connected graphs

A graph G=(V,E) is Hamiltonian connected if there exists a Hamiltonian path between any two vertices in G. Let P ₁=(u ₁,u ₂,…,u _|V|) and P ₂=(v ₁,v ₂,…,v _|V|) be any two Hamiltonian paths of G. We say that P ₁ and P ₂ are independent if u ₁=v ₁,u _|V|=v _|V|, and u _i ≠v _i for 1<i<|V|. A cubic graph G is 2-independent Hamiltonian connected if there are two independent Hamiltonian paths between any two different vertices of G. A graph G is 1-Hamiltonian if G−F is Hamiltonian for any F⊆V∪E with |F|=1. A graph G is super 3^*-connected if there exist i internal disjoint paths spanning G for i=1,2,3. It is proved that every super 3^*-connected graph is 1-Hamiltonian. In this paper, we prove that every cubic 2-independent Hamiltonian connected graph is also 1-Hamiltonian. We present some cubic 2-independent Hamiltonian connected graphs that are super 3^*-connected, some cubic 2-independent Hamiltonian connected graphs that are not super 3^*-connected, some super 3^*-connected graphs that are not 2-independent Hamiltonian connected, and some cubic 1-Hamiltonian graphs that are Hamiltonian connected but neither 2-independent Hamiltonian connected nor super 3^*-connected. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work was supported in part by the National Science Council of the Republic of China under Contract NSC 94-2213-E-233-011.     

On the equitable k *-laceability of hypercubes

Let G be a finite undirected bipartite graph. Let u, v be two vertices of G from different partite sets. A collection of k internal vertex disjoint paths joining u to v is referred as a k-container C _k (u,v). A k-container is a k ^*-container if it spans all vertices of G. We define G to be a k ^*-laceable graph if there is a k ^*-container joining any two vertices from different partite sets. A k ^*-container C _k ^*(u,v)={P ₁,…,P _k } is equitable if ||V(P _i )|−|V(P _j )||≤2 for all 1≤i,j≤k. A graph is equitably k ^*-laceable if there is an equitable k ^*-container joining any two vertices in different partite sets. Let Q _n be the n-dimensional hypercube. In this paper, we prove that the hypercube Q _n is equitably k ^*-laceable for all k≤n−4 and n≥5. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. The work of H.-M. Huang was supported in part by the National Science Council of the Republic of China under NSC94-2115-M008-013.     

One-dimensional optimal bounded-shape partitions for Schur convex sum objective functions

Consider the problem of partitioning n nonnegative numbers into p parts, where part i can be assigned n_i numbers with n_i lying in a given range. The goal is to maximize a Schur convex function F whose ith argument is the sum of numbers assigned to part i. The shape of a partition is the vector consisting of the sizes of its parts, further, a shape (without referring to a particular partition) is a vector of nonnegative integers (n₁,..., n_p) which sum to n. A partition is called size-consecutive if there is a ranking of the parts which is consistent with their sizes, and all elements in a higher-ranked part exceed all elements in the lower-ranked part. We demonstrate that one can restrict attention to size-consecutive partitions with shapes that are nonmajorized, we study these shapes, bound their numbers and develop algorithms to enumerate them. Our study extends the analysis of a previous paper by Hwang and Rothblum which discussed the above problem assuming the existence of a majorizing shape. This research is partially supported by ROC National Science grant NSC 92-2115-M-009-014.     

A study on cyclic bandwidth sum

Suppose G is a graph of p vertices. A proper labeling f of G is a one-to-one mapping f:V(G)→{1,2,…,p}. The cyclic bandwidth sum of G with respect to f is defined by CBS _f (G)=∑ _uv∈E(G)|f(v)−f(u)| _p , where |x| _p =min {|x|,p−|x|}. The cyclic bandwidth sum of G is defined by CBS(G)=min {CBS _f (G): f is a proper labeling of G}. The bandwidth sum of G with respect to f is defined by BS _f (G)=∑ _uv∈E(G)|f(v)−f(u)|. The bandwidth sum of G is defined by BS(G)=min {BS _f (G): f is a proper labeling of G}. In this paper, we give a necessary and sufficient condition for BS(G)=CBS(G), and use this to show that BS(T)=CBS(T) when T is a tree. We also find cyclic bandwidth sums of complete bipartite graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Supported in part by the National Science Council under grants NSC91-2115-M-156-001.     

Packing 5-cycles into balanced complete m-partite graphs for odd m

Let be a complete m-partite graph with partite sets of sizes n ₁,n ₂,…,n _m . A complete m-partite graph is balanced if each partite set has n vertices. We denote this complete m-partite graph by K _m(n). In this paper, we completely solve the problem of finding a maximum packing of the balanced complete m-partite graph K _m(n), m odd, with edge-disjoint 5-cycles and we explicitly give the minimum leaves. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Research of M.-H.W. was supported by NSC 93-2115-M-264-001.     

Optimal all-to-all personalized exchange in d-nary banyan multistage interconnection networks

All-to-all personalized exchange occurs in many important applications in parallel processing. In the past two decades, algorithms for all-to-all personalized exchange were mainly proposed for hypercubes, meshes, and tori. Recently, Yang and Wang (IEEE Trans Parallel Distrib Syst 11:261–274, 2000) proposed an optimal all-to-all personalized exchange algorithm for binary (each switch is of size 2×2) banyan multistage interconnection networks. It was pointed out in Massini (Discret Appl Math 128:435–446, 2003) that the algorithm in Yang, Wang (IEEE Trans Parallel Distrib Syst 11:261–274, 2000) depends on the network topologies and requires pre-computation and memory allocation for a Latin square. Thus in (Discret Appl Math 128:435–446, 2003), Massini proposed a new optimal algorithm, which is independent of the network topologies and does not require pre-computation or memory allocation for a Latin square. Unfortunately, Massini’s algorithm has a flaw and does not realize all-to-all personalized exchange. In this paper, we will correct the flaw and generalize Massini’s algorithm to be applicable to d-nary (each switch is of size d×d) banyan multistage interconnection networks. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This research was partially supported by the National Science Council of the Republic of China under the grant NSC94-2115-M-009-006.     

Embedded paths and cycles in faulty hypercubes

An important task in the theory of hypercubes is to establish the maximum integer f _n such that for every set ℱ of f vertices in the hypercube Q_n,{\mathcal {Q}}_{n}, with 0≤f≤f _n , there exists a cycle of length at least 2 ⁿ −2f in the complement of ℱ. Until recently, exact values of f _n were known only for n≤4, and the best lower bound available for f _n with n≥5 was 2n−4. We prove that f ₅=8 and obtain the lower bound f _n ≥3n−7 for all n≥5. Our results and an example provided in the paper support the conjecture that f_n=((n) || 2)-2f_{n}={n\choose 2}-2 for each n≥4. New results regarding the existence of longest fault-free paths with prescribed ends are also proved.     

Distance graphs on R n with 1-norm

Suppose S is a subset of a metric space X with metric d. For each subset D⊆{d(x,y):x,y∈S,x≠y}, the distance graph G(S,D) is the graph with vertex set S and edge set E(S,D)={xy:x,y∈S,d(x,y)∈D}. The current paper studies distance graphs on the n-space R ₁ ⁿ with 1-norm. In particular, most attention is paid to the subset Z ₁ ⁿ of all lattice points of R ₁ ⁿ . The results obtained include the degrees of vertices, components, and chromatic numbers of these graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Supported in part by the National Science Council under grant NSC-94-2115-M-002-015. Taida Institue for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office.     

On 3-Stage Clos Networks with Different Nonblocking Requirements on Two Types of Calls

Hwang and Lin introduced a new nonblocking requirement for 2-cast traffic which imposes different requirements on different types of coexisting calls. The requirement is strictly nonblocking for point-to-point calls among the 2-cast traffic, and is rearrangeable for genuine 2-cast calls. They conjectured that the 3-stage Clos network C(n,n,r,r,2n) satisfies the above requirement. We prove that C(n,n,4,r,2n) satisfies the above requirement.Supported in part by NSC91-2115-M009-002.Supported in part by the National Science Council under grant NSC91-2115-M009-010 and by the Li-Li-Tai-Yang Network Research Center of National Chiao Tung University.     

An unexpected meeting of four seemingly unrelated problems: graph testing, DNA complex screening, superimposed codes and secure key distribution

This paper discusses the relation among four problems: graph testing, DNA complex screening, superimposed codes and secure key distribution. We prove a surprising equivalence relation among these four problems, and use this equivalence to improve current results on graph testing. In the rest of this paper, we give a lower bound for the minimum number of tests on DNA complex screening model. The first and second author would like to dedicate this paper to professor Frank K. Hwang on the occasion of his 65th birthday. This research is partially supported by Republic of China, National Science Council grant NSC 92-2115-M-009-014.     

Total restrained domination in claw-free graphs

A set S of vertices in a graph G=(V,E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of V−S is adjacent to a vertex in V−S. The total restrained domination number of G, denoted by γ _tr (G), is the minimum cardinality of a TRDS of G. In this paper we characterize the claw-free graphs G of order n with γ _tr (G)=n. Also, we show that γ _tr (G)≤n−Δ+1 if G is a connected claw-free graph of order n≥4 with maximum degree Δ≤n−2 and minimum degree at least 2 and characterize those graphs which achieve this bound.     

L(j,k)- and circular L(j,k)-labellings for the products of complete graphs

Let j and k be two positive integers with j≥k. An L(j,k)-labelling of a graph G is an assignment of nonnegative integers to the vertices of G such that the difference between labels of any two adjacent vertices is at least j, and the difference between labels of any two vertices that are at distance two apart is at least k. The minimum range of labels over all L(j,k)-labellings of a graph G is called the λ _j,k -number of G, denoted by λ _j,k (G). A σ(j,k)-circular labelling with span m of a graph G is a function f:V(G)→{0,1,…,m−1} such that |f(u)−f(v)| _m ≥j if u and v are adjacent; and |f(u)−f(v)| _m ≥k if u and v are at distance two apart, where |x| _m =min {|x|,m−|x|}. The minimum m such that there exists a σ(j,k)-circular labelling with span m for G is called the σ _j,k -number of G and denoted by σ _j,k (G). The λ _j,k -numbers of Cartesian products of two complete graphs were determined by Georges, Mauro and Stein ((2000) SIAM J Discret Math 14:28–35). This paper determines the λ _j,k -numbers of direct products of two complete graphs and the σ _j,k -numbers of direct products and Cartesian products of two complete graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This work is partially supported by FRG, Hong Kong Baptist University, Hong Kong; NSFC, China, grant 10171013; and Southeast University Science Foundation grant XJ0607230.     

Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults

The locally twisted cube is a variation of hypercube, which possesses some properties superior to the hypercube. In this paper, we investigate the edge-fault-tolerant hamiltonicity of an n-dimensional locally twisted cube, denoted by LTQ _n . We show that for any LTQ _n (n≥3) with at most 2n−5 faulty edges in which each node is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. We also demonstrate that our result is optimal with respect to the number of faulty edges tolerated.     

Group testing in graphs

This paper studies the group testing problem in graphs as follows. Given a graph G=(V,E), determine the minimum number t(G) such that t(G) tests are sufficient to identify an unknown edge e with each test specifies a subset X⊆V and answers whether the unknown edge e is in G[X] or not. Damaschke proved that ⌈log ₂ e(G)⌉≤t(G)≤⌈log ₂ e(G)⌉+1 for any graph G, where e(G) is the number of edges of G. While there are infinitely many complete graphs that attain the upper bound, it was conjectured by Chang and Hwang that the lower bound is attained by all bipartite graphs. Later, they proved that the conjecture is true for complete bipartite graphs. Chang and Juan verified the conjecture for bipartite graphs G with e(G)≤2⁴ or for k≥5. This paper proves the conjecture for bipartite graphs G with e(G)≤2⁵ or for k≥6. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. J.S.-t.J. is supported in part by the National Science Council under grant NSC89-2218-E-260-013. G.J.C. is supported in part by the National Science Council under grant NSC93-2213-E002-28. Taida Institute for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office.     

Packing cycles exactly in polynomial time

Let G=(V,E) be an undirected graph in which every vertex v∈V is assigned a nonnegative integer w(v). A w-packing is a collection of cycles (repetition allowed) in G such that every v∈V is contained at most w(v) times by the members of . Let 〈w〉=2|V|+∑ _v∈V ⌈log (w(v)+1)⌉ denote the binary encoding length (input size) of the vector (w(v): v∈V) ^T . We present an efficient algorithm which finds in O(|V|⁸〈w〉²+|V|¹⁴) time a w-packing of maximum cardinality in G provided packing and covering cycles in G satisfy the ℤ₊-max-flow min-cut property.     

Decomposition of K m,n into 4-cycles and 2t-cycles

In this paper we show the sufficient conditions for the decomposition of the complete bipartite graphs K _2m,2n and K _2n+1,2n+1−F into cycles of two different lengths 4 and 2t, t>2, where F is a 1-factor of K _2n+1,2n+1. After that we prove that the results are true for t=5 and 6. Dedicated to Frank K. Hwang on the occasion of his 65th birthday. An erratum to this article can be found at     

Optimal tree structure with loyal users and batch updates

We study the probabilistic model in the key tree management problem. Users have different behaviors. Normal users have probability p to issue join/leave request while the loyal users have probability zero. Given the numbers of such users, our objective is to construct a key tree with minimum expected updating cost. We observe that a single LUN (Loyal User Node) is enough to represent all loyal users. When 1−p≤0.57 we prove that the optimal tree that minimizes the cost is a star. When 1−p>0.57, we try to bound the size of the subtree rooted at every non-root node. Based on the size bound, we construct the optimal tree using dynamic programming algorithm in O(n⋅K+K ⁴) time where K=min {4(log (1−p)⁻¹)⁻¹,n} and n is the number of normal users.     

Upper paired-domination in claw-free graphs

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The maximum cardinality of a minimal paired-dominating set of G is the upper paired-domination number of G, denoted by Γ_pr(G). We establish bounds on Γ_pr(G) for connected claw-free graphs G in terms of the number n of vertices in G with given minimum degree δ. We show that Γ_pr(G)≤4n/5 if δ=1 and n≥3, Γ_pr(G)≤3n/4 if δ=2 and n≥6, and Γ_pr(G)≤2n/3 if δ≥3. All these bounds are sharp. Further, if n≥6 the graphs G achieving the bound Γ_pr(G)=4n/5 are characterized, while for n≥9 the graphs G with δ=2 achieving the bound Γ_pr(G)=3n/4 are characterized.     

A quadratic lower bound for Rocchio’s similarity-based relevance feedback algorithm with a fixed query updating factor

Rocchio’s similarity-based relevance feedback algorithm, one of the most important query reformation methods in information retrieval, is essentially an adaptive supervised learning algorithm from examples. In practice, Rocchio’s algorithm often uses a fixed query updating factor. When this is the case, we strengthen the linear Ω(n) lower bound obtained by Chen and Zhu (Inf. Retr. 5:61–86, 2002) and prove that Rocchio’s algorithm makes Ω(k(n−k)) mistakes in searching for a collection of documents represented by a monotone disjunction of k relevant features over the n-dimensional binary vector space {0,1} ⁿ , when the inner product similarity measure is used. A quadratic lower bound is obtained when k is linearly proportional to n. We also prove an O(k(n−k)³) upper bound for Rocchio’s algorithm with the inner product similarity measure in searching for such a collection of documents with a constant query updating factor and a zero classification threshold.