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     

Partitions of a graph into paths with prescribed endvertices and lengths

For a graph G, let σ₂(G) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| = n = Σ^k_{i = 1} a_i and σ₂(G) ≥ n + k − 1, then for any k vertices v₁, v₂,…, v_k in G, there exist vertex‐disjoint paths P₁, P₂,…, P_k such that |V(P_i)| = a_i and v_i is an endvertex of P_i for 1 ≤ i ≤ k. In this paper, we verify the conjecture for the cases where almost all a_i ≤ 5, and the cases where k ≤ 3. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 163–169, 2000     

A characterization of panconnected graphs satisfying a local ore-type condition

It is well known that a graph G of order p ≥ 3 is Hamilton-connected if d(u) + d(v) ≥ p + 1 for each pair of nonadjacent vertices u and v. In this paper we consider connected graphs G of order at least 3 for which d(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| + 1 for any path uwv with uv ∉ E(G), where N(x) denote the neighborhood of a vertex x. We prove that a graph G satisfying this condition has the following properties: (a) For each pair of nonadjacent vertices x, y of G and for each integer k, d(x, y) ≤ k ≤ |V(G)| − 1, there is an x − y path of length k. (b) For each edge xy of G and for each integer k (excepting maybe one k η {3,4}) there is a cycle of length k containing xy. Consequently G is panconnected (and also edge pancyclic) if and only if each edge of G belongs to a triangle and a quadrangle. Our results imply some results of Williamson, Faudree, and Schelp. © 1996 John Wiley & Sons, Inc.     

Some new perfect Steiner triple systems

In a Steiner triple system STS(v) = (V, B), for each pair {a, b} ⊂ V, the cycle graph G_a,b can be defined as follows. The vertices of G_a,b are V \ {a, b, c} where {a, b, c} ∈ B. {x, y} is an edge if either {a, x, y} or {b, x, y} ∈ B. The Steiner triple system is said to be perfect if the cycle graph of every pair is a single (v − 3)-cycle. Perfect STS(v) are known only for v = 7, 9, 25, and 33. We construct perfect STS (v) for v = 79, 139, 367, 811, 1531, 25771, 50923, 61339, and 69991. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 327–330, 1999     

On low bound of degree sequences of spanning trees in K-edge-connected graphs

A graph G = (V, E) is k-edge-connected if for any subset E′ ⊆ E,|E′| < k, G − E′ is connected. A d_k-tree T of a connected graph G = (V, E) is a spanning tree satisfying that ∀v ∈ V, d_T(v) ≤ + α, where [·] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d_k-tree, and α = 1 for k = 2, α = 2 for k ≥ 3. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 87–95, 1998     

A note on graphs and sphere orders

A partially ordered set P is called a k-sphere order if one can assign to each element a ∈ P a ball B_a in R^k so that a < b iff B_a ? B_b. To a graph G = (V,E) associate a poset P(G) whose elements are the vertices and edges of G. We have v < e in P(G) exactly when v ∈ V, e ∈ E, and v is an end point of e. We show that P(G) is a 3-sphere order for any graph G. It follows from E. R. Scheinerman [“A Note on Planar Graphs and Circle Orders,” SIAM Journal of Discrete Mathematics, Vol. 4 (1991), pp. 448–451] that the least k for which G embeds in R^k equals the least k for which P(G) is a k-sphere order. For a simplicial complex K one can define P(K) by analogy to P(G) (namely, the face containment order). We prove that for each 2-dimensional simplicial complex K, there exists a k so that P(K) is a k-sphere order. © 1993 John Wiley & Sons, Inc.     

A novel use of t-packings to construct d-disjunct matrices

A t-packing is an ordered pair (V,P) where V is a v-set and P is a collection of k-subsets (blocks) of V such that each t-subset of V occurs in at most one block of P. If each t-subset of V occurs in exactly one block of P, then (V,P) is known as a Steiner (t,k,v)-design. In this paper, we explore a novel use of t-packings to construct d-disjunct matrices.     

Decomposition tree of a lexicographic product of binary structures

Given a set S and a positive integer k, a binary structure is a function . The set S is denoted by V(B) and the integer k is denoted by . With each subset X of V(B) associate the binary substructure B[X] of B induced by X defined by B[X](x,y)=B(x,y) for any x≠y∈X. A subset X of V(B) is a clan of B if for any x,y∈X and v∈V(B)?X, B(x,v)=B(y,v) and B(v,x)=B(v,y). A subset X of V(B) is a hyperclan of B if X is a clan of B satisfying: for every clan Y of B, if X∩Y≠0?, then X⊆Y or Y⊆X. With each binary structure B associate the family Π(B) of the maximal proper and nonempty hyperclans under inclusion of B. The decomposition tree of a binary structure B is constituted by the hyperclans X of B such that Π(B[X])≠0? and by the elements of Π(B[X]). Given binary structures B and C such that , the lexicographic product B⌊C⌋ of C by B is defined on V(B)×V(C) as follows. For any (x,y)≠(x^′,y^′)∈V(B)×V(C), B⌊C⌋((x,x^′),(y,y^′))=B(x,y) if x≠y and B⌊C⌋((x,x^′),(y,y^′))=C(x^′,y^′) if x=y. The decomposition tree of the lexicographic product B⌊C⌋ is described from the decomposition trees of B and C.     

Brooks-type theorems for choosability with separation

We consider the following type of problems. Given a graph G = (V, E) and lists L(v) of allowed colors for its vertices v ∈ V such that |L(v)| = p for all v ∈ V and |L(u) ∩ L(v)| ≤ c for all uv ∈ E, is it possible to find a “list coloring,” i.e., a color f(v) ∈ L(v) for each v ∈ V, so that f(u) ≠ f(v) for all uv ∈ E? We prove that every of maximum degree Δ admits a list coloring for every such list assignment, provided p ≥ . Apart from a multiplicative constant, the result is tight, as lists of length may be necessary. Moreover, for G = K_n (the complete graph on n vertices) and c = 1 (i.e., almost disjoint lists), the smallest value of p is shown to have asymptotics (1 + o(1)) . For planar graphs and c = 1, lists of length 4 suffice. ˜© 1998 John Wiley & Sons, Inc. J Graph Theory 27: 43–49, 1998     

Cycles containing all vertices of maximum degree

For a graph G and an integer k, denote by V_k the set {v ∈ V(G) | d(v) ≥ k}. Veldman proved that if G is a 2-connected graph of order n with n ≤ 3k - 2 and |V_k| ≤ k, then G has a cycle containing all vertices of V_k. It is shown that the upper bound k on |V_k| is close to best possible in general. For the special case k = δ(G), it is conjectured that the condition |V_k| ≤ k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n ≤ 2δ(G) + δ(G) + 1. This result is an almost-generalization of Jackson's Theorem that every 2-connected k-regular graph of order n with n ≤ 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented. © 1993 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     

On k-ordered Hamiltonian graphs

A Hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices of G, there exists a Hamiltonian cycle that encounters v₁, v₂, …, v_k in this order. Define f(k, n) as the smallest integer m for which any graph on n vertices with minimum degree at least m is a k-ordered Hamiltonian graph. In this article, answering a question of Ng and Schultz, we determine f(k, n) if n is sufficiently large in terms of k. Let g(k, n) = − 1. More precisely, we show that f(k, n) = g(k, n) if n ≥ 11k − 3. Furthermore, we show that f(k, n) ≥ g(k, n) for any n ≥ 2k. Finally we show that f(k, n) > g(k, n) if 2k ≤ n ≤ 3k − 6. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 17–25, 1999     

On the acyclic choosability of graphs

A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is L‐list colorable if for a given list assignment L = {L(v): v ∈ V}, there exists a proper coloring c of G such that c (v) ∈ L(v) for all v ∈ V. If G is L‐list colorable for every list assignment with |L (v)| ≥ k for all v ∈ V, then G is said k‐choosable. A graph is said to be acyclically k‐choosable if the obtained coloring is acyclic. In this paper, we study the links between acyclic k‐choosability of G and Mad(G) defined as the maximum average degree of the subgraphs of G and give some observations about the relationship between acyclic coloring, choosability, and acyclic choosability. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 281–300, 2006     

有向Kirkman填充设计的谱

§ 1　IntroductionLet X be a set of v points.A packing(directed packing) of X is a collection of subsets(ordered subsets) of X(called blocks) such that any pair(ordered pair) of distinct pointsfrom X occur together in atmostone block in the collection.A packing(directed packing)is called resolvable ifitsblock setadmitsa partition into parallel classes,each parallel classbeing a partition of the pointset X.A Kirkman triple system KTS(v) is a collection Tof3 -subsets of X(triples) suchthat …     

New upper bounds on the minimum size of covering designs

Let D = {B₁, B₂,…, B_b} be a finite family of k-subsets (called blocks ) of a v-set X(v) = {1, 2,…, v} (with elements called points ). Then D is a (v, k, t) covering design or covering if every t-subset of X(v) is contained in at least one block of D. The number of blocks, b, is the size of the covering, and the minimum size of the covering is called the covering number , denoted C(v, k, t). This article is concerned with new constructions of coverings. The constructions improve many upper bounds on the covering number C(v, k, t) © 1998 John Wiley & Sons, Inc. J Combin Designs 6:21–41, 1998     

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     

Incomplete perfect mendelsohn designs with block size 4 and holes of size 2 and 3

Let v, k, and n be positive integers. An incomplete perfect Mendelsohn design, denoted by k-IPMD(v, n), is a triple (X, Y, ??) where X is a v-set (of points), Y is an n-subset of X, and ?? is a collection of cyclically ordered k-subsets of X (called blocks) such that every ordered pair (a, b) ∈ (X × X)\(Y × Y) appears t-apart in exactly one block of ?? and no ordered pair (a,b) ∈ Y × Y appears in any block of ?? for any t, where 1 ≤ t ≤ k ? 1. In this article, the necessary conditions for the existence of a 4-IPMD(v, n), namely (v ? n) (v ? 3n ? 1) ≡ 0 (mod 4) and v ≥ 3n + 1, are shown to be sufficient for the case n = 3. For the case n = 2, these conditions are sufficient except for v = 7 and with the possible exception of v = 14,15,18,19,22,23,26,27,30. The latter result provides a useful application to the problem relating to the packing of perfect Mendelsohn designs with block size 4. © 1994 John Wiley & Sons, Inc.     

Centers to centroids in graphs

For S ? V(G) the S-center and S-centroid of G are defined as the collection of vertices u ∈ V(G) that minimize e_s(u) = max {d(u, v): v ∈ S} and d_s(u) = ∑_u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ? k ?|V(G)| and u ∈ V(G) let r_k(u) = max {∑_s∈S d(u, s): S ? V(G), |S| = k}. The k-centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which r_k(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included.     

A bound for Wilson's theorem (II)

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