On Ramsey numbers involving starlike multipartite graphs

The Ramsey number r(G, H) is evaluated exactly in certain cases in which both G and H are complete multipartite graphs K(n,₁, n₂, …. n_k). Specifically, each of the following cases is handled whenever n is sufficiently large: r(K(1, m₁, …. m_k), K(1, n)), r(K(1, m), K(n₁, …. n_k, n)), provided m ≧ 4, and r(K(1, 1, m), K(n_k, …, n_k, n)).     

Embeddings of bipartite graphs

If G is a bipartite graph with bipartition A, B then let G_m,n(A, B) be obtained from G by replacing each vertex a of A by an independent set a₁, …, a_m, each vertex b of B by an independent set b₁,…, b_n, and each edge ab of G by the complete bipartite graph with edges a_ib_j (1 ≤ i ≤ m and 1 ≤ j ≤ n). Whenever G has certain types of spanning forests, then cellular embeddings of G in surfaces S may be lifted to embeddings of G_m,n(A, B) having faces of the same sizes as those of G in S. These results are proved by the technique of “excess-current graphs.” They include new genus embeddings for a large class of bipartite graphs.     

Recursive constructions for triangulations

Three recursive constructions are presented; two deal with embeddings of complete graphs and one with embeddings of complete tripartite graphs. All three facilitate the construction of 2) non‐isomorphic face 2‐colourable triangulations of K_n and K_n,n,n in orientable and non‐orientable surfaces for values of n lying in certain residue classes and for appropriate constants a. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 87–107, 2002     

A duality theorem for graph embeddings

A generalized type of graph covering, called a “Wrapped quasicovering” (wqc) is defined. If K, L are graphs dually embedded in an orientable surface S, then we may lift these embeddings to embeddings of dual graphs K?,L? in orientable surfaces S?, such that S? are branched covers of S and the restrictions of the branched coverings to K?,L? are wqc's of K, L. the theory is applied to obtain genus embeddings of composition graphs G[nK₁] from embeddings of “quotient” graphs G.     

A New Construction for Cohen–Macaulay Graphs

Let G be a finite simple graph on a vertex set V(G) = {x ₁₁,…, x _n1}. Also let m ₁,…, m _n  ≥ 2 be integers and G ₁,…, G _n be connected simple graphs on the vertex sets V(G _i ) = {x _i1,…, x _{im i} }. In this article, we provide necessary and sufficient conditions on G ₁,…, G _n for which the graph obtained by attaching the G _i to G is unmixed or vertex decomposable. Then we characterize Cohen–Macaulay and sequentially Cohen–Macaulay graphs obtained by attaching the cycle graphs or connected chordal graphs to arbitrary graphs.     

Mixed ramsey numbers: Chromatic numbers versus graphs

For positive integers n₁, n₂, …, n_I and graphs G_I+1, G_I+2, …, G_k, 1 ≤ / < k, the mixed Ramsey number _χ(n₁, …, n₁, G_I+1, …, G_k) is define as the least positive integer p such that for each factorization K_p = F₁⊕ … ⊕ F_⊕ F_I+1⊕ … ⊕ F_k, it it follows that χ(F_i) ≥ n_i for some i, 1 ? i ? l, or G_i is a subgraph of F_i for some i, l < i ? k. Formulas are presented for maxed Ramsey numbers in which the graphs G_I+1, G_I+2, …, G_k are connected, and in which k = I+1 and G_I+1 is arbitray.     

Covering the vertices of a graph by cycles of prescribed length

The main theorem of that paper is the following: let G be a graph of order n, of size at least (n² - 3n + 6)/2. For any integers k, n₁, n₂,…,n_k such that n = n₁ + n₂ +. + n_k and n_i ? 3, there exists a covering of the vertices of G by disjoint cycles (C_i) =l…k with |C_i| = ni, except when n = 6, n₁ = 3, n₂ = 3, and G is isomorphic to G₁, the complement of G₁ consisting of a C₃ and a stable set of three vertices, or when n = 9, n₁ = n₂ = n₃ = 3, and G is isomorphic to G₂, the complement of G₂ consisting of a complete graph on four vertices and a stable set of five vertices. We prove an analogous theorem for bipartite graphs: let G be a bipartite balanced graph of order 2n, of size at least n² - n + 2. For any integers s, n₁, n₂,…,n_s with n_i ? 2 and n = n₁ + n₂ + ? + n_s, there exists a covering of the vertices of G by s disjoint cycles C_i, with |C_i| = 2n_i.     

On B(n,k) 2-groups

A finite group G is said to be a B(n, k) group if for any n-element subset {a ₁,…, a _n } of G, |{a _i a _j |1 ≤ i, j ≤ n}| ≤k. In this article, we give characterizations of the B(5, 19) 2-groups, and the B(6, k) 2-groups for 21 ≤ k ≤ 28.     

Self-dual embeddings of complete multipartite graphs

In this paper we examine self-dual embeddings of complete multipartite graphs, focusing primarily on K_m(n) having m parts each of size n. If m = 2, then n must be even. If the embedding is on an orientable surface, then an Euler characteristic argument shows that no such embedding exists when n is odd and m ? 2, 3 (mod 4); there is no such restriction for embeddings on nonorientable surfaces. We show that these embeddings exist with a few small exceptions. As a corollary, every group has a Cayley graph with a self-dual embedding. Our main technique is an addition construction that combines self-dual embeddings of two subgraphs into a self-dual embedding of their union. We also apply this technique to nonregular multipartite graphs and to cubes.     

Triangular embeddings of complete graphs (neighborly maps) with 12 and 13 vertices

In this paper, we describe the generation of all nonorientable triangular embeddings of the complete graphs K₁₂ and K₁₃. (The 59 nonisomorphic orientable triangular embeddings of K₁₂ were found in 1996 by Altshuler, Bokowski, and Schuchert, and K₁₃ has no orientable triangular embeddings.) There are 182,200 nonisomorphic nonorientable triangular embeddings for K₁₂, and 243,088,286 for K₁₃. Triangular embeddings of complete graphs are also known as neighborly maps and are a type of twofold triple system. We also use methods of Wilson to provide an upper bound on the number of simple twofold triple systems of order n, and thereby on the number of triangular embeddings of K_n. We mention an application of our results to flexibility of embedded graphs. © 2005 Wiley Periodicals, Inc. J Combin Designs     

A Regularization Procedure for Σn−i=1fi(zj)xi = g(zj), ( j = 1, 2, …, n)

A regularization procedure for linear systems of the type fi(z_j)x_i = g(zj), (j = 1, 2, …, n) is presented, which is particularly useful in the case when z₁, z₂, …, z_n are close to each other. The associated numerical algorithm was tested on several examples for which analytic solutions do exist and was found to yield highly accurate results.     

Zur Lösung einer Klasse von Gleichungen mit einem monotonen Potentialoperator

This paper is concerned with terminable and interminable paths and trails in infinite graphs. It is shown that

• The only connected graphs which contain no 2 – ∞ way and in which no finite path is terminable are precisely all the 1 – ∞ multiways.
• The only connected graphs which have no 2 – ∞ trail and in which no finite trail is terminable are precisely all the 1 – ∞ multiways all of whose multiplicities are odd numbers and which have infinitely many bridges.
• In addition the strucuture of those connected graphs is determined which have a 1 – ∞ trail and in which no 1 – ∞ trail but every finite trail is terminable.

In this paper the terminology and notation of a previous paper of the writer [1] and of F. HARARY 's book [6] will be used. Furthermore, a graph consisting of the distinct nodes n₁,…,n_δ (where δ≧1) and of one or more (n_i, n_i+1)-edges for i = 1,…, δ – 1 will be called a multiway, and analogously for 1 – ∞ and 2 – ∞ multiways. The number of edges joining n_i and n_i+1 will be called the (n_i,+1)-multiplicity. Thus a multiway in which each multiplicity is 1 is a way. Multiplicities are allowed to be infinite.     

Additive and hereditary properties of graphs are uniquely factorizable into irreducible factors

A hereditary property of graphs is any class of graphs closed under isomorphism and subgraphs. Let 𝒫₁, 𝒫₂,…, 𝒫_n be hereditary properties of graphs. We say that a graph G has property 𝒫_1°𝒫_2°···_°𝒫_n if the vertex set of G can be partitioned into n sets V₁, V₂,…, V_n such that the subgraph of G induced by V_i belongs to 𝒫_i; i = 1, 2,…, n. A hereditary property is said to be reducible if there exist hereditary properties 𝒫₁ and 𝒫₂ such that ℛ = 𝒫_1°𝒫₂; otherwise it is irreducible. We prove that the factorization of a reducible hereditary property into irreducible factors is unique whenever the property is additive, i.e., it is closed under the disjoint union of graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 44–53, 2000     

Quadrilateral embeddings of bipartite graphs

Current graphs and a theorem of White are used to show the existence of almost complete regular bipartite graphs with quadrilateral embeddings conjectured by Pisanski. Decompositions of K_n and K_{n, n} into graphs with quadrilateral embeddings are discussed, and some thickness results are obtained. Some new genus results are also obtained.     

On B(4, 13) 2-Groups

A group G is said to be a B(n, k) group if for any n-element subset {a ₁,…, a _n } of G, |{a _i a _j  | 1 ≤ i, j ≤ n}| ≤k. In this article, we give a complete characterization of B(4, 13) 2-groups, and then obtain a complete characterization of B(4, 13) groups.     

Chromatic factorizations of a graph

Let n₁ ? n₂ ? …? ? n_k ? 2 be integers. We say that G has an (n₁, n₂, …?, n_k-chromatic factorization if G) can be edge-factored as G₁ ⊕ G₂ ⊕ …? ⊕ G_k with χ(G_i) = nA_i, for i = 1,2,…, k. The following results are proved:

• i If (n₁ ? 1)n₂ …? n_k < χ(G) ? n₁n₂ …? n_k, then G has an (n₁, n₂, …?, n_k)-chromatic factorization.
• ii If n₁ + n₂ + …? + n_k ? (k - 1) ? n ? n₁n₂ …? n_k, then K_n has an (n₁, n₂, …?, n_k)-chromatic factorization.

     

Group of units of group algebras

By a right (left resp.) S_2n-polynomial we mean a multilinear polynomial f(X₁,…, X_t) over the ring of integers with noncommuting in-determinates X_isuch that for any prime ring R if f( X₁,…, X _t) is a PI of some nonzero right (left resp.) ideal of R, then R satisfies S_2nthe standard identity of degree 2n. In this paper we prove the theorem:Let R be a prime ring, d a nonzero derivation of R, L a noncommutative Lie ideal of R and f(X₁,…, X_t) a right or left S_2n-polynomial. Suppose that f(d( u₁)ⁿ¹,…,d(u_t)^nt)=0 for all u_iu,_i[d] L, where n₁,…,n_tare fixed positive integers. Then R satisfies S_2n+2. Also, the one-sided version of the theorem is given.     

Partitions of the 8‐dimensional vector space over GF(2)

Let V = V(n, q) denote the vector space of dimension n over GF(q). A set of subspaces of V is called a partition of V if every nonzero vector in V is contained in exactly one subspace of V. Given a partition 𝒫 of V with exactly a_i subspaces of dimension i for 1≤i≤n, we have , and we call the n‐tuple (a_n, a_{n − 1}, …, a₁) the type of 𝒫. In this article we identify all 8‐tuples (a₈, a₇, …, a₂, 0) that are the types of partitions of V(8, 2). © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 462–474, 2010     

Edge-colored saturated graphs

A graph G is (k₁, k₂, …, k_t)-saturated if there exists a coloring C of the edges of G in t colors 1, 2, …, t in such a way that there is no monochromatic complete k_i-subgraph K of color i, 1 ? i ? t, but the addition of any new edge of color i, joining two nonadjacent vertices in G, with C, creates a monochromatic K of color i, 1 ? i ? t. We determine the maximum and minimum number of edges in such graphs and characterize the unique extremal graphs.