Optimal (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">n</Emphasis>) visual cryptographic schemes for general <Emphasis Type="Italic">k</Emphasis>

In (k, n) visual cryptographic schemes (VCS), a secret image is encrypted into n pages of cipher text, each printed on a transparency sheet, which are distributed among n participants. The image can be visually decoded if any k(≥2) of these sheets are stacked on top of one another, while this is not possible by stacking any k − 1 or fewer sheets. We employ a Kronecker algebra to obtain necessary and sufficient conditions for the existence of a (k, n) VCS with a prior specification of relative contrasts that quantify the clarity of the recovered image. The connection of these conditions with an L ₁-norm formulation as well as a convenient linear programming formulation is explored. These are employed to settle certain conjectures on contrast optimal VCS for the cases k = 4 and 5. Furthermore, for k = 3, we show how block designs can be used to construct VCS which achieve optimality with respect to the average and minimum relative contrasts but require much smaller pixel expansions than the existing ones.     

Interval <Emphasis Type="Italic">k</Emphasis>-Graphs and Orders

An interval k-graph is the intersection graph of a family of intervals of the real line partitioned into k classes with vertices adjacent if and only if their corresponding intervals intersect and belong to different classes. In this paper we study the cocomparability interval k-graphs; that is, the interval k-graphs whose complements have a transitive orientation and are therefore the incomparability graphs of strict partial orders. For brevity we call these orders interval k-orders. We characterize the kind of interval representations a cocomparability interval k-graph must have, and identify the structure that guarantees an order is an interval k-order. The case k =?2 is peculiar: cocomparability interval 2-graphs (equivalently proper- or unit-interval bigraphs, bipartite permutation graphs, and complements of proper circular-arc graphs to name a few) have been characterized in many ways, but we show that analogous characterizations do not hold if k >?2. We characterize the cocomparability interval 3-graphs via one forbidden subgraph and hence interval 3-orders via one forbidden suborder.     

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     

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 the <Emphasis Type="Italic">k</Emphasis>-gamma <Emphasis Type="Italic">q</Emphasis>-distribution

We provide combinatorial as well as probabilistic interpretations for the q-analogue of the Pochhammer k-symbol introduced by Díaz and Teruel. We introduce q-analogues of the Mellin transform in order to study the q-analogue of the k-gamma distribution.     

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.     

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.     

A Note on <Emphasis Type="Italic">k</Emphasis>-walks in Bridgeless Graphs

We show that every bridgeless graph of maximum degree has a spanning -walk. The bound is optimal. Supported by project 1M0545 and Research Plan MSM 4977751301 of the Czech Ministry of Education. Supported by the NSFC (60673047 and 10471078), SRSDP (20040422004) and PDSF (2004036402) of China.     

<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.     

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.      

Facets of the <Emphasis Type="Italic">r</Emphasis>-Stable (<Emphasis Type="Italic">n</Emphasis>, <Emphasis Type="Italic">k</Emphasis>)-Hypersimplex

Let k, n, and r be positive integers with k < n and \({r \leq \lfloor \frac{n}{k} \rfloor}\). We determine the facets of the r-stable n, k-hypersimplex. As a result, it turns out that the r-stable n, k-hypersimplex has exactly 2n facets for every \({r < \lfloor \frac{n}{k} \rfloor}\). We then utilize the equations of the facets to study when the r-stable hypersimplex is Gorenstein. For every k > 0 we identify an infinite collection of Gorenstein r-stable hypersimplices, consequently expanding the collection of r-stable hypersimplices known to have unimodal Ehrhart \({\delta}\)-vectors.     

<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.     

<Emphasis Type="Italic">k</Emphasis>-noncrossing and <Emphasis Type="Italic">k</Emphasis>-nonnesting graphs and fillings of ferrers diagrams

We give a correspondence between graphs with a given degree sequence and fillings of Ferrers diagrams by nonnegative integers with prescribed row and column sums. In this setting, k-crossings and k-nestings of the graph become occurrences of the identity and the antiidentity matrices in the filling. We use this to show the equality of the numbers of k-noncrossing and k-nonnesting graphs with a given degree sequence. This generalizes the analogous result for matchings and partition graphs of Chen, Deng, Du, Stanley, and Yan, and extends results of Klazar to k > 2. Moreover, this correspondence reinforces the links recently discovered by Krattenthaler between fillings of diagrams and the results of Chen et al.     

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]).     

On the Structure of Contractible Edges in <Emphasis Type="Italic">k</Emphasis>-connected Partial <Emphasis Type="Italic">k</Emphasis>-trees

Contraction of an edge e merges its end points into a new single vertex, and each neighbor of one of the end points of e is a neighbor of the new vertex. An edge in a k-connected graph is contractible if its contraction does not result in a graph with lesser connectivity; otherwise the edge is called non-contractible. In this paper, we present results on the structure of contractible edges in k-trees and k-connected partial k-trees. Firstly, we show that an edge e in a k-tree is contractible if and only if e belongs to exactly one (k + 1) clique. We use this characterization to show that the graph formed by contractible edges is a 2-connected graph. We also show that there are at least |V(G)| + k − 2 contractible edges in a k-tree. Secondly, we show that if an edge e in a partial k-tree is contractible then e is contractible in any k-tree which contains the partial k-tree as an edge subgraph. We also construct a class of contraction critical 2k-connected partial 2k-trees.     

The Number of Labeled Outerplanar <Emphasis Type="Italic">k</Emphasis>-Cyclic Graphs

A k-cyclic graph is a graph with cyclomatic number k. An explicit formula for the number of labeled connected outerplanar k-cyclic graphs with a given number of vertices is obtained. In addition, such graphs with fixed cyclomatic number k and a large number of vertices are asymptotically enumerated. As a consequence, it is found that, for fixed k, almost all labeled connected outerplanar k-cyclic graphs with a large number of vertices are cacti.     

On <Emphasis Type="Italic">k</Emphasis>-th Power of Upper Bound Graphs

We consider k-th power of upper bound graphs. According to the characterization of upper bound graphs, we obtain a characterization of k-th power of upper bound graphs. That is, for a connected upper bound graph G, G^k is an upper bound graph if and only if for any pair of A^k -simplicial vertices s₁, s₂ such that , there exists a G^k -simplicial vertex s satisfying the conditions: and . Furthermore we also get some properties on squares of upper bound graphs.AMS Subject Classification: 05C62.     

The Relaxed Edge-Coloring Game and <Emphasis Type="Italic">k</Emphasis>-Degenerate Graphs

The (r, d)-relaxed edge-coloring game is a two-player game using r colors played on the edge set of a graph G. We consider this game on forests and more generally, on k-degenerate graphs. If F is a forest with Δ(F)=Δ, then the first player, Alice, has a winning strategy for this game with r=Δ?j and d≥2j+2 for 0≤j≤Δ?1. This both improves and generalizes the result for trees in Dunn, C. (Discret. Math. 307, 1767–1775, 2007). More broadly, we generalize the main result in Dunn, C. (Discret. Math. 307, 1767–1775, 2007) by showing that if G is k-degenerate with Δ(G)=Δ and j∈[Δ+k?1], then there exists a function h(k,j) such that Alice has a winning strategy for this game with r=Δ+k?j and d≥h(k,j).     

Removing vertices from a <Emphasis Type="Italic">k</Emphasis>-connected graph without losing its <Emphasis Type="Italic">k</Emphasis>-connectivity

The paper studies the problem of removing vertices from a k-connected graph without losing its k-connectivity. It is proved that certain inner vertices can be removed from k-blocks, provided that the interior of each block is sufficiently large with respect to its boundary, and the degree of every vertex of the graph is no less than or . Bibliography: 3 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 340, 2006, pp. 103–116.     

Restricted <Emphasis Type="Italic">k</Emphasis>-color partitions

We generalize overpartitions to (k, j)-colored partitions: k-colored partitions in which each part size may have at most j colors. We find numerous congruences and other symmetries. We use a wide array of tools to prove our theorems: generating function dissections, modular forms, bijections, and other combinatorial maps. In the process of proving certain congruences, we find results of independent interest on the number of partitions with exactly 2 sizes of part in several arithmetic progressions. We find connections to divisor sums, the Han/Nekrasov–Okounkov hook length formula and a possible approach to finitization, and other topics, suggesting that a rich mine of results is available. We pose several immediate questions and conjectures.