Existence of (q,k, 1) difference families with q a prime power and k = 4, 5

The existence of a (q, k, 1) difference family in GF(q) has been completely solved for k = 3. For k = 4, 5 partial results have been given by Bose, Wilson, and Buratti. In this article, we continue the investigation and show that the necessary condition for the existence of a (q, k, 1) difference family in GF(q), i.e., q ≡ 1 (mod k(k − 1)) is also sufficient for k = 4, 5. For general k, Wilson's bound shows that a (q, k, 1) difference family in GF(q) exists whenever q ≡ 1 (mod k(k − 1)) and q > [k(k − 1)/2]^k(k−1). An improved bound on q is also presented. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 21–30, 1999     

Graphs G for which both G and G¯ are Contraction Critically k-Connected

 An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is called contraction critically k-connected. For k≥4, we prove that if both G and its complement Gˉ are contraction critically k-connected, then |V(G)|<k ^5/3+4k ^3/2. Received: October, 2001 Final version received: September 18, 2002 AMS Classification: 05C40     

Spaces with large projection constants

For every prime numberk, we give an explicit construction of a complexk-dimensional spaceX _k with projection constantγ(X _k ) = √k − 1/√k + 1/k. Moreover, there are realk-dimensional spacesX _k withγ(x _K ) ≧ √k − 1 for a subsequence of integersk. Hence in both casesγ(X _k )/√k → 1 which is the maximal possible value sinceγ(X _k ) ≦ √k is generally true.     

On a generalization of the Shannon functional inequality

The well known Shannon entroy −∑ p_k log p_k satisfies the inequality −∑ p_k log p_k − ∑ p_k log q_k. Extensive studies have been made on the inequality ∑ p_kƒ_k(q_k) ∑ p_kƒ_k(p_k) which contains the above inequality as a special case. In this paper, we consider the most general inequality ∑ g_k(p_k)ƒ_k(p_k) ∑ g_k(p_k)ƒ_k(q_k) above type and obtain its general solution on an open domain.     

On <Emphasis Type="Italic">k</Emphasis>-Spaces and <Emphasis Type="Italic">k</Emphasis><Subscript><Emphasis Type="Italic">R</Emphasis></Subscript>-Spaces

In this note we study the relation between k _R -spaces and k-spaces and prove that a k _R -space with a σ-hereditarily closure-preserving k-network consisting of compact subsets is a k-space, and that a k _R -space with a point-countable k-network consisting of compact subsets need not be a k-space. This work was supported by the NSF of China (10271056).     

Cyclic k‐cycle systems of order 2kn + k: A solution of the last open cases

We exhibit cyclic (K_v, C_k)‐designs with v > k, v ≡ k (mod 2k), for k an odd prime power but not a prime, and for k = 15. Such values were the only ones not to be analyzed yet, under the hypothesis v ≡ k (mod 2k). Our construction avails of Rosa sequences and approximates the Hamiltonian case (v = k), which is known to admit no cyclic design with the same values of k. As a particular consequence, we settle the existence question for cyclic (K_v, C_k)‐designs with k a prime power. © 2004 Wiley Periodicals, Inc. J Combin Designs 12: 299–310, 2004.     

Generating-Tree Isomorphisms for Pattern-Avoiding Involutions

We show that for k ≥ 5 and the permutations τ _k = (k − 1)k(k − 2). . .312 and J _k = k(k − 1). . .21, the generating tree for involutions avoiding the pattern τ _k is isomorphic to the generating tree for involutions avoiding the pattern J _k . This implies a family of Wilf equivalences for pattern avoidance by involutions.     

Short maximal chains in the lattice of clones over a finite set

Let ??_k (3 ≦ k < ?₀) denote the lattice of clones of finitary operations on a k-element set. One interesting characteristic of the uncountable lattice ??_k is the minimum l_k of the cardinalities of maximal chains in ??_k. It is known that for k prime l_k = 5. In this paper the 5-element maximal chains contained in ??_k are investigated. It is proved that for k composite l_k ≧ 6 while for k prime there are exactly (k–2)! (k + 4) 5-element maximal chains in ??_k, each closely related to a group operation.     

The diameter of domination k-critical graphs

A graph is k-domination-critical if γ(G) = k, and for any edge e not in G, γ(G + e) = k ? 1. In this paper we show that the diameter of a domination k-critical graph with k ≧ 2 is at most 2k ? 2. We also show that for every k ≧ 2, there is a k-domination-critical graph having diameter [(3/2)k ? 1]. We also show that the diameter of a 4-domination-critical graph is at most 5.     

On stability of Hamilton‐connectedness under the 2‐closure in claw‐free graphs

It is easy to characterize chordal graphs by every k‐cycle having at least f(k) = k ? 3 chords. I prove new, analogous characterizations of the house‐hole‐domino‐free graphs using f(k) = 2?(k ? 3)/2?, and of the graphs whose blocks are trivially perfect using f(k) = 2k ? 7. These three functions f(k) are optimum in that each class contains graphs in which every k‐cycle has exactly f(k) chords. The functions 3?(k ? 3)/3? and 3k ? 11 also characterize related graph classes, but without being optimum. I consider several other graph classes and their optimum functions, and what happens when k‐cycles are replaced with k‐paths. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:137‐147, 2011     

On the family of diophantine triples {<Emphasis Type="Italic">k</Emphasis> + 1, 4<Emphasis Type="Italic">k</Emphasis>, 9<Emphasis Type="Italic">k</Emphasis> + 3}

We prove that if k is a positive integer and d is a positive integer such that the product of any two distinct elements of the set {k + 1, 4k, 9k + 3, d} increased by 1 is a perfect square, then d = 144k ³ + 192k ² + 76k + 8.      

On generalized Cartan subspaces

Let G be a connected reductive algebraic group defined over a field k of characteristic not 2, θ an involution of G defined over k, H a k-open subgroup of the fixed point group of θ and G _k (resp. H _k ) the set of k-rational points of G (resp. H). The variety G _k /H _k is called a symmetric k-variety. For real and p-adic symmetric k-varieties the space L ²(G _k /H _k ) of square integrable functions decomposes into several series, one for each H _k -conjugacy class of Cartan subspaces of G _k /H _k .     

Singular Manakov flows and geodesic flows on homogeneous spaces of SO(N)

We prove complete integrability of the Manakov-type SO(n)-invariant geodesic flows on homogeneous spaces SO(n)/SO(k₁) ×⋯× SO(k _r ), for any choice of k ₁,…,k _r , k ₁ + ⋯ + k _r ⩽ n. In particular, a new proof of the integrability of a Manakov symmetric rigid body motion around a fixed point is presented. Also, the proof of integrability of the SO(n)-invariant Einstein metrics on SO(k ₁ + k ₂ + k ₃)/SO(k ₁) × SO(k ₂) × SO(k ₃) and on the Stiefel manifolds V (n, k) = SO(n)/SO(k) is given.     

Minimum k-hamiltonian graphs,II

We consider in this paper graphs which remain hamiltonian after the removal of k edges (k-edge hamiltonian) or k vertices (k-hamiltonian). These classes of graphs arise from reliability considerations in network design. In a previous paper, W. W. Wong and C. K. Wong presented families of minimum k-hamiltonian graphs and minimum k-edge hamiltonian graphs for k even. Here, we complete this study in the case where k is odd.     

Ramsey theory for graph connectivity

r_c(k) Denotes the smallest integer such that any c-edge-coloring of the r_c(k) vertex complete graph has a monochromatic k-connected subgraph. For any c, k ≧ 2, we show 2c(k – 1) + 1 ≦ r_c(k) < 10/3 c(k – 1) + 1, and further that 4(k – 1) + 1 ≧ r₂(k) < (3 + √ (k – 1) + 1. Some exact values for various Ramsey connectivity numbers are also computed.     

The number of connected sparsely edged graphs. II. Smooth graphs and blocks

A smooth graph is a connected graph without endpoints; f(n, q) is the number of connected graphs, v(n, q) is the number of smooth graphs, and u(n, q) is the number of blocks on n labeled points and q edges: W_k, V_k, and U_k are the exponential generating functions of f(n, n + k), v(n, n + k), and u(n, n + k), respectively. For any k ? 1, our reduction method shows that V_k can be deduced at once from W_k, which was found for successive k by the computer method described in our previous paper. Again the reduction method shows that U_k must be a sum of powers (mostly negative) of 1 - X and, given this information, we develop a recurrence method well suited to calculate U_k for successive k. Exact formulas for v(n, n + k) and u(n, n + k) for general n follow at once.     

Polynomial interpolation and sums of powers of integers

In this note, we revisit the problem of polynomial interpolation and explicitly construct two polynomials in n of degree k + 1, P_k(n) and Q_k(n), such that P_k(n) = Q_k(n) = f_k(n) for n = 1, 2,…?, k, where f_k(1), f_k(2),…?, f_k(k) are k arbitrarily chosen (real or complex) values. Then, we focus on the case that f_k(n) is given by the sum of powers of the first n positive integers S_k(n) = 1^k + 2^k + ??? + n^k, and show that S_k(n) admits the polynomial representations S_k(n) = P_k(n) and S_k(n) = Q_k(n) for all n = 1, 2,…?, and k ≥ 1, where the first representation involves the Eulerian numbers, and the second one the Stirling numbers of the second kind. Finally, we consider yet another polynomial formula for S_k(n) alternative to the well-known formula of Bernoulli.     

A bound for Wilson's theorem (II)

In this article we prove the following theorem. For any k ≥ 3, let c(k, 1) = exp{exp{k^k2}}. If v(v − 1) ≡ 0 (mod k(k −1)) and v − 1 ≡ 0 (mod k−1) and v > c(k, 1), then a B(v,k, 1) exists. © 1996 John Wiley & Sons, Inc.     

An Algorithm to Construct <Emphasis Type="BoldItalic">k</Emphasis>-Regular <Emphasis Type="BoldItalic">k</Emphasis>-Connected Graphs with the Maximum <Emphasis Type="BoldItalic">k</Emphasis>-Diameter

 Let f(2m,k) be the Maximum k-diameter of k-regular k-connected graphs on 2m vertices. In this paper we give an algorithm and prove that we can construct k-regular k-connected graphs on 2m vertices with the maximum k-diameter using it. We also prove some known results about f(2m,k) and verify that we can get some unknown values of f(2m,k) by our algorithm. Received: December 1, 2000 Final version received: March 12, 2002 Acknowledgments. We thank the referee for many useful suggestions.