The <Emphasis Type="Italic">p</Emphasis>-Adic order of the <Emphasis Type="Italic">k</Emphasis>-Fibonacci and <Emphasis Type="Italic">k</Emphasis>-Lucas numbers

Let (F _k,n ) _n and (L _k,n )n be the k-Fibonacci and k-Lucas sequence, respectively, which satisfies the same recursive relation a _n+1 = ka _n + a _n?1 with initial values F _k,0 = 0, F _k,1 = 1, L _k,0 = 2 and L _k,1 = k. In this paper, we characterize the p-adic orders ν _p (F _k,n ) and ν _p (L _k,n ) for all primes p and all positive integers k.     

On proper secrets, (<Emphasis Type="Italic">t</Emphasis>, <Emphasis Type="Italic">k</Emphasis>)-bases and linear codes

This paper contains three parts where each part triggered and motivated the subsequent one. In the first part (Proper Secrets) we study the Shamir’s “k-out-of-n” threshold secret sharing scheme. In that scheme, the dealer generates a random polynomial of degree k−1 whose free coefficient is the secret and the private shares are point values of that polynomial. We show that the secret may, equivalently, be chosen as any other point value of the polynomial (including the point at infinity), but, on the other hand, setting the secret to be any other linear combination of the polynomial coefficients may result in an imperfect scheme. In the second part ((t, k)-bases) we define, for every pair of integers t and k such that 1 ≤ t ≤ k−1, the concepts of (t, k)-spanning sets, (t, k)-independent sets and (t, k)-bases as generalizations of the usual concepts of spanning sets, independent sets and bases in a finite-dimensional vector space. We study the relations between those notions and derive upper and lower bounds for the size of such sets. In the third part (Linear Codes) we show the relations between those notions and linear codes. Our main notion of a (t, k)-base bridges between two well-known structures: (1, k)-bases are just projective geometries, while (k−1, k)-bases correspond to maximal MDS-codes. We show how the properties of (t, k)-independence and (t, k)-spanning relate to the notions of minimum distance and covering radius of linear codes and how our results regarding the size of such sets relate to known bounds in coding theory. We conclude by comparing between the notions that we introduce here and some well known objects from projective geometry.      

Degree sequences of <Emphasis Type="Italic">k</Emphasis>-multi-hypertournaments

Let n and k（n ≥ k 〉 1） be two non-negative integers.A k-multi-hypertournament on n vertices is a pair（V,A）,where V is a set of vertices with ｜V｜=n,and A is a set of k-tuples of vertices,called arcs,such that for any k-subset S of V,A contains at least one（at most k!） of the k! k-tuples whose entries belong to S.The necessary and suffcient conditions for a non-decreasing sequence of non-negative integers to be the out-degree sequence（in-degree sequence） of some k-multi-hypertournament are given.     

Goal-minimally <Emphasis Type="Italic">k</Emphasis>-elongated graphs

Let k be an integer. A 2-edge connected graph G is said to be goal-minimally k-elongated (k-GME) if for every edge uv ∈ E(G) the inequality d _G−uv (x, y) > k holds if and only if {u, v} = {x, y}. In particular, if the integer k is equal to the diameter of graph G, we get the goal-minimally k-diametric (k-GMD) graphs. In this paper we construct some infinite families of GME graphs and explore k-GME and k-GMD properties of cages. This research was supported by the Slovak Scientific Grant Agency VEGA No. 1/0406/09.     

Generalizing Pancyclic and <Emphasis Type="Italic">k</Emphasis>-Ordered Graphs

Given positive integers kmn, a graph G of order n is (k,m)-pancyclic if for any set of k vertices of G and any integer r with mrn, there is a cycle of length r containing the k vertices. Minimum degree conditions and minimum sum of degree conditions of nonadjacent vertices that imply a graph is (k,m)-pancylic are proved. If the additional property that the k vertices must appear on the cycle in a specified order is required, then the graph is said to be (k,m)-pancyclic ordered. Minimum degree conditions and minimum sum of degree conditions for nonadjacent vertices that imply a graph is (k,m)-pancylic ordered are also proved. Examples showing that these constraints are best possible are provided.Acknowledgments. The authors would like to thank the referees for their careful reading of the paper and their useful suggestions.Final version received: January 26, 2004     

Structure theorems of <Emphasis Type="Italic">E</Emphasis>(<Emphasis Type="Italic">n</Emphasis>)-Azumaya algebras

Let k be a field and E(n) be the 2 ⁿ⁺¹-dimensional pointed Hopf algebra over k constructed by Beattie, Dăscălescu and Grünenfelder [J. Algebra, 2000, 225: 743–770]. E(n) is a triangular Hopf algebra with a family of triangular structures R _M parameterized by symmetric matrices M in M _n (k). In this paper, we study the Azumaya algebras in the braided monoidal category $ E_{(n)} \mathcal{M}^{R_M } $ E_{(n)} \mathcal{M}^{R_M } and obtain the structure theorems for Azumaya algebras in the category $ E_{(n)} \mathcal{M}^{R_M } $ E_{(n)} \mathcal{M}^{R_M } , where M is any symmetric n×n matrix over k.     

On κ—ordered Graphs Involved Degree Sum

A graph G is κ-ordered Hamiltonian 2≤κ≤n,if for every ordered sequence S of κ distinct vertices of G,there exists a Hamiltonian cycle that encounters S in the given order,In this article,we prove that if G is a graph on n vertices with degree sum of nonadjacent vertices at least n 3κ-9/2,then G is κ-ordered Hamiltonian for κ=3,4,…,[n/19].We also show that the degree sum bound can be reduced to n 2[κ/2]-2 if κ(G）≥3κ-1/2 or δ（G）≥5κ-4.Several known results are generalized.     

Eigenvalues of the Manifold Sp（n）/U（n）

In this paper, we give the eigenvalues of the manifold Sp(n)/U(n). We prove that an eigenvalue λ _s (f ₂, f ₂, …, f _n ) of the Lie group Sp(n), corresponding to the representation with label (f ₁, f ₂, ..., f _n ), is an eigenvalue of the manifold Sp(n)/U(n), if and only if f ₁, f ₂, …, f _n are all even.     

Realizability of the <Emphasis Type="Italic">H</Emphasis><Subscript><Emphasis Type="Italic">k</Emphasis></Subscript>-distance functions by homology classes of path spaces

In previous papers, we have constructed and studied mappings d _k : M × M → ℝ called the H _k -distance functions. The main result of this paper is a theorem on realizability of the generalized distances d _k (υ, w), υ, w ∈ M, by critical values of the length functional L: Ω(M, υ, w) → ℝ generated by nontrivial homology classes of the space Ω(M, υ, w) of paths joining the points υ and w.     

The <Emphasis Type="Italic">k</Emphasis>-Centrum Straight-line Location Problem

A line is sought in the plane which minimizes the sum of the k largest (Euclidean) weighted distances from n given points. This problem generalizes the known straight-line center and median problems and, as far as the authors are aware, has not been tackled up to now. By way of geometric duality it is shown that such a line may always be found which either passes through two of the given points or lying at equal weighted distance from three of these. This allows construction of an algorithm to find all t-centrum lines for 1 ≤ t ≤ k in O((k + logn)n ³). Finally it is shown that both, the characterization of an optimal line and the algorithm, can be extended to any smooth norm.     

On <Emphasis Type="Italic">k</Emphasis>- critical 2<Emphasis Type="Italic">k</Emphasis>- connected graphs

A graph G is called an (n,k)-graph if κ(G-S)=n-|S| for any S ? V(G) with |S| ≤ k, where ?(G) denotes the connectivity of G. Mader conjectured that for k ≥ 3 the graph K_2k+2?(1-factor) is the unique (2k, k)-graph. Kriesell has settled two special cases for k = 3,4. We prove the conjecture for the general case k ≥ 5.     

Finite <Emphasis Type="Italic">p</Emphasis>-central groups of height <Emphasis Type="Italic">k</Emphasis>

A finite group G is called p ⁱ -central of height k if every element of order p ⁱ of G is contained in the k ^th -term ζ _k (G) of the ascending central series of G. If p is odd, such a group has to be p-nilpotent (Thm. A). Finite p-central p-groups of height p − 2 can be seen as the dual analogue of finite potent p-groups, i.e., for such a finite p-group P the group P/Ω₁(P) is also p-central of height p − 2 (Thm. B). In such a group P, the index of P ^p is less than or equal to the order of the subgroup Ω₁(P) (Thm. C). If the Sylow p-subgroup P of a finite group G is p-central of height p − 1, p odd, and N _G (P) is p-nilpotent, then G is also p-nilpotent (Thm. D). Moreover, if G is a p-soluble finite group, p odd, and P ∈ Syl _p (G) is p-central of height p − 2, then N _G (P) controls p-fusion in G (Thm. E). It is well-known that the last two properties hold for Swan groups (see [11]).     

Semiclassical <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript> Estimates of Quasimodes on Curved Hypersurfaces

Let M be a compact manifold of dimension n, P=P(h) a semiclassical pseudodifferential operator on M, and u=u(h) an L ² normalized family of functions such that P(h)u(h) is O(h) in L ²(M) as h↓0. Let H⊂M be a compact submanifold of M. In a previous article, the second-named author proved estimates on the L ^p norms, p≥2, of u restricted to H, under the assumption that the u are semiclassically localized and under some natural structural assumptions about the principal symbol of P. These estimates are of the form Ch ^−δ(n,k,p) where k=dim H (except for a logarithmic divergence in the case k=n−2, p=2). When H is a hypersurface, i.e., k=n−1, we have δ(n,n−1, 2)=1/4, which is sharp when M is the round n-sphere and H is an equator.     

<Emphasis Type="Italic">k</Emphasis>-Free-like groups

The following results are proved. In Theorem 1, it is stated that there exist both finitely presented and not finitely presented 2-generated nonfree groups which are k-free-like for any k ⩾ 2. In Theorem 2, it is claimed that every nonvirtually cyclic (resp., noncyclic and torsion-free) hyperbolic m-generated group is k-free-like for every k ⩾ m + 1 (resp., k ⩾ m). Finally, Theorem 3 asserts that there exists a 2-generated periodic group G which is k-free-like for every k ⩾ 3. Supported by NSF (grant Nos. DMS 0455881 and DMS-0700811). (A. Yu. Olshanskii, M. V. Sapir) Supported by RFBR project No. 08-01-00573. (A. Yu. Olshanskii) Supported by BSF grant (USA–Israel). (M. V. Sapir) Translated from Algebra i Logika, Vol. 48, No. 2, pp. 245–257, March–April, 2009.     

<Emphasis Type="Italic">k</Emphasis>-invariant nets over an algebraic extension of a field <Emphasis Type="Italic">k</Emphasis>

Let K be an algebraic extension of a field k, let σ = (σ _ij ) be an irreducible full (elementary) net of order n ≥ 2 (respectively, n ≥ 3) over K, while the additive subgroups σ _ij are k-subspaces of K. We prove that all σij coincide with an intermediate subfield P, k ? P ? K, up to conjugation by a diagonal matrix.     

Partitioning a graph into defensive <Emphasis Type="Italic">k</Emphasis>-alliances

A defensive k-alliance in a graph is a set S of vertices with the property that every vertex in S has at least k more neighbors in S than it has outside of S. A defensive k-alliance S is called global if it forms a dominating set. In this paper we study the problem of partitioning the vertex set of a graph into (global) defensive k-alliances. The (global) defensive k-alliance partition number of a graph Θ = (V, E), (ψ _k ^gd (Γ)) ψ _k ^d (Γ), is defined to be the maximum number of sets in a partition of V such that each set is a (global) defensive k-alliance. We obtain tight bounds on ψ _k ^d (Θ) and ψ _k ^gd (Γ) in terms of several parameters of the graph including the order, size, maximum and minimum degree, the algebraic connectivity and the isoperimetric number. Moreover, we study the close relationships that exist among partitions of Γ₁ × Γ₂ into (global) defensive (k ₁ + k ₂)-alliances and partitions of Γ _i into (global) defensive k _i -alliances, i ∈ {1, 2}.     

On the phase transitions of (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)-SAT

Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let T _k (V) denote the set of all 2 ^k n ^k possible k-tuples on V. Randomly generate a set C of k-tuples by including every k-tuple in T _k (V) independently with probability p, and let Q be a given set of q “bad” tuple assignments. An instance I = (C,Q) is called satisfiable if there exists an assignment that does not set any of the k-tuples in C to a bad tuple assignment in Q. Suppose that θ, q > 0 are fixed and ε = ε(n) > 0 be such that εlnn/lnlnn→∞. Let k ≥ (1 + θ) log₂ n and let \({p_0} = \frac{{\ln 2}}{{q{n^{k - 1}}}}\). We prove that

$$\mathop {\lim }\limits_{n \to \infty } P\left[ {I is satisfiable} \right] = \left\{ {\begin{array}{*{20}c} {1,} & {p \leqslant (1 - \varepsilon )p_0 ,} \\ {0,} & {p \geqslant (1 + \varepsilon )p_0 .} \\ \end{array} } \right.$$

     

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.      

The Roman <Emphasis Type="Italic">k</Emphasis>-domatic number of a graph

Let k be a positive integer. A Roman k-dominating function on a graph G is a labeling f: V (G) → {0, 1, 2} such that every vertex with label 0 has at least k neighbors with label 2. A set {f ₁, f ₂, …, f _d } of distinct Roman k-dominating functions on G with the property that Σ _i=1 ^d f _i (v) ≤ 2 for each v ∈ V (G), is called a Roman k-dominating family (of functions) on G. The maximum number of functions in a Roman k-dominating family on G is the Roman k-domatic number of G, denoted by d _kR (G). Note that the Roman 1-domatic number d _1R (G) is the usual Roman domatic number d _R (G). In this paper we initiate the study of the Roman k-domatic number in graphs and we present sharp bounds for d _kR (G). In addition, we determine the Roman k-domatic number of some graphs. Some of our results extend those given by Sheikholeslami and Volkmann in 2010 for the Roman domatic number.     

Clique matchings in the <Emphasis Type="Italic">k</Emphasis>-ary <Emphasis Type="Italic">n</Emphasis>-dimensional cube

A clique matching in the k-ary n-dimensional cube (hypercube) is a collection of disjoint one-dimensional faces. A clique matching is called perfect if it covers all vertices of the hypercube. We show that the number of perfect clique matchings in the k-ary n-dimensional cube can be expressed as the k-dimensional permanent of the adjacency array of some hypergraph. We calculate the order of the logarithm of the number of perfect clique matchings in the k-ary n-dimensional cube for an arbitrary positive integer k as n→∞.