Singular (k,n − k) boundary value problems between conjugate and right focal

For 1 ⩽k⩽n − 1 and 0 ⩽q⩽k − 1, solutions are obtained for the boundary value problem, (−1)^n−k = f(x,y), y⁽ⁱ⁾=0, 0⩽i⩽k − 1, and y⁽ⁱ⁾ = 0, q⩽j⩽n − k + q − 1, where f(x,y) is singular at y = 0. An application is made of a fixed point theorem for operators that are decreasing with respect to a cone.     

The maximum distance problem and band sequences

We solve the following problem. For 1 ⩽ j, k ⩽ n and |j − k| ⩽ m, let a_jk be a given complex number with a_kj = ā_jk. We wish to find linearly independent vectors x₁,…,x_n such that 〈x_k, x_j〉 = a_jk for |j − k| ⩽ m and such that the distance from x_k to the linear span of x₁,…,x_k−1 is maximal for 2 ⩽ k ⩽ n. We construct and characterize all such sequences of vectors. Our solution leads naturally to the class of m-band sequences of vectors in an inner product space. We study these sequences and characterize their equivalence classes under unitary transformations.     

The number of subsets without a fixed circular distance

An explicit formula is derived for the number of k-element subsets A of {1,2,…, n} such that no two elements in A are at “circular” distance q, i.e., if i ϵ A and 1 ⩽ i ⩽ n − q (resp. n − q + 1 ⩽ i ⩽ n) then i + q ∉ A (resp. i + q − n ∉ A).     

Bipartite regulation numbers

The bipartite regulation number br(G) of a bipartite graph G with maximum degree d is the minimum number of vertices required to add to G to construct a d-regular bipartite supergraph of G. It is shown that if G is a connected m-by-n bipartite graph with m ⩽ n and n − m ⩾ d − 1, then br(G) = n − m. If. however, n − m ⩽ d − 2, the br(G) = n ⇔ m + 2l for some l satisfying 0 ⩽ l ⩽ d − (n − m). Conversely, if l, k and d (>2) are integers such that 0 ⩽ l ⩽ k and 2 ⩽ k ⩽ d, then there is an connected m-by-n bipartite graph G of maximum degree d for which br(G) = n − m + 2l, for some m and n with k = d − (n −m).     

A class of facet producing graphs for vertex packing polyhedra

We examine a family of graphs called webs. For integers n ? 2 and $\text{k, 1 ? k ?}\text{1}\text{2}\text{n}$, the web W(n, k) has vertices V_n = {1, …, n} and edges {(i, j): j = i+k, …, i+n ? k, for i?V_n (sums mod n)}. A characterization is given for the vertex packing polyhedron of W(n, k) to contain a facet, none of whose projections is a facet for the lower dimensional vertex packing polyhedra of proper induced subgraphs of W(n, k). Simple necessary and sufficient conditions are given for W(n, k) to contain W(n′, k′) as an induced subgraph; these conditions are used to show that webs satisfy the Strong Perfect Graph Conjecture. Complements of webs are also studied and it is shown that if both a graph and its complement are webs, then the graph is either an odd hole or its complement.     

Some results on generalized exponents

A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V, denoted exp(u), is the least integer k such that there is a u → v walk of length k for each v ∈ V. For a set X ⊆ V, exp(X) is the least integer k such that for each v ∈ V there is a X → v walk of length k, i.e., a u → v walk of length k for some u ∈ X. Let F(G, k) : = max{exp(X) : |X| = k} and F(n, k) : = max{F(G, k) : |V| = n}, where |X| and |V| denote the number of vertices in X and V, respectively. Recently, B. Liu and Q. Li proved F(n, k) = (n − k)(n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k, 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F(G, k) = F(n, k), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G, Δ⁺(G) = max{d⁺(u) : u ∈ V}, and thus obtain a new refinement of the Wielandt bound (n − 1)² + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998     

Periodicities of partition functions and stirling numbers modulo p

If p(n, k) is the number of partitions of n into parts ≤k, then the sequence {p(k, k), p(k + 1, k),…} is periodic modulo a prime p. We find the minimum period Q = Q(k, p) of this sequence. More generally, we find the minimum period, modulo p, of {p(n; T)}_{n ≥ 0}, the number of partitions of n whose parts all lie in a fixed finite set T of positive integers. We find the minimum period, modulo p, of {S(k, k), S(k + 1, k),…}, where these are the Stirling numbers of the second kind. Some related congruences are proved. The methods involve the use of cyclotomic polynomials over Z_p[x].     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).     

Vertex-disjoint quadrilaterals containing specified edges in a bipartite graph

The theory of vertex-disjoint cycles and 2-factors of graphs is the extension and generation of the well-known Hamiltonian cycles theory and it has important applications in network communication. In this paper we first prove the following result. Let G=(V ₁,V ₂;E) be a bipartite graph with |V ₁|=|V ₂|=n such that n≥2k+1, where k≥1 is an integer. If d(x)+d(y)≥?(4n+2k?1)/3? for each pair of nonadjacent vertices x and y of G with x∈V ₁ and y∈V ₂, then, for any k independent edges e ₁,…,e _k of G, G contains k vertex-disjoint quadrilaterals C ₁,…,C _k such that e _i ∈E(C _i ) for each i∈{1,…,k}. We further show that the degree condition above is sharp. If |V ₁|=|V ₂|=2k, we give degree conditions that G has a 2-factor with k vertex-disjoint quadrilaterals C ₁,…,C _k containing specified edges of G.     

The periods of the sequences generated by some symmetric shift registers

E_k(x₂,…, x_n) is defined by E_k(a₂,…, a_n) = 1 if and only if ∑_i=2ⁿa_i = k. We determine the periods of sequences generated by the shift registers with the feedback functions x₁ + E_k(x₂,…, x_n) and x₁ + E_k(x₂,…, x_n) + E_k+1(x₂,…, x_n) over the field GF(2).     

Small cycles and 2-factor passing through any given vertices in graphs

The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ ₂(G):=min?{d(u)+d(v)|uv ? E(G),u≠v}. In the paper, the main results of this paper are as follows:

1. Let k≥2 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k of length at most four such that v _i ∈V(C _i ) for all 1≤i≤k.
2. Let k≥1 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k such that:
   1. v _i ∈V(C _i ) for all 1≤i≤k.
   2. V(C ₁)∪???∪V(C _k )=V(G), and
   3. |C _i |≤4, 1≤i≤k?1.

Moreover, the condition on σ ₂(G)≥n+2k?2 is sharp.     

Successes,runs and longest runs

The probability distribution of the number of success runs of length k (⩾1) in n (⩾1) Bernoulli trials is obtained. It is noted that this distribution is a binomial distribution of order k, and several open problems pertaining to it are stated. Let S_n and L_n, respectively, denote the number of successes and the length of the longest success run in the n Bernoulli trials. A formula is derived for the probability P(L_n ⩽ k | S_n = r) (0 ⩽ k ⩽ r ⩽ n), which is alternative to those given by Burr and Cane (1961) and Gibbons (1971). Finally, the probability distribution of X_{n, Ln}^(k) is established, where X_{n, Ln}^(k) denotes the number of times in the n Bernoulli trials that the length of the longest success run is equal to k.     

Successes,runs and longest runs

The probability distribution of the numbeer of success runs of length k ( >/ 1) in n ( ⩾ 1) Bernoulli trials is obtained. It is noted that this distribution is a binomial distribution of order k, and several open problems pertaining to it are stated. Let S_n and L_n, respectively, denote the number of successes and the length of the longest success run in the n Bernoulli trials. A formula is derived for the probability P(L_n ⩽ k | S_n = r) (0 ⩽ k ⩽ r ⩽ n), which is alternative to those given by Burr and Cane (1961) and Gibbons (1971). Finally, the probability distribution of X_{n, Ln}^(k) is established, where X_{n, Ln}^(k) denotes the number of times in the n Bernoulli trials that the length of the longest success run is equal to k.     

Properties of Regular Uniform k—Stratified Graphs

A regular graph G = (V, E) is a k-stratified graph if V is partitioned into V₁, V₂, …, V_k subsets called strata. The stratification splits the degree d_v ∀v ϵ V into k-integers d_v1, d_v2, …, d_vk each one corresponding to a stratum. If d_v1 = d_v2 = … = d_vk ∀v ϵ V then G is called regular uniform k-stratified, RU^k_s(n, d) where n is the cardinality of the vertex set in each stratum and d is the degree of every vertex in each stratum. For every k, the class RU^k_s(n, d) has a unique graph generator class RU^l_s(n, d) derived by decomposition of graphs in RU^k_s(n, d). We investigate the minimization of the cardinality of V, the colorability, vertex coloring and the diameter of the graphs in the class. We also deal with complexity questions concerning RU^k_s(n, d). Some well-known computer network models such as barrel shifters and hypercubes are shown to belong in RU^k_s(n, d).     

Hamiltonian decompositions of complete regular s-partite graphs

In this paper we give a procedure by which Hamiltonian decompositions of the s-partite graph K_n,n,…,n, where (s − 1)n is even, can be constructed. For 2t⩽s, 1⩽a₁⩽…⩽a_t⩽n, we find conditions which are necessary and sufficient for a decomposition of the edge-set of K_a1a2…,a_t into (s − 1)n/2 classes, each class consisting of disjoint paths, to be extendible to a Hamiltonian decomposition of the complete s-partite graph K_rmn,n,…,n so that each of the classes forms part of a Hamiltonian cycle.     

On 2-factors with cycles containing specified vertices in a bipartite graph

Let k≥1 be an integer and G=(V ₁,V ₂;E) a bipartite graph with |V ₁|=|V ₂|=n such that n≥2k+2. Our result is as follows: If $d(x)+d(y)\geq \lceil\frac{4n+k}{3}\rceil$ for any nonadjacent vertices x∈V ₁ and y∈V ₂, then for any k distinct vertices z ₁,…,z _k , G contains a 2-factor with k+1 cycles C ₁,…,C _k+1 such that z _i ∈V(C _i ) and l(C _i )=4 for each i∈{1,…,k}.     

Existence of triple solutions of discrete (n,p) boundary value problems

We consider the following boundary value problem: −Δⁿy = F(k,y, Δy,…,Δⁿ⁻¹y), k ϵ Z[n − 1, N], Δⁱy(0) = 0, 0 ≤ i ≤ n − 2, Δ^py(N + n - p) = 0, where n ≥ 2 and p is a fixed integer satisfying 0 ≤ p ≤ n − 1. Using a fixed-point theorem for operators on a cone, we shall yield the existence of at least three positive solutions.     

All rationals occur as exponents

For integers n ⩾k⩾ 1 and L ⊃ {0, 1,…, k − 1};, m(n, k, L) denotes the maximum number of k-subsets of an n-set so that the size of the intersection of any two among them is in L. It is proven that for every rational number r ⩾ 1 there is a choice of k and L so that cn^r < m(n, k, L) < dn^r, where c, d depend on k and L but not on n.     

Domino tilings of rectangles with fixed width

Let t(k,n) denote the number of ways to tile a 1 × n rectangle with 1 × 2 rectangles (called dominoes). We show that for each fixed k the sequence t_k=(t(k,0), t(k,1),…) satisfies a difference equation (linear, homogeneous, and with constant coefficients). Furthermore, a computational method is given for finding this difference equation together with the initial terms of the sequence. This gives rise to a new way to compute t(k,n) which differs completely with the known Pfaffian method. The generating function of t_k is a rational function F_k, and F_k is given explicitly for k=1,…,8. We end with some conjectures concerning the form of F_k based on our computations.     

Multiple vertex coverings by specified induced subgraphs

Given graphs H₁,…, H_k, let f(H₁,…, H_k) be the minimum order of a graph G such that for each i, the induced copies of H_i in G cover V(G). We prove constructively that f(H₁, H₂) ≤ 2(n(H₁) + n(H₂) − 2); equality holds when H₁ = H ₂ = K_n. We prove that f(H₁, K _n) = n + 2√δ(H₁)n + O(1) as n → ∞. We also determine f(K_{1, m −1}, K _n) exactly. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 180–190, 2000