A bound for wilson's theorem (I)

In 1975, Richard M. Wilson proved: Given any positive integers k ? 3 and λ, there exists a constant v⁰ = v⁰(k, λ) such that v ? B(k,λ) for every integer v ? v⁰ that satisfies λ(v ? 1) ≡ 0(mod k ? 1) and λv(v ? 1) ≡ 0[mod k(k ? 1)]. The proof given by Wilson does not provide an explicit value of v⁰. We try to find such a value v⁰(k, λ). In this article we consider the case λ = 1 and v ≡ 1[mod k(k ? 1)]. We show that: if k ? 3 and v = 1[mod k(k ? 1)] where v > k^kk5, then a B(v,k, 1) exists. © 1995 John Wiley & Sons, Inc.     

Self-converse Mendelsohn designs with block size 4t + 2

A Mendelsohn design MD(v, k, λ) is a pair (X, B) where X is a v-set together with a collection B of cyclic k-tuples from X such that each ordered pair from X, as adjacent entries, is contained in exactly λk-tuples of B. An MD(v, k, λ) is said to be self-converse, denoted by SCMD(v, k, λ) = (X, B, f), if there is an isomorphic mapping from (X, B) to (X, B⁻¹), where B⁻¹ = {B⁻¹ = 〈x_k, x_k−1, … x₂, x₁〉; B = 〈x₁, … ,x_k〉 ∈ B.}. The existence of SCMD(v, 3, λ) and SCMD(v, 4, 1) has been settled by us. In this article, we will investigate the existence of SCMD(v, 4t + 2, 1). In particular, when 2t + 1 is a prime power, the existence of SCMD(v, 4t + 2, 1) has been completely solved, which extends the existence results for MD(v, k, 1) as well. © 1999 John Wiley & Sons, Inc. J. Combin Designs 7: 283–310, 1999     

A bound for Wilson's theorem (III)

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

Acyclic 5‐choosability of planar graphs without small cycles

A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L‐list colorable if for a given list assignment L = {L(v): v: ∈ V}, there exists a proper acyclic coloring ? of G such that ?(v) ∈ L(v) for all v ∈ V. If G is acyclically L‐list colorable for any list assignment with |L (v)|≥ k for all v ∈ V, then G is acyclically k‐choosable. In this article, we prove that every planar graph G without 4‐ and 5‐cycles, or without 4‐ and 6‐cycles is acyclically 5‐choosable. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 245–260, 2007     

Self‐converse Mendelsohn designs with block size 4 and 5

A (v, k, λ)‐Mendelsohn design(X, ℬ︁) is called self‐converse if there is an isomorphic mapping ƒ from (X, ℬ︁) to (X, ℬ︁⁻¹), where ℬ︁⁻¹ = {B⁻¹ = 〈x_k, x_k−1,…,x₂, x₁〉: B = 〈x₁, x₂,…,x_k−1, x_k〉 ϵ ℬ︁}. In this paper, we give the existence spectrum for self‐converse (v, 4, 1)– and (v, 5, 1)– Mendelsohn designs. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 411–418, 2000     

Block designs with large holes and α -resolvable BIBDs

In a (v, k, λ: w) incomplete block design (IBD) (or PBD [v, {k, w^*}. λ]), the relation v ≥ (k ? 1)w + 1 must hold. In the case of equality, the IBD is referred to as a block design with a large hole, and the existence of such a configuration is equivalent to the existence of a λ-resolvable BIBD(v ? w, k ? 1, λ). The existence of such configurations is investigated for the case of k = 5. Necessary and sufficient conditions are given for all v and λ ? 2 (mod 4), and for λ ≡ 2 mod 4 with 11 possible exceptions for v. © 1993 John Wiley & Sons, Inc.     

Planar graphs without 4‐cycles are acyclically 6‐choosable

A proper vertex coloring of a graph G=(V, E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L‐list colorable if for a given list assignment L={L(v)|v∈V}, there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L‐list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k‐choosable. In this paper we prove that every planar graph G without 4‐cycles is acyclically 6‐choosable. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 307–323, 2009     

Alternating groups and flag‐transitive 2‐(v,k, 4) symmetric designs

In this article, we study the classification of flag‐transitive, point‐primitive 2‐ (v, k, 4) symmetric designs. We prove that if the socle of the automorphism group G of a flag‐transitive, point‐primitive nontrivial 2‐ (v, k, 4) symmetric design ?? is an alternating group A_n for n≥5, then (v, k) = (15, 8) and ?? is one of the following: (i) The points of ?? are those of the projective space PG(3, 2) and the blocks are the complements of the planes of PG(3, 2), G = A₇ or A₈, and the stabilizer G_x of a point x of ?? is L₃(2) or AGL₃(2), respectively. (ii) The points of ?? are the edges of the complete graph K₆ and the blocks are the complete bipartite subgraphs K_{2, 4} of K₆, G = A₆ or S₆, and G_x = S₄ or S₄ × Z₂, respectively. © 2011 Wiley Periodicals, Inc. J Combin Designs 19:475‐483, 2011     

On large sets of Pk‐decompositions

Let G = (V(G),E(G)) be a graph. A (ν, G, λ)‐GD is a partition of all the edges of λK_ν into subgraphs (G‐blocks), each of which is isomorphic to G. The (ν, G, λ)‐GD is named as graph design for G or G‐decomposition. The large set of (ν, G, λ)‐GD is denoted by (ν, G, λ)‐LGD. In this paper, we obtain a general result by using the finite fields, that is, if q ≥ k ≥ 2 is an odd prime power, then there exists a (q,P_k, k ? 1)‐LGD. © 2005 Wiley Periodicals, Inc. J Combin Designs.     

A new class for large sets of almost Hamilton cycle decompositions

A k-cycle system of order v with index λ, denoted by CS(v, k, λ), is a collection A of k-cycles (blocks) of K _v such that each edge in K _v appears in exactly λ blocks of A. A large set of CS(v, k, λ)s is a partition of the set of all k-cycles of K _v into CS(v, k, λ)_s, and is denoted by LCS(v, k, λ). A (v ?1)-cycle in K _v is called almost Hamilton. The completion of the existence problem for LCS(v, v?1, λ) depends only on one case: all v ≥ 4 for λ = 2. In this paper, it is shown that there exists an LCS(v, v ? 1, 2) for all v ≡ 2 (mod 4), v ≥ 6.     

Two‐factors each component of which contains a specified vertex

It is shown that if G is a graph of order n with minimum degree δ(G), then for any set of k specified vertices {v₁,v₂,…,v_k} ? V(G), there is a 2‐factor of G with precisely k cycles {C₁,C₂,…,C_k} such that v_i ∈ V(C_i) for (1 ≤ i ≤ k) if or 3k + 1 ≤ n ≤ 4k, or 4k ≤ n ≤ 6k ? 3,δ(G) ≥ 3k ? 1 or n ≥ 6k ? 3, . Examples are described that indicate this result is sharp. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 188–198, 2003     

A small generating set for the 3‐BD closed set of block sizes ≥ 6

Let v, k be positive integers and k ≥ 3, then K_k = : {v: v ≥ k} is a 3‐BD closed set. Two finite generating sets of 3‐BD closed sets K₄ and K₅ are obtained by H. Hanani [5] and Qiurong Wu [12] respectively. In this article we show that if v ≥ 6, then v ∈ B₃(K,1), where K = {6,7,…,41,45,46,47,51,52,53,83,84}\{22,26}; that is, we show that K is a generating set for K₆. Finally we show that v ∈ B₃(6,20) for all v ∈ K\{35,39,40,45}. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 128–136, 2008     

Upper bounds on the general covering number Cλ(v,k, t,m)

A collection of k‐subsets (called blocks) of a v‐set X (v) = {1, 2,…, v} (with elements called points) is called a t‐(v, k, m, λ) covering if for every m‐subset M of X (v) there is a subcollection of with such that every block K ∈ has at least t points in common with M. It is required that v ≥ k ≥ t and v ≥ m ≥ t. The minimum number of blocks in a t‐(v, k, m, λ) covering is denoted by C_λ(v, k, t, m). We present some constructions producing the best known upper bounds on C_λ(v, k, t, m) for k = 6, a parameter of interest to lottery players. © 2004 Wiley Periodicals, Inc.     

List Colorings of K5‐Minor‐Free Graphs With Special List Assignments

The following question was raised by Bruce Richter. Let G be a planar, 3‐connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), 6} for all v∈V(G)? More generally, we ask for which pairs (r, k) the following question has an affirmative answer. Let r and k be the integers and let G be a K₅‐minor‐free r‐connected graph that is not a Gallai tree (i.e. at least one block of G is neither a complete graph nor an odd cycle). Is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), k} for all v∈V(G)? We investigate this question by considering the components of G[S_k], where S_k: = {v∈V(G)|d(v)8k} is the set of vertices with small degree in G. We are especially interested in the minimum distance d(S_k) in G between the components of G[S_k]. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:18–30, 2012     

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.     

Long cycles passing through a specified path in a graph

For a graph G and an integer k ≥ 1, let ς_k(G) = d_G(v_i): {v₁, …, v_k} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς₂(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998     

Support sizes of threefold resolvable triple systems

Let SS_R(v, 3) denote the set of all integer b* such that there exists a RTS(v, 3) with b* distinct triples. In this paper, we determine the set SS_R(v, 3) for v ≡ 3 (mod 6) and v ≥ 3 with only five undecided cases. We establish that SS_R(v, 3) = P(v, 3) for v ≡ 3 (mod 6), v ≥ 21 and v ≠ 33, 39 where P(v, 3) = {m_v, m_v + 4, m_v + 6, m_v + 7, …, 3m_v} and m_v, = v(v ? 1)/6. As a by‐product, we remove the last two undecided cases for the intersection numbers of Kirkman triple system of order 27, this improves the known result provided in [ 2 ]. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 275–289, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10037     

P 4k−1-factorization of bipartite multigraphs

Let λK _m,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A P _v-factorization of λK _m,n is a set of edge-disjoint P _v -factors of λK _m,n which partition the set of edges of λK _m,n. When v is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P _v -factorization of λK _m,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true for v = 3. In this paper we will show that the conjecture is true when v = 4k ? 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P _4k?1-factorization of λK _m,n is (1) (2k ? 1)m ? 2kn, (2) (2k ? 1)n ? 2km, (3) m + n ≡ 0 (mod 4k ? 1), (4) λ(4k ? 1)mn/[2(2k ? 1)(m + n)] is an integer.     

Existence results for near resolvable designs

A near resolvable design, NRB(v, k), is a balanced incomplete block design whose block set can be partitioned into v classes such that each class contains every point of the design but one, and each point is missing from exactly one class. The necessary conditions for the existence of near resolvable designs are v ≡ 1 mod k and λ = k ? 1. These necessary conditions have been shown to be sufficient for k ? {2,3,4} and almost always sufficient for k ? {5,6}. We are able to show that there exists an integer n₀(k) so that NRB(v,k) exist for all v > n₀(k) and v ≡ 1 mod k. Using some new direct constructions we show that there are many k for which it is easy to compute an explicit bound on n₀(k). These direct constructions also allow us to build previously unknown NRB(v,5) and NRB(v,6). © 1995 John Wiley & Sons, Inc.     

A note on traversing specified vertices in graphs embedded with large representativity

A graph G is said to have property P(2,k) if given any k+2 distinct vertices a,b,v₁,…,v_k, there is a path P in G joining a and b and passing through all of v₁,…,v_k. A graph G is said to have property C(k) if given any k distinct vertices v₁,…,v_k, there is a cycle C in G containing all of v₁,…,v_k. It is shown that if a 4-connected graph G is embedded in an orientable surface Σ (other than the sphere) of Euler genus eg(G,Σ), with sufficiently large representativity (as a function of both eg(G,Σ) and k), then G possesses both properties P(2,k) and C(k).