421 research outputs found
Enumerating Consecutive and Nested Partitions for Graphs
No full textConsecutive & nested partitions have been extensively studied in the set-partition problem as tools
with which to search efficiently for an optimal partition. We extend the study of consecutive and
nested partitions on a set of integers to the vertex-set of a graph. A subset of vertices is considered
consecutive if the subgraph induced by the subset is connected. In this sense the partition problem on
a set of integers can be treated as a special case when the graph is a line. In this paper we give the
number of consecutive & nested partitions when the graph is a cycle. We also give a partial order
on general graphs with respect to these numbers
An improved upper bound for the subarray partial concentrators
No full textAbstractPartial concentrators are used for the assignment of inlets to first-stage switches in the two-stage rearrangeable broadcast networks proposed by Richards and Hwang, who also proposed the subarray method to construct partial concentrators and studied their capacities. An upper bound of the capacity of the subarray partial concentrator was given by Du, Hwang and Richards and conjectured to be the best by Richards and Hwang. In this paper we disprove this conjecture by giving a better upper bound
The capacity of the subarray partial concentrators
No full textAbstractA partial concentrator with parameters n, m, and c, is an n (inputs) × m (outputs) bipartile graph such that any set of k inputs, k≤c, has a perfect matching to some set of k outputs. A partial concentrator is regular if each input has M edges and each output has nMm edges. We study the problem of maximizing c for given m,n and M. For n=(mM)2 Kufta and Vacroux, and Richards and Hwang gave a similar construction of a partial concentrator and proved c≥M2+M−1. If, furthermore, mM is a prime, the construction given by Richards and Hwang has a cyclic property. In this paper we use this cyclic property to prove c≥M2+2M−2. This is the best result possible for M=3 since it coincides with an upper bound previously proved
The Existence of Symmetric Skew Balanced Starters for Odd Prime Powers
No full textStrong starters and skew starters have been widely used in various combinatorial designs such as Room squares and Howell designs. Mullin and Nemeth, also Chong and Chan, gave a construction of skew starters for every odd prime power n. Skew balanced starters and symmetric skew balanced starters are two special types of skew starters crucially used in the construction of completely balanced Howell rotations for bridge tournaments (which is different from Howell designs and whose construction remains an open problem). Represent an odd prime power n as ek + 1 where e = 2m and k is odd. Recently, Du and Hwang gave a construction for symmetric skew balanced starters for general m ⩾ 2 but could prove its validity only for k ⩾ O(e3). Yu and Hwang improved this result to k ⩾ O(e) and conjectured that the construction is valid for all m ⩾ 2 and k − 1. In this paper we prove the conjecture except for the two cases k = 3, 9
New classes of complete balanced Howell rotations
No full textAbstractComplete balanced Howell rotations (CBHR) owe their origins to duplicate bridge tournaments but have since been shown to possess of deep combinatorial properties. They include many other combinatorial designs as special cases, such as: balanced Howell rotations, weak complete balanced Howell rotations, Room squares, Howell designs, and a class of balanced incomplete block designs.All known CBHR's are for n partnerships such that n = 2t(pr + 1), where pr is an odd prime power and t a natural number. In most cases, pr ≡ 3(mod 4) is also assumed. Berlekamp and Hwang gave constructions of CBHR's for each such n > 3 with t = 0; Schellenberg gave constructions for each such n with t = 1. In this paper, we construct CBHR for each such n with t arbitrary
New constructions for balanced Howell rotations
No full textAbstractHowell rotations have been used in bridge tournaments for a long time. But it was not until 1955 that Parker and Mood first gave a rigorous definition of a balanced Howell rotation and began a systematic study of its mathematical properties. Later, Berlekamp and Hwang extended this work to the study of complete balanced Howell rotations (which are special cases of balanced Howell rotations). Surprisingly, even though the concept of balanced Howell rotations precedes that of complete balanced Howell rotations, systematic construction methods have been studied only for the latter. Most of these construction methods use the properties of a Galois field GF(pγ) where pγ is a prime power. In this paper, we use the properties of a Galois domain GD(pγqs) to construct balanced Howell rotations for n partnerships where n − 1 is the product of two prime powers satisfying certain conditions. In particular, we construct a balanced Howell rotation for 36 partnerships, this being the smallest number for which the existence of a balanced Howell rotation was not previously known. We also give two composition methods for the constructions of balanced Howell rotations
Selecting k objects from a cycle with p pairs of separation s
No full textAbstractRecently Konvalina determined the number of ways of selecting k objects from a cycle of n objects with no two selected objects separated by exactly one object. For arbitrary integers p, k, and s, we show that a recent result of the author can be applied to determine the number of ways of selecting k objects (from a cycle of n objects) which contain exactly p pairs of selected objects separated by exactly s objects. Konvalina's result follows as the special case p = 0 and s = 1
The steiner ratio conjecture is true for five points
No full textAbstractThe long-standing conjecture of Gilbert and Pollak states that for any set of n given points in the Euclidean plane, the ratio of the length of a Steiner minimal tree and the length of a minimal (spanning) tree is at least 32. This conjecture was shown to be true for n = 3 by Gilbert and Pollak, and for n = 4 by Pollak. Recently, Du, Yao and Hwang used a different approach to give a shorter proof for n = 4. In this paper we continue this approach to prove the conjecture for n = 5. Such results for small n are useful in obtaining bounds for the ratio of the two lengths in the general case
- …
