On the uniqueness of the graphs G(n, k) of the Johnson schemes

T. A. Dowling (J. Combin. Theory6 (1969), 251–263) proved the uniqueness of the graphs G(n, k) of the Johnson schemes for n > 2k(k ? 1) + 4. We improve this result by showing the uniqueness of G(n, k) for n > 4k.     

The graphs G(n, k) of the Johnson Schemes are unique for n ≥ 20

Let G(n, k) denote the graph of the Johnson Scheme J(n, k), i.e., the graph whose vertices are all k-subsets of a fixed n-set, with two vertices adjacent if and only if their intersection is of size k ? 1. It is known that G(n, k) is a distance regular graph with diameter k. Much work has been devoted to the question of whether a distance regular graph with the parameters of G(n, k) must isomorphic to G(n, k). In this paper, this question is settled affirmatively for n ≥ 20. In fact the result is proved with weaker conditions.     

Characterization of k-variegated graphs, k ⩾ 3

A graph is said to be k-variegated if its vertex set can be partitioned into k equal parts such that each vertex is adjacent to exactly one vertex from every other part not containing it. Bednarek and Sanders [1] posed the problem of characterizing k-variegated graphs. V.N. Bhat-Nayak, S.A. Choudum and R.N. Naik [2] gave the characterization of 2-variegated graphs. In this paper we characterize k-variegated graphs for k ? 3.     

On the mutual embeddability of (2k, k, k − 1) and (2k − 1, k, k) quasi-residual designs

The complements of blocks containing a given point in a (2k ? 1, k, k) design, enlarged by this point, and the blocks not containing it, form a (2k ? 1, k, k) design. Likewise, the complements of blocks containing a given point in a (2k, k, k ? 1) design and the blocks not containing it, form a (2k ? 1, k, k) design. In this paper we show that if a quasi-residual (2k ? 1, k, k) design is obtained from an embeddable (2k ? 1, k, k) or (2k, k, k ? 1) design, then it is also embeddable, and describe an example of non-embeddable (12, 6, 5) design such that all (11, 6, 6) designs obtained from it are embeddable.     

Uniqueness of norm on L(G) and C(G) when G is a compact group

Let G be a compact group. If the trivial representation of G is not weakly contained in the left regular representation of G on L₀²(G) and X is either L^p(G) for 1<p?∞ or C(G), then we show that every complete norm |·| on X that makes translations from (X,|·|) into itself continuous is equivalent to ||·||_p or ||·||_∞ respectively. If 1<p?∞ and every left invariant linear functional on L^p(G) is a constant multiple of the Haar integral, then we show that every complete norm |·| on L^p(G) that makes translations from (L^p(G),|·|) into itself continuous and that makes the map t?L_t from G into bounded is equivalent to ||·||_p.     

Polynomial algorithms for m × (m + 1) integer programs and m × (m + k) diophantine systems

Recent results of Kannan and Bachem (on computing the Smith Normal Form of a matrix) and Lenstra (on solving integer inequality systems) are used with classical results by Smith to obtain polynomial-time algorithms for solving m × (m + 1) equality constrained integer programs and m × (m + k) systems of diophantine equations for fixed k.     

On integers of the forms k−2 and k2+1

In this paper we prove that if (r,12)?3, then the set of positive odd integers k such that k^r−2ⁿ has at least two distinct prime factors for all positive integers n contains an infinite arithmetic progression. The same result corresponding to k^r2ⁿ+1 is also true.     

An upper bound on the Ramsey numbers R(3, k)

Ajtai, Komlós, and Szemerédi (J. Combin. Theory Ser. A29 (1980), 354–360) recently announced that $\text{R(3, k) <}\text{100k}{}^2\text{ln}\text{k}$. This follows from the discovery of a (polynomial) algorithm to find in any triangle-free graph on n vertices with average degree t an independent set of size at least $\text{n}\text{ln}\text{t}\text{100t}$. Here, their algorithm is modified to improve both bounds, replacing 100 by 2.4, and carefully working out the details of the proof.     

On the restriction map of the Fourier-Stieltjes algebra B(G) and Bp(G)

G is a locally compact group that contains the semidirect product J of a closed normal subgroup H and a closed connected subgroup K. Conditions on J are given that imply that the restriction map B_p(G) → B_p(H) (1 < p < ∞; G amenable if p ≠ 2) of the Fourier-Stieltjes algebras is not surjective. It is also shown that if the restriction map B(J) → B(H) is surjective, J need not be a direct product, even if H is nilpotent.     

Reliability analysis of a k-out-of-n:G repairable system with single vacation

This paper analyzes a k-out-of-n:G   repairable system with one repairman who takes a single vacation, the duration of which follows a general distribution. The working time of each component is an exponentially distributed random variable and the repair time of each failed component is governed by an arbitrary distribution. Moreover, we assume that every component is “as good as new” after being repaired. Under these assumptions, several important reliability measures such as the availability, the rate of occurrence of failures, and the mean time to first failure of the system are derived by employing the supplementary variable technique and the Laplace transform. Meanwhile, their recursive expressions are obtained. Furthermore, through numerical examples, we study the influence of various parameters on the system reliability measures. Finally, the Monte Carlo simulation and two special cases of the system which are (n-1)$(n-1)$-out-of-n:G repairable system and 1-out-of-n:G repairable system are presented to illustrate the correctness of the analytical results.     

On some t−(2k, k, λ) designs

t?(2k, k, λ) designs having a property similar to that of Hadamard 3-designs are studied. We consider conditions (i), (ii), or (iii) for t?(2k, k, λ) designs: (i) The complement of each block is a block. (ii) If A and B are a complementary pair of blocks, then ∥ A ∩ C ∥ = ∥ B ∩ C ∥ ± u holds for any block C distinct from A and B, where u is a positive integer. (iii) if A and B are a complementary pair of blocks, then ∥ A ∩ C ∥ = ∥ B ∩ C ∥ or ∥ A ∩ C ∥ = ∥ B ∩ C ∥ ± u holds for any block C distinct from A and B, where u is a positive integer. We show that a t?(2k, k, λ) design with t ? 2 and with properties (i) and (ii) is a 3?(2u(2u + 1), u(2u + 1), u(2u² + u ? 2)) design, and that a t?(2k, k, λ) design with t ? 4 and with properties (i) and (iii) is the 5-(12, 6, 1) design, the 4-(8, 4, 1) design, a $\text{5?(2u}{}^2\text{, u}{}^2\text{,}\text{1}\text{4}\text{(u}{}^2\text{? 3) (u}{}^2\text{? 4))}$ design, or a $\text{5?(}\text{2}\text{3}\text{u(2u + 1),}\text{1}\text{3}\text{u(2u = 1),}\text{1}\text{5 4}\text{u(2u}{}^2\text{+ u ? 9) (2u}{}^2\text{+ u ? 12))}$ design.     

A note on the (G′/G)-expansion method again

We report an observation on two recent analytic methods; the (G′/G)-expansion method and the simplest equation method.     

Parallel and k-out-of-n: G systems with nonidentical components and their mean residual life functions

A system with n independent components which has a k-out-of-n: G structure operates if at least k components operate. Parallel systems are 1-out-of-n: G systems, that is, the system goes out of service when all of its components fail. This paper investigates the mean residual life function of systems with independent and nonidentically distributed components. Some examples related to some lifetime distribution functions are given. We present a numerical example for evaluating the relationship between the mean residual life of the k-out-of-n: G system and that of its components.     

Translation-invariant linear forms on C0(G), C(G), Lp(G) for noncompact groups

Suppose G is a locally compact noncompact group. For abelian such G's, it is shown in this paper that L¹(G), C(G), and L^∞(G) always have discontinuous translation-invariant linear forms(TILF's) while C₀(G) and L^p(G) for 1 < p < ∞ have such forms if and only if $\text{G}\text{H}$ is a torsion group for some open σ-compact subgroup H of $\text{G}$. For σ-compact amenable G's, all the above spaces have discontinuous left TILF's.     

On (d,1)-total numbers of graphs

A (d,1)-total labelling of a graph G assigns integers to the vertices and edges of G such that adjacent vertices receive distinct labels, adjacent edges receive distinct labels, and a vertex and its incident edges receive labels that differ in absolute value by at least d. The span of a (d,1)-total labelling is the maximum difference between two labels. The (d,1)-total number, denoted , is defined to be the least span among all (d,1)-total labellings of G. We prove new upper bounds for , compute some for complete bipartite graphs K_m,n, and completely determine all for d=1,2,3. We also propose a conjecture on an upper bound for in terms of the chromatic number and the chromatic index of G.     

A characterization of the closed unital ideals of the Fourier-Stieltjes algebra B(G) of a locally compact amenable group G

Let G be a locally compact amenable group, B(G) its Fourier-Stieltjes algebra and I be a closed ideal of it. In this paper we prove the following result: The ideal I has a unit element iff it is principal. This is the noncommutative version of the Glicksberg-Host-Parreau Theorem. The paper also contains an abstract version of this theorem.