On Hamiltonian-connected regular graphs

In this paper it is shown that any m-regular graph of order 2m (m ≧ 3), not isomorphic to K_m,m, or of order 2m + 1 (m even, m ≧ 4), is Hamiltonian connected, which extends a previous result of Nash-Williams. As a corollary, it is derived that any such graph contains atleast m Hamiltonian cycles for odd m and atleast 1/2m Hamiltonian cycles for even m.     

On the wiener type regularity of a boundary point for the polyharmonic operator

It is shown that the Wiener regularity of a boundary point with respect to the m-harmonic operator is a local property for the space dimensions n=2m,2m+1,2m+2 with m > 2 and n = 4,5,6,7 with m = 2. An estimate for the continuity modulus of the solution formulated in terms of the Wiener type m-capacitary integral is obtained for the same n and m.     

A method for constructing a self-dual normal basis in odd characteristic extension fields

This paper proposes a useful method for constructing a self-dual normal basis in an arbitrary extension field F_p^m such that 4p does not divide m(p−1) and m is odd. In detail, when the characteristic p and extension degree m satisfies the following conditions (1) and either (2a) or (2b); (1) 2km+1 is a prime number, (2a) the order of p in F_2km+1 is 2km, (2b) 2km and the order of p in F_2km+1 is km, we can consider a class of Gauss period normal bases. Using this Gauss period normal basis, this paper shows a method to construct a self-dual normal basis in the extension field F_p^m.     

Nearly triply regular Drad’s ofRH type

Nearly triply regular (4m ², 2m ²−m,m ²−m) DRAD’s, wherem is an even power of 2, are constructed.     

A small embedding for partial even-cycle systems

Let m = 2k. We show that for some 0 ≤ ξ <1, a partial directed m-cycle system of order n can be embedded in a directed m-cycle system of order (mn)/2 + (2m² 1) √(8n + 1)/4 + 4m^{3 2} + 4 + 1/2. For fixed m, this is asymptotic in n to (mn)/2 and so for large n is roughly one-fourth the best known bound of 2mn + 1. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 205–215, 1999     

The intersection problem for m-cycle systems

Let I_m(v) denote the set of integers k for which a pair of m-cycle systems of K_v, exist, on the same vertex set, having k common cycles. Let J_m(v) = {0, 1, 2,…, t_v ?2, t_v} where t_v = v(v ? 1)/2m. In this article, if 2mn + x is an admissible order of an m-cycle system, we investigate when I_m(2mn + x) = J_m(2mn + x), for both m even and m odd. Results include J^m(2mn + 1) = I^m(2mn + 1) for all n > 1 if m is even, and for all n > 2 if n is odd. Moreover, the intersection problem for even cycle systems is completely solved for an equivalence class x (mod 2m) once it is solved for the smallest in that equivalence class and for K_2m+1. For odd cycle systems, results are similar, although generally the two smallest values in each equivalence class need to be solved. We also completely solve the intersection problem for m = 4, 6, 7, 8, and 9. (The cased m = 5 was done by C-M. K. Fu in 1987.) © 1993 John Wiley & Sons, Inc.     

On invariant notions of Segre varieties in binary projective spaces

Invariant notions of a class of Segre varieties S_(m)(2){\mathcal{S}_{(m)}(2)} of PG(2 ^m − 1, 2) that are direct products of m copies of PG(1, 2), m being any positive integer, are established and studied. We first demonstrate that there exists a hyperbolic quadric that contains S_(m)(2){\mathcal{S}_{(m)}(2)} and is invariant under its projective stabiliser group G_S(m)(2){G_{{\mathcal{S}}_{(m)}(2)}} . By embedding PG(2 ^m − 1, 2) into PG(2 ^m − 1, 4), a basis of the latter space is constructed that is invariant under G_S(m)(2){G_{{\mathcal{S}}_{(m)}(2)}} as well. Such a basis can be split into two subsets whose spans are either real or complex-conjugate subspaces according as m is even or odd. In the latter case, these spans can, in addition, be viewed as indicator sets of a G_S(m)(2){G_{{\mathcal{S}}_{(m)}(2)}} -invariant geometric spread of lines of PG(2 ^m − 1, 2). This spread is also related with a G_S(m)(2){G_{{\mathcal{S}}_{(m)}(2)}} -invariant non-singular Hermitian variety. The case m = 3 is examined in detail to illustrate the theory. Here, the lines of the invariant spread are found to fall into four distinct orbits under G_S(m)(2){G_{{\mathcal{S}}_{(m)}(2)}} , while the points of PG(7, 2) form five orbits.     

Exact coverings of 2-paths by hamilton cycles

We construct a C(2m, 2m, 2) design which is a family of Hamilton cycles in K_2m so that each 2-path of K_2m lies in exactly two of the cycles.     

On a family of elliptic curves of rank at least 2

Let C_m:y² = x³ ? m²x + p²q² be a family of elliptic curves over ?, where m is a positive integer and p, q are distinct odd primes. We study the torsion part and the rank of C_m(?). More specifically, we prove that the torsion subgroup of C_m(?) is trivial and the ?-rank of this family is at least 2, whenever m ? 0 (mod 3), m ? 0 (mod 4) and m ≡ 2 (mod 64) with neither p nor q dividing m.

     

Connected (g,f)‐factors

The vertex set of the reduced Kneser graph KG₂(m,2) consists of all pairs {a,b} such that a, bε{1,2,…,m} and 2≤|a?b|≤m?2. Two vertices are defined to be adjacent if they are disjoint. We prove that, if m≥4 and m≠5, then the circular chromatic number of KG₂(m,2) is equal to m?2, its ordinary chromatic number. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 62–68, 2002     

Convergence of m-bonacci ‘golden ratios’

This paper proves that the ratios of consecutive terms of the m-bonacci sequence converge to a limit φ_m < 2 and, as m → ∞, these φ_m converge to 2. Further, it is shown that the generating functions for the m-bonacci sequences converge pointwise to the geometric series.     

Neighborly polytopes

A 2m-polytopeQ isneighborly if eachm vertices ofQ determine a face. It is shown that the combinatorial structure of a neighborly 2m-polytope determines the combinatorial structure of every subpolytope. We develop a construction of “sewing a vertex onto a polytope”, which, when applied to a neighborly 2m-polytope, yields a neighborly 2m-polytope with one more, vertex. Using this construction, we show that the numberg(2m+β,2m) of combinatorial types of neighborly 2m-polytopes with 2m+β vertices grows superexponentially as β→∞ (m≧2 fixed) and asm→∞ (β≧4 fixed).     

Inplace 2D matching in compressed images

The compressed matching problem is the problem of finding all occurrences of a pattern in a compressed text. In this paper we discuss the 2-dimensional compressed matching problem in Lempel–Ziv compressed images. Given a pattern P of (uncompressed) size m×m, and a text T of (uncompressed) size n×n, both in 2D-LZ compressed form, our algorithm finds all occurrences of P in T. The algorithm is strongly inplace, that is, the amount of extra space used is proportional to the best possible compression of a pattern of size m². The best compression that the 2D-LZ technique can obtain for a file of size m² is O(m). The time for performing the search is O(n²) and the preprocessing time is O(m³). Our algorithm is general in the sense that it can be used for any 2D compression which can be sequentially decompressed in small space.     

Lorentzian similarity manifolds

An (m+2)-dimensional Lorentzian similarity manifold M is an affine flat manifold locally modeled on (G,ℝ ^m+2), where G = ℝ ^m+2 ⋊ (O(m+1, 1)×ℝ⁺). M is also a conformally flat Lorentzian manifold because G is isomorphic to the stabilizer of the Lorentzian group PO(m+2, 2) of the Lorentz model S ^m+1,1. We discuss the properties of compact Lorentzian similarity manifolds using developing maps and holonomy representations.     

Bound on <Emphasis Type="Italic">m</Emphasis>-restricted Edge Connectivity

An m-restricted edge cut is an edge cut that separates a connected graph into a disconnected one with no components having order less than m. m-restrict edge connectivity λm is the cardinality of a minimum m-restricted edge cut. Let G be a connected k-regular graph of order at least 2m that contains m-restricted edge cuts and X be a subgraph of G. Let θ(X) denote the number of edges with one end in X and the other not in X and ξm=min{θ(X) ;X is a connected vertex-induced subgraph of order m}.It is proved in this paper that if G has girth at least m/2 2,then λm≤ξm.The upper bound of λm is sharp.     

Varieties of quasigroups arising from 2-perfect m-cycle systems

For m = 6 and for all odd composite integers m, as well as for all even integers m 10 that satisfy certain conditions, 2-perfect m-cycle systems are constructed whose quasigroups have a homomorphism onto quasigroups which do not correspond to a 2-perfect m-cycle systems. Thus it is shown that for these values of m the class of quasigroups arising from all 2-perfect m-cycle systems does not form a variety.     

A semi-recursion for the number of involutions in special orthogonal groups over finite fields

Let I(n) be the number of involutions in a special orthogonal group SO(n,Fq) defined over a finite field with q elements, where q is the power of an odd prime. Then the numbers I(n) form a semi-recursion, in that for m>1 we haveI(2m+3)=(q2m+2+1)I(2m+1)+q2m(q2m−1)I(2m−2). We give a purely combinatorial proof of this result, and we apply it to give a universal bound for the character degree sum for finite classical groups defined over Fq.     

On the doyen-wilson theorem for m-cycle systems

In this article we consider the embedding of m-cycle systems of order u in m-cycle systems of order v when m is odd. When u and v are 1 or m (mod 2m) we completely settle this problem, except possibly for the smallest such embedding in some cases when u ≡ v ≡ m (mod 2m). In particular, there are no exceptions if m ∈ {7,9}, so the generalization of the Doyen-Wilson Theorem is now settled for all odd m with m ≤ 9. © 1994 John Wiley & Sons, Inc.     

Rearrangements of (0–1) matrices

Let ℬ(m) be the set of all then-square (0–1) matrices containingm ones andn ²−m zeros, 0<m<n ². The problem of finding the maximum ofs(A ²) over this set, wheres(A ²) is the sum of the entries ofA ²,A ∈ ℬ (m) is considered. This problem is solved in the particular casesm=n ² −k ² andm=k ²,k ²>(n ²/2). This paper forms part of a thesis in partial fulfillment of the requirements for the degree of Doctor of Science at the Technion-Israel Institute of Technology. The author wishes to thank Professor B. Schwarz and Dr. D. London for their help in the preparation of this paper.     

Covering a square by small perimeter rectangles

We show that if the unit square is covered byn rectangles, then at least one must have perimeter at least 4(2m+1)/(n+m(m+1)), wherem is the largest integer whose square is at mostn. This result is exact forn of the formm(m+1) (orm ²).Research supported in part by NSF under contract DMS-8406100.Supported in part by the Weizmann Fellowship for Scientific Research.Supported in part by the University of Minnesota under the Ordway Endowment.