Embedding partial odd‐cycle systems in systems with orders in all admissible congruence classes

For odd m, relatively little is known about embedding partial m‐cycle systems into m‐cycle systems of small orders not congruent to 1 or m modulo 2m. In this paper we prove that any partial m‐cycle system of order u can be embedded in an m‐cycle system of order v if v≥m(2u+1)+(m?1)/2, v is odd and $\left( {_{2}^{V} } \right) \equiv 0\left( {\bmod {\rm }m} \right)$. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 202–208, 2010     

A conjecture on small embeddings of partial Steiner triple systems

A well‐known, and unresolved, conjecture states that every partial Steiner triple system of order u can be embedded in a Steiner triple system of order υ for all υ ≡ 1 or 3, (mod 6), υ ≥ 2u + 1. However, some partial Steiner triple systems of order u can be embedded in Steiner triple systems of order υ <2u + 1. A more general conjecture that considers these small embeddings is presented and verified for some cases. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 313–321, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10017     

Embeddings of resolvable mendelsohn triple systems

In this article it is shown that any resolvable Mendelsohn triple system of order u can be embedded in a resolvable Mendelsohn triple system of order v iff v≥ 3u, except possibly for 71 values of (u,v). © 1993 John Wiley & Sons, Inc.     

Edge disjoint Hamilton cycles in graphs

Let G be a graph of order n and k ≥ 0 an integer. It is conjectured in [8] that if for any two vertices u and v of a 2(k + 1)‐connected graph G,d _G (u,v) = 2 implies that max{d(u;G), d(v;G)} ≥ (n/2) + 2k, then G has k + 1 edge disjoint Hamilton cycles. This conjecture is true for k = 0, 1 (see cf. [3] and [8]). It will be proved in this paper that the conjecture is true for every integer k ≥ 0. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 8–20, 2000     

Quasi‐embeddings of Steiner triple systems,or Steiner triple systems of different orders with maximum intersection

In this paper, we present a conjecture that is a common generalization of the Doyen–Wilson Theorem and Lindner and Rosa's intersection theorem for Steiner triple systems. Given u, v ≡ 1,3 (mod 6), u < v < 2u + 1, we ask for the minimum r such that there exists a Steiner triple system such that some partial system can be completed to an STS , where |?| = r. In other words, in order to “quasi‐embed” an STS(u) into an STS(v), we must remove r blocks from the small system, and this r is the least such with this property. One can also view the quantity (u(u ? 1)/6) ? r as the maximum intersection of an STS(u) and an STS(v) with u < v. We conjecture that the necessary minimum r = (v ? u) (2u + 1 ? v)/6 can be achieved, except when u = 6t + 1 and v = 6t + 3, in which case it is r = 3t for t ≠ 2, or r = 7 when t = 2. Using small examples and recursion, we solve the cases v ? u = 2 and 4, asymptotically solve the cases v ? u = 6, 8, and 10, and further show for given v ? u > 2 that an asymptotic solution exists if solutions exist for a run of consecutive values of u (whose required length is no more than v ? u). Some results are obtained for v close to 2u + 1 as well. The cases where ≈ 3u/2 seem to be the hardest. © 2004 Wiley Periodicals, Inc.     

Embeddings of Sλ(2, 4, v)

It is shown that the necessary condition for a given S_λ(2,4,u) to be embedded in some S_λ(2,4,v) as a subdesign, namely v ≥ 3u + 1, is also sufficient for the case of λ = 6. Combining this with the previously known results gives the same sufficiency for any positive integer λ. © 1994 John Wiley & Sons, Inc.     

Embedding Partial 4-cycle Systems of Arbitrary Index

Recently, Lindner showed that every partial 4-cycle system of order n and index 1 could be embedded in a 4-cycle system of order ν and index 1 with v ≤ 2n + 15. While the technique he used does not immediately extend to any higher index, here we develop his ideas to show that every partial 4-cycle system of order n and index λ can be embedded in a 4-cycle system of order v and index λ for all λ-admissible . This improves on the best known bounds of v = 4n and v = 8n + 1 when λ > 1 is even and odd respectively.     

Rotational k‐cycle systems of order v < 3k; another proof of the existence of odd cycle systems

We give an explicit solution to the existence problem for 1‐rotational k‐cycle systems of order v < 3k with k odd and v ≠ 2k + 1. We also exhibit a 2‐rotational k‐cycle system of order 2k + 1 for any odd k. Thus, for k odd and any admissible v < 3k there exists a 2‐rotational k‐cycle system of order v. This may also be viewed as an alternative proof that the obvious necessary conditions for the existence of odd cycle systems are also sufficient. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 433–441, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10061     

Degree bounds for the circumference of 3‐connected graphs

Let C be a longest cycle in the 3‐connected graph G and let H be a component of G ? V(C) such that |V(H)| ≥ 3. We supply estimates of the form |C| ≥ 2d(u) + 2d(v) ? α(4 ≤ α ≤ 8), where u,v are suitably chosen non‐adjacent vertices in G. Also the exceptional classes for α = 6,7,8 are characterized. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On large sets of almost Hamilton cycle decompositions

A large set of CS(v, k, λ), k‐cycle system of order v with index λ, is a partition of all k‐cycles of K_v into CS(v, k, λ)s, denoted by LCS(v, k, λ). A (v ? 1)‐cycle is called almost Hamilton. The completion of the existence spectrum for LCS(v, v ? 1, λ) only depends on one case: all v ≥ 4 for λ = 2. In this article, it is shown that there exists an LCS(v, v ? 1,2) for any v ≡ 0,1 (mod 4) except v = 5, and for v = 6,7,10,11. © 2006 Wiley Periodicals, Inc. J Combin Designs 16: 53–69, 2008     

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.     

Even graphs

A nontrivial connected graph G is called even if for each vertex v of G there is a unique vertex v such that d(v, v ) = diam G. Special classes of even graphs are defined and compared to each other. In particular, an even graph G is called symmetric if d(u, v) + d(u, v ) = diam G for all u, v ∈ V(G). Several properties of even and symmetric even graphs are stated. For an even graph of order n and diameter d other than an even cycle it is shown that n ≥ 3d – 1 and conjectured that n ≥ 4d – 4. This conjecture is proved for symmetric even graphs and it is shown that for each pair of integers n, d with n even, d ≥ 2 and n ≥ 4d – 4 there exists an even graph of order n and diameter d. Several ways of constructing new even graphs from known ones are presented.     

Enclosings of λ-fold 4-cycle systems

In this paper we solve the problem of enclosing a λ-fold 4-cycle system of order v into a (λ + m)-fold 4-cycle system of order v + u for all m > 0 and u ≥ 1. An ingredient is constructed that is of interest on its own right, namely the problem of finding equitable partial 4-cycle systems of λ K _v . This supplementary solution builds on a result of Raines and Staniszlo.     

A proof of Lindner's conjecture on embeddings of partial Steiner triple systems

Lindner's conjecture that any partial Steiner triple system of order u can be embedded in a Steiner triple system of order v if and is proved. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 63–89, 2009     

On circuits and pancyclic line graphs

Clark proved that L(G) is hamiltonian if G is a connected graph of order n ≥ 6 such that deg u + deg v ≥ n – 1 – p(n) for every edge uv of G, where p(n) = 0 if n is even and p(n) = 1 if n is odd. Here it is shown that the bound n – 1 – p(n) can be decreased to (2n + 1)/3 if every bridge of G is incident with a vertex of degree 1, which is a necessary condition for hamiltonicity of L(G). Moreover, the conclusion that L(G) is hamiltonian can be strengthened to the conclusion that L(G) is pancyclic. Lesniak-Foster and Williamson proved that G contains a spanning closed trail if |V(G)| = n ≥ 6, δ(G) ≥ 2 and deg u + deg v ≥ n – 1 for every pair of nonadjacent vertices u and v. The bound n – 1 can be decreased to (2n + 3)/3 if G is connected and bridgeless, which is necessary for G to have a spanning closed trail.     

Embeddings of pure mendelsohn triple systems and pure directed triple systems

It is proved in this article that the necessary and sufficient conditions for the embedding of a λ-fold pure Mendelsohn triple system of order v in λ-fold pure Mendelsohn triple of order u are λu(u ? 1) ≡ 0 (mod 3) and u ? 2v + 1. Similar results for the embeddings of pure directed triple systems are also obtained. © 1995 John Wiley & Sons, Inc.     

Embedding partial totally symmetric quasigroups

This paper concerns the embedding problem for partial totally symmetric quasigroups. For all n?9, it is shown that any partial totally symmetric quasigroup of order n can be embedded in a totally symmetric quasigroup of order v if v is even and v?2n+4, and this is the best possible such inequality.     

两类广义Petersen 图的Euler亏格

广义 Petersen 图 P(n, m) 是这样的一个图:它的顶点集是{u_i, v_i | i=0,1, ^… , n-1}, 边集是 {u_iu_i+1, v_iv_i+m, u_iv_i | i=0,1, ^…, n-1}, 这里 m, n 是正整数、加法是在模n 下且 m<|n/2| . 这篇文章证明了P(2m+1, m)(m≥ 2) 的 Euler 亏格是1, 并且 P(2m+2, m)(m≥ 5) 的 Euler 亏格是2.     

General exact solutions for linear and nonlinear waves in a Thirring model

In the present paper, we construct exact solutions to a system of partial differential equations iu_x + v + u | v | ² = 0, iv_t + u + v | u | ² = 0 related to the Thirring model. First, we introduce a transform of variables, which puts the governing equations into a more useful form. Because of symmetries inherent in the governing equations, we are able to successively obtain solutions for the phase of each nonlinear wave in terms of the amplitudes of both waves. The exact solutions can be described as belonging to two classes, namely, those that are essentially linear waves and those which are nonlinear waves. The linear wave solutions correspond to waves propagating with constant amplitude, whereas the nonlinear waves evolve in space and time with variable amplitudes. In the traveling wave case, these nonlinear waves can take the form of solitons, or solitary waves, given appropriate initial conditions. Once the general solution method is outlined, we focus on a number of more specific examples in order to show the variety of physical solutions possible. We find that radiation naturally emerges in the solution method: if we assume one of u or v with zero background, the second wave will naturally include both a solitary wave and radiation terms. The solution method is rather elegant and can be applied to related partial differential systems. Copyright © 2014 John Wiley & Sons, Ltd.     

On the structure of extremal graphs of high girth

Let n ≥ 3 be a positive integer, and let G be a simple graph of order v containing no cycles of length smaller than n + 1 and having the greatest possible number of edges (an extremal graph). Does G contain an n + 1-cycle? In this paper we establish some properties of extremal graphs and present several results where this question is answered affirmatively. For example, this is always the case for (i) v ≥ 8 and n = 5, or (ii) when v is large compared to n: v ≥ , where a = n - 3 - , n ≥ 12. On the other hand we prove that the answer to the question is negative for v = 2n + 2 ≥ 26. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 147–153, 1997