An analogue of group divisible designs for Moore graphs

We study graphs whose adjacency matrix S of order n satisfies the equation S + S² = J ? K + kI, where J is a matrix of order n of all 1's, K is the direct sum on $\text{n}\text{l}$ matrices of order l of all 1's, and I is the identity matrix. Moore graphs are the only solutions to the equation in the case l = 1 for which K = I. In the case k = l we can obtain Moore graphs from a solution S by a bordering process analogous to obtaining (ν, κ, λ)-designs from some group divisible designs. Other parameters are rare. We are able to find one new interesting graph with parameters k = 6, l = 4 on n = 40 vertices. We show that it has a transitive automorphism group isomorphic to C₄ × S₅.     

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.     

The factors of a design matrix

Let X and Y be integral matrices of order n > 1 and suppose that these matrices satisfy the matrix equation XY = B, where B is a matrix with k in the n main diagonal positions and λ and μ in all other positions. Suppose further that k, λ, and μ are nonnegative integers and that λ occurs exactly the same number of times in each line of B and that a similar situation holds for μ. We call X and Y the factors of the design matrix B. The matrix equation described above embraces a vast category of combinatorial configurations that are characterized by square incidence matrices. We investigate the factors of design matrices and prove a duality theorem for the factors of certain “quadratic” design matrices. This result may be regarded as a strong generalization of Connor's duality theorem on symmetric group divisible designs. We conclude with a brief discussion of certain special factors of design matrices that are of particular interest to us.     

Ramsey graphs and block designs

Symmetric (ν, κ, λ)-block designs admitting polarity maps are shown to be closely related to certain Ramsey numbers for bipartite graphs. In particular, if there exists a (ν, κ, λ)-difference set in an abelian group of order ν, then the Ramsey number R(K_2,λ+1, K_1,ν?k+1) is either 1 + ν or 2 + ν.     

Regular orientable imbeddings of complete graphs

This paper classifies the regular imbeddings of the complete graphs K_n in orientable surfaces. Biggs showed that these exist if and only if n is a prime power p^e, his examples being Cayley maps based on the finite field F = GF(n). We show that these are the only examples, and that there are $\text{φ(n ? 1)}\text{e}$ isomorphism classes of such maps (where φ is Euler's function), each corresponding to a conjugacy class of primitive elements of F, or equivalently to an irreducible factor of the cyclotomic polynomial Φ_{n ? 1}(z) over GF(p). We show that these maps are all equivalent under Wilson's map-operations H_i, and we determined for which n they are reflexible or self-dual.     

Some mutually disjoint steiner systems

A t-design λ; t-d-n is a system of subsets of size d (called blocks) from an n-set S, such that each t-subset from S is contained in precisely λ blocks. A Steiner system S(l, m, n) is a t-design with parameters 1; l-m-n. Two Steiner systems (or t-designs) are disjoint if they share no blocks. A search has been conducted which resulted in discovering 9 mutually disjoint S(5, 8, 24)'s, 24 mutually disjoint S(4, 7, 23)'s, 60 mutually disjoint S(3, 6, 22)'s, and 197 mutually disjoint S(2, 5, 21)'s. Taking unions of several mutually disjoint Steiner systems will then produce t-designs (with varying λ's) on 21, 22, 23, and 24 points.     

An existence theory for pairwise balanced designs,III: Proof of the existence conjectures

Given positive integers k and λ, balanced incomplete block designs on v points with block size k and index λ exist for all sufficiently large integers v satisfying the congruences λ(v ? 1) ≡ 0 (mod k ? 1) and λv(v ? 1) ≡ 0 (mod k(k ? 1)). Analogous results hold for pairwise balanced designs where the block sizes come from a given set K of positive integers. We also observe that the number of nonisomorphic designs on v points with given block size k > 2 and index λ tends to infinity as v increases (subject to the above congruences).     

Two characterizations of interchange graphs of complete m-partite graphs

A graph G is m-partite if its points can be partitioned into m subsets V₁,…,V_m such that every line joins a point in V_i with a point in V_j, i ≠ j. A complete m-partite graph contains every line joining V_i with V_j. A complete graph K_p has every pair of its p points adjacent. The nth interchange graph I_n(G) of G is a graph whose points can be identified with the K_n+1's of G such that two points are adjacent whenever the corresponding K_n+1's have a K_n in common.Interchange graphs of complete 2-partite and 3-partite graphs have been characterized, but interchange graphs of complete m-partite graphs for m > 3 do not seem to have been investigated. The main result of this paper is two characterizations of interchange graphs of complete m-partite graphs for m ≥ 2.     

On the separation power and the completion of partial latin squares

Let n and m be natural numbers, n ? m. The separation power of order n and degree m is the largest integer k = k(n, m) such that for every (0, 1)-matrix A of order n with constant linesums equal to m and any set of k 1's in A there exist (disjoint) permutation matrices P₁,…, P_m such that A = P₁ + … + P_m and each of the k 1's lies in a different P_i. Almost immediately we have 1 ? k(n, m) ? m ? 1, yet in all cases where the value of k(n, m) is actually known it equals m ? 1 (except under the somewhat trivial circumstances of k(n, m) = 1). This leads to a conjecture about the separation power, namely that k(n, m) = m ? 1 if $\text{m ? [}\text{n}\text{2}\text{] + 1}$. We obtain the bound $\text{k(n, m) ? m ? [}\text{n}\text{2}\text{] + 2}$, so that this conjecture holds for n ? 7. We then move on to latin squares, describing several equivalent formulations of the concept. After establishing a sufficient condition for the completion of a partial latin square in terms of the separation power, we can show that the Evans conjecture follows from this conjecture about the separation power. Finally the lower bound on k(n, m) allows us to show, after some calculations, that the Evans conjecture is true for orders n ? 11.     

Spanning 3-ended trees in k-connected K 1,4-free graphs

A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree.     

Strongly regular graphs and finite Ramsey theory

Some connections between strongly regular graphs and finite Ramsey theory are drawn. Let B_n denote the graph K₂+K?_n. If there exists a strongly regular graph with parameters (υ, k, λ, μ), then the Ramsey number r(B_λ+1, B_{υ?2k+μ ?1})?υ+1. We consider the implications of this inequality for both Ramsey theory and the theory of strongly regular graphs.     

A classification of 4-connected graphs

Having observed Tutte's classification of 3-connected graphs as those attainable from wheels by line addition and point splitting and Hedetniemi's classification of 2-connected graphs as those obtainable from K₂ by line addition, subdivision and point addition, one hopes to find operations which classify n-connected graphs as those obtainable from, for example, K_n+1. In this paper I give several generalizations of the above operations and use Halin's theorem to obtain two variations of Tutte's theorem as well as a classification of 4-connected graphs.     

Enumeration of self-complementary structures

For functions f : D → R_k where D is a finite set and R_k = {0,1,… k} we define complementary and self-complementary functions. De Bruijn's generalization of Polya's theorem gives a formula for the number of non-isomorphic self-complementary functions $\text{f ∈ R}{}_{\mathrm{k}}{}^{\mathrm{D}}$. We consider the special cases of generalized graphs and m-placed relations. Among other results we prove that the number of non-isomorphic self-complementary relations over 2n elements is equal to the number of non-isomorphic self-complementary graphs with 4n + 1 points.     

Balanced Incomplete Block Designs with Block Size 9 and λ=2,4,8

The necessary conditions for the existence of a balanced incomplete block design on v points, with index λ and block size k, are that: $$\begin{gathered} {\text{ }}\lambda (v - 1) \equiv 0{\text{ mod (}}k - 1{\text{)}} \hfill \\ \lambda v(v - 1) \equiv 0{\text{ mod (}}k - 1{\text{)}} \hfill \\ \end{gathered} $$ In this paper we study k=9 with λ=2,4 or 8. For λ=8, we show these conditions on v are sufficient, and for λ=2, 4 respectively there are 8 and 3 possible exceptions the largest of which are v=1845 and 783. We also give some examples of group divisible designs derived from balanced ternary designs.     

Non-cover generalized Mycielski, Kneser, and Schrijver graphs

A graph is said to be a cover graph if it is the underlying graph of the Hasse diagram of a finite partially ordered set. We prove that the generalized Mycielski graphs M_m(C_2t+1) of an odd cycle, Kneser graphs KG(n,k), and Schrijver graphs SG(n,k) are not cover graphs when m?0,t?1, k?1, and n?2k+2. These results have consequences in circular chromatic number.     

Intersection theorems for group divisible difference sets

Let D be an (m,n;k;λ₁,λ₂)-group divisible difference set (GDDS) of a group G, written additively, relative to H, i.e. D is a k-element subset of G, H is a normal subgroup of G of index m and order n and for every nonzero element g of G,?{(d₁,d₂)?,d₁,d₂?D,d₁?d₂=g}? is equal to λ₁ if g is in H, and equal to λ₂ if g is not in H. Let H₁,H₂,…,H_m be distinct cosets of H in G and S_i=D∩H_i for all i=1,2,…,m. Some properties of S₁,S₂,…,S_m are studied here. Table 1 shows all possible cardinalities of S_i's when the order of G is not greater than 50 and not a prime. A matrix characterization of cyclic GDDS's with λ₁=0 implies that there exists a cyclic affine plane of even order, say n, only if n is divisible by 4 and there exists a cyclic (n?1,$\text{1}\text{2}$n?1,$\text{1}\text{4}$n?1)-difference set.     

Non-Hamiltonian simple 3-polytopes having just two types of faces

It is shown that for every value of an integer k, k?11, there exist 3-valent 3-connected planar graphs having just two types of faces, pentagons and k-gons, and which are non- Hamiltonian. Moreover, there exist ?=?(k) > 0, for these values of k, and sequences (G_n)^∞_n=1 of the said graphs for which V(G_n)→∞ and the size of a largest circuit of G_n is at most (1??)V(G_n); similar result for the size of a largest path in such graphs is established for all k, k?11, except possibly for k = 14, 17, 22 and k = 5m+ 5 for all m?2.     

Computational Complexity of the Vertex Cover Problem in the Class of Planar Triangulations

We study the computational complexity of the vertex cover problem in the class of planar graphs (planar triangulations) admitting a plane representation whose faces are triangles. It is shown that the problem is strongly NP-hard in the class of 4-connected planar triangulations in which the degrees of vertices are of order O(log n), where n is the number of vertices, and in the class of plane 4-connected Delaunay triangulations based on the Minkowski triangular distance. A pair of vertices in such a triangulation is adjacent if and only if there is an equilateral triangle ?(p, λ) with p ∈ R² and λ > 0 whose interior does not contain triangulation vertices and whose boundary contains this pair of vertices and only it, where ?(p, λ) = p + λ? = {x ∈ R²: x = p + λa, a ∈ ?}; here ? is the equilateral triangle with unit sides such that its barycenter is the origin and one of the vertices belongs to the negative y-axis. Keywords: computational complexity, Delaunay triangulation, Delaunay TD-triangulation.     

One edge union of shell graphs and one vertex union of complete bipartite graphs are cordial

In this paper we prove that one edge union of k-copies of shell graphs H(n,n−3) is cordial, for all n⩾4 and k⩾1 and one vertex union of t copies of complete bipartite graph K_m,n is cordial.     

Collinear subsets of lattice point sequences—An analog of Szemerédi's theorem

Szemerédi's theorem states that given any positive number B and natural number k, there is a number n(k, B) such that if n ? n(k, B) and 0 < a₁ < … < a_n is a sequence of integers with a_n ? Bn, then some k of the a_i form an arithmetic progression. We prove that given any B and k, there is a number m(k, B) such that if m ? m(k, B) and u₀, u₁, …, u_m is a sequence of plane lattice points with ∑_i=1^m…u_i ? u_i?1… ? Bm, then some k of the u_i are collinear. Our result, while similar to Szemerédi's theorem, does not appear to imply it, nor does Szemerédi's theorem appear to imply our result.