Coloring 4‐cycle systems

An m‐cycle system of order n is a partition of the edges of the complete graph K_n into m‐cycles. We investigate k‐colorings of 4‐cycle systems in which no 4‐cycle is monochromatic. For any k ≥ 3, we construct a k‐chromatic 4‐cycle system. We also show that for any k ge; 2, there exists an integer w_k such that for all admissible n ≥ w_k, there is a k‐chromatic 4‐cycle system of order n. © 2005 Wiley Periodicals, Inc. J Combin Designs     

Cyclic even cycle systems of the complete graph

In this article, it is proved that for each even integer m?4 and each admissible value n with n>2m, there exists a cyclic m‐cycle system of K_n, which almost resolves the existence problem for cyclic m‐cycle systems of K_n with m even. © 2011 Wiley Periodicals, Inc. J Combin Designs 20:23–39, 2012     

All cycle‐complete graph Ramsey numbers r(Cm,K6)

The cycle‐complete graph Ramsey number r(C_m, K_n) is the smallest integer N such that every graph G of order N contains a cycle C_m on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(C_m, K_n) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C₃, K₃) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n² ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003     

Types of superregular matrices and the number of n‐arcs and complete n‐arcs in PG (r,q)

Based on the classification of superregular matrices, the numbers of non‐equivalent n‐arcs and complete n‐arcs in PG(r, q) are determined (i) for 4 ≤ q ≤ 19, 2 ≤ r ≤ q ? 2 and arbitrary n, (ii) for 23 ≤ q ≤ 32, r = 2 and n ≥ q ? 8<$>. The equivalence classes over both PGL (k, q) and PΓL(k, q) are considered throughout the examinations and computations. For the classification, an n‐arc is represented by the systematic generator matrix of the corresponding MDS code, without the identity matrix part of it. A rectangular matrix like this is superregular, i.e., it has only non‐singular square submatrices. Four types of superregular matrices are studied and the non‐equivalent superregular matrices of different types are stored in databases. Some particular results on t(r, q) and m′(r, q)—the smallest and the second largest size for complete arcs in PG(r, q)—are also reported, stating that m′(2, 31) = 22, m′(2, 32) = 24, t(3, 23) = 10, and m′(3, 23) = 16. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 363–390, 2006     

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     

A linear Vizing‐like relation relating the size and total domination number of a graph

We prove that m ≤ Δ (n ? γ_t) for every graph each component of which has order at least 3 of order n, size m, total domination number γ_t, and maximum degree Δ ≥ 3. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 285–290, 2005     

{2, 3}‐perfect m‐cycle systems are equationally defined for m = 5, 7, 8, 9, and 11 only

An m‐cycle system (S,C) of order n is said to be {2,3}‐perfect provided each pair of vertices is connected by a path of length 2 in an m‐cycle of C and a path of length 3 in an m‐cycle of C. The class of {2,3}‐perfect m‐cycle systems is said to be equationally defined provided, there exists a variety of quasigroups V with the property that a finite quasigroup (Q, , \, /) belongs to V if and only if its multiplicative (Q, ) part can be constructed from a {2,3}‐perfect m‐cycle system using the 2‐construction (a a = a for all a ∈ Q and if a ≠ b, a b = c and b a = d if and only if the m‐cycle (…, d, x, a, b, y, c, …) ∈ C). The object of this paper is to show that the class of {2,3}‐perfect m‐cycle systems cannot be equationally defined for all m ≥ 10, m ≠ 11. This combined with previous results shows that {2, 3}‐perfect m‐cycle systems are equationally defined for m = 5, 7, 8, 9, and 11 only. © 2004 Wiley Periodicals, Inc.     

Latin squares with restricted transversals

We prove that for all odd m ≥ 3 there exists a latin square of order 3 m that contains an ( m ? 1 ) × m latin subrectangle consisting of entries not in any transversal. We prove that for all even n ≥ 10 there exists a latin square of order n in which there is at least one transversal, but all transversals coincide on a single entry. A corollary is a new proof of the existence of a latin square without an orthogonal mate, for all odd orders n ≥ 11 . Finally, we report on an extensive computational study of transversal‐free entries and sets of disjoint transversals in the latin squares of order n ? 9 . In particular, we count the number of species of each order that possess an orthogonal mate. © 2011 Wiley Periodicals, Inc. J Combin Designs 20:124‐141, 2012     

Vertex pancyclic in‐tournaments

An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. The topic of this paper is to investigate vertex k‐pancyclicity of in‐tournaments of order n, where for some 3 ≤ k ≤ n, every vertex belongs to a cycle of length p for every k ≤ p ≤ n. We give sharp lower bounds for the minimum degree such that a strong in‐tournament is vertex k‐pancyclic for k ≤ 5 and k ≥ n − 3. In the latter case, we even show that the in‐tournaments in consideration are fully (n − 3)‐extendable which means that every vertex belongs to a cycle of length n − 3 and that the vertex set of every cycle of length at least n − 3 is contained in a cycle of length one greater. In accordance with these results, we state the conjecture that every strong in‐tournament of order n with minimum degree greater than is vertex k‐pancyclic for 5 < k < n − 3, and we present a family of examples showing that this bound would be best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 84–104, 2001     

Monochromatic Hamiltonian t‐tight Berge‐cycles in hypergraphs

In any r‐uniform hypergraph for 2 ≤ t ≤ r we define an r‐uniform t‐tight Berge‐cycle of length ?, denoted by C_?^{(r, t)}, as a sequence of distinct vertices v₁, v₂, … , v_?, such that for each set (v_i, v_{i + 1}, … , v_{i + t ? 1}) of t consecutive vertices on the cycle, there is an edge E_i of that contains these t vertices and the edges E_i are all distinct for i, 1 ≤ i ≤ ?, where ? + j ≡ j. For t = 2 we get the classical Berge‐cycle and for t = r we get the so‐called tight cycle. In this note we formulate the following conjecture. For any fixed 2 ≤ c, t ≤ r satisfying c + t ≤ r + 1 and sufficiently large n, if we color the edges of K_n^(r), the complete r‐uniform hypergraph on n vertices, with c colors, then there is a monochromatic Hamiltonian t‐tight Berge‐cycle. We prove some partial results about this conjecture and we show that if true the conjecture is best possible. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 34–44, 2008     

Lower bounds for lower Ramsey numbers

For any graph G, let i(G) and μ;(G) denote the smallest number of vertices in a maximal independent set and maximal clique, respectively. For positive integers m and n, the lower Ramsey number s(m, n) is the largest integer p so that every graph of order p has i(G) ≤ m or μ;(G) ≤ n. In this paper we give several new lower bounds for s (m, n) as well as determine precisely the values s(1, n).     

On cycle—Complete graph ramsey numbers

A new upper bound is given for the cycle-complete graph Ramsey number r(C_m, K_n), the smallest order for a graph which forces it to contain either a cycle of order m or a set of n independent vertices. Then, another cycle-complete graph Ramsey number is studied, namely r(?C_m, K_n) the smallest order for a graph which forces it to contain either a cycle of order / for some / satisfying 3?/?m or a set of n independent vertices. We obtain the exact value of r(?C_m K_n) for all m > n and an upper bound which applies when m is large in comparison with log n.     

A note on a conjecture about cycles with many incident chords

Given positive integers n and k, let g_k(n) denote the maximum number of edges of a graph on n vertices that does not contain a cycle with k chords incident to a vertex on the cycle. Bollobás conjectured as an exercise in [2, p. 398, Problem 13] that there exists a function n(k) such that g_k(n) = (k + 1)n ? (k + 1)² for all n ≥ n(k). Using an old result of Bondy [ 3 ], we prove the conjecture, showing that n(k) ≤ 3 k + 3. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 180–182, 2004     

Delaying satisfiability for random 2SAT

Let (C₁,C′_(*)),(C₂,C′_(*)),…,(C _m,C′_(*)) be a sequence of ordered pairs of 2CNF clauses chosen uniformly at random (with replacement) from the set of all 4 \begin{align*}\binom{n}{2}\end{align*} clauses on n variables. Choosing exactly one clause from each pair defines a probability distribution over 2CNF formulas. The choice at each step must be made on‐line, without backtracking, but may depend on the clauses chosen previously. We show that there exists an on‐line choice algorithm in the above process which results whp in a satisfiable 2CNF formula as long as m/n ≤ (1000/999)^1/4. This contrasts with the well‐known fact that a random m ‐clause formula constructed without the choice of two clauses at each step is unsatisfiable whp whenever m/n > 1. Thus the choice algorithm is able to delay satisfiability of a random 2CNF formula beyond the classical satisfiability threshold. Choice processes of this kind in random structures are known as “Achlioptas processes.” This paper joins a series of previous results studying Achlioptas processes in different settings, such as delaying the appearance of a giant component or a Hamilton cycle in a random graph. In addition to the on‐line setting above, we also consider an off‐line version in which all m clause‐pairs are presented in advance, and the algorithm chooses one clause from each pair with knowledge of all pairs. For the off‐line setting, we show that the two‐choice satisfiability threshold for k ‐SAT for any fixed k coincides with the standard satisfiability threshold for random 2k ‐SAT.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Some new HSOLSSOMs of types hn and 1m u1

In this paper, two new direct construction methods are given for holey self‐orthogonal Latin squares with a symmetric orthogonal mate (HSOLSSOMs). Some new HSOLSSOMs using already known methods are also given. The known existence results for HSOLSSOMs of types 1^m u¹ and hⁿ are improved; for type 1^m u¹ there remain just four possible exceptions with u odd and 3 ≤ u ≤ 15; for type hⁿ, there are just two possible exceptions remaining, for (h, n) = (6, 12) and (6, 18). As a byproduct, the known existence results for three holey mutually orthogonal Latin squares (3 HMOLS) are also improved. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 435–444, 2001     

Total domination in 2‐connected graphs and in graphs with no induced 6‐cycles

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γ_t(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γ_t(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γ_t(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009     

Comparison of Some Purities,Flatnesses and Injectivities

In this article, we compare (n, m)-purities for different pairs of positive integers (n, m). When R is a commutative ring, these purities are not equivalent if R does not satisfy the following property: there exists a positive integer p such that, for each maximal ideal P, every finitely generated ideal of R _P is p-generated. When this property holds, then the (n, m)-purity and the (n, m′)-purity are equivalent if m and m′ are integers ≥np. These results are obtained by a generalization of Warfield's methods. There are also some interesting results when R is a semiperfect strongly π-regular ring. We also compare (n, m)-flatnesses and (n, m)-injectivities for different pairs of positive integers (n, m). In particular, if R is right perfect and right self (?₀, 1)-injective, then each (1, 1)-flat right R-module is projective. In several cases, for each positive integer p, all (n, p)-flatnesses are equivalent. But there are some examples where the (1, p)-flatness is not equivalent to the (1, p + 1)-flatness.     

Pancyclic arcs and connectivity in tournaments

A tournament is an orientation of the edges of a complete graph. An arc is pancyclic in a tournament T if it is contained in a cycle of length l, for every 3 ≤ l ≤ |T|. Let p(T) denote the number of pancyclic arcs in a tournament T. In 4 , Moon showed that for every non‐trivial strong tournament T, p(T) ≥ 3. Actually, he proved a somewhat stronger result: for any non‐trivial strong tournament h(T) ≥ 3 where h(T) is the maximum number of pancyclic arcs contained in the same hamiltonian cycle of T. Moreover, Moon characterized the tournaments with h(T) = 3. All these tournaments are not 2‐strong. In this paper, we investigate relationship between the functions p(T) and h(T) and the connectivity of the tournament T. Let p_k(n) := min {p(T), T k‐strong tournament of order n} and h_k(n) := min{h(T), T k‐strong tournament of order n}. We conjecture that (for k ≥ 2) there exists a constant α_k> 0 such that p_k(n) ≥ α_kn and h_k(n) ≥ 2k+1. In this paper, we establish the later conjecture when k = 2. We then characterized the tournaments with h(T) = 4 and those with p(T) = 4. We also prove that for k ≥ 2, p_k(n) ≥ 2k+3. At last, we characterize the tournaments having exactly five pancyclic arcs. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 87–110, 2004     

Degree conditions for k‐ordered hamiltonian graphs

For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. It is shown that if G is a graph of order n with 3 ≤ k ≤ n/2, and deg(u) + deg(v) ≥ n + (3k − 9)/2 for every pair u, v of nonadjacent vertices of G, then G is k-ordered hamiltonian. Minimum degree conditions are also given for k-ordered hamiltonicity. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 199–210, 2003     

Continuous k‐to‐1 functions between complete graphs whose orders are of a different parity

A function between graphs is k‐to‐1 if each point in the codomain has precisely k pre‐images in the domain. Given two graphs, G and H, and an integer k≥1, and considering G and H as subsets of ?³, there may or may not be a k‐to‐1 continuous function (i.e. a k‐to‐1 map in the usual topological sense) from G onto H. In this paper we consider graphs G and H whose order is of a different parity and determine the even and odd values of k for which there exists a k‐to‐1 map from G onto H. We first consider k‐to‐1 maps from K_2r onto K_2s+1 and prove that for 1≤r≤s, (r, s)≠(1, 1), there is a continuous k‐to‐1 map for k even if and only if k≥2s and for k odd if and only if k≥?s?_o (where ?s?_o indicates the next odd integer greater than or equal to s). We then consider k‐to‐1 maps from K_2s+1 onto K_2s. We show that for 1≤r<s, such a map exists for even values of k if and only if k≥2s. We also prove that whatever the values of r and s are, no such k‐to‐1 map exists for odd values of k. To conclude, we give all triples (n, k, m) for which there is a k‐to‐1 map from K_n onto K_m in the case when n≤m. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 35–60, 2010.