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     

Regular orientable embeddings of complete bipartite graphs

In this paper, it will be shown that the isomorphism classes of regular orientable embeddings of the complete bipartite graph K_n,n are in one‐to‐one correspondence with the permutations on n elements satisfying a given criterion, and the isomorphism classes of them are completely classified when n is a product of any two (not necessarily distinct) prime numbers. For other n, a lower bound of the number of those isomorphism classes of K_n,n is obtained. As a result, many new regular orientable embeddings of the complete bipartite graph are constructed giving an answer of Nedela‐?koviera's question raised in 12 . © 2005 Wiley Periodicals, Inc. J Graph Theory     

On the number of triangular embeddings of complete graphs and complete tripartite graphs

We prove that for every prime number p and odd m>1, as s→∞, there are at least w face 2‐colorable triangular embeddings of K_{w, w, w}, where w = m·p^s. For both orientable and nonorientable embeddings, this result implies that for infinitely many infinite families of z, there is a constant c>0 for which there are at least z nonisomorphic face 2‐colorable triangular embeddings of K_z. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Cyclic bi‐embeddings of Steiner triple systems on 12s + 7 points

A cyclic face 2‐colourable triangulation of the complete graph K_n in an orientable surface exists for n ≡ 7 (mod 12). Such a triangulation corresponds to a cyclic bi‐embedding of a pair of Steiner triple systems of order n, the triples being defined by the faces in each of the two colour classes. We investigate in the general case the production of such bi‐embeddings from solutions to Heffter's first difference problem and appropriately labelled current graphs. For n = 19 and n = 31 we give a complete explanation for those pairs of Steiner triple systems which do not admit a cyclic bi‐embedding and we show how all non‐isomorphic solutions may be identified. For n = 43 we describe the structures of all possible current graphs and give a more detailed analysis in the case of the Heawood graph. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 92–110, 2002; DOI 10.1002/jcd.10001     

Long cycles in 3‐connected graphs in orientable surfaces

In this article, we apply a cutting theorem of Thomassen to show that there is a function f: N → N such that if G is a 3‐connected graph on n vertices which can be embedded in the orientable surface of genus g with face‐width at least f(g), then G contains a cycle of length at least cn, where c is a constant not dependent on g. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 69–84, 2002     

Minimum genus embeddings of the complete graph

In this paper,the problem of construction of exponentially many minimum genus embeddings of complete graphs in surfaces are studied.There are three approaches to solve this problem.The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths;the second approach is to find a current assignment of the current graph by the theory of current graph;the third approach is to find exponentially many embedding(or rotation) schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph.According to this three approaches,we can construct exponentially many minimum genus embeddings of complete graph K_(12s+8) in orientable surfaces,which show that there are at least 10/3×(200/9)~s distinct minimum genus embeddings for K_(12s+8) in orientable surfaces.We have also proved that K_(12s+8) has at least 10/3×(200/9)~s distinct minimum genus embeddings in non-orientable surfaces.     

Commuting decompositions of complete graphs

We say that two graphs G and H with the same vertex set commute if their adjacency matrices commute. In this article, we show that for any natural number r, the complete multigraph K is decomposable into commuting perfect matchings if and only if n is a 2‐power. Also, it is shown that the complete graph K_n is decomposable into commuting Hamilton cycles if and only if n is a prime number. © 2006 Wiley Periodicals, Inc. J Combin Designs     

Phase transitions for random walk asymptotics on free products of groups

Suppose we are given finitely generated groups Γ₁,…,Γ_m equipped with irreducible random walks. Thereby we assume that the expansions of the corresponding Green functions at their radii of convergence contain only logarithmic or algebraic terms as singular terms up to sufficiently large order (except for some degenerate cases). We consider transient random walks on the free product Γ₁* … *Γ_m and give a complete classification of the possible asymptotic behaviour of the corresponding n‐step return probabilities. They either inherit a law of the form ?^nδn log n from one of the free factors Γ_i or obey a ?^nδn^?3/2‐law, where ? < 1 is the corresponding spectral radius and δ is the period of the random walk. In addition, we determine the full range of the asymptotic behaviour in the case of nearest neighbour random walks on free products of the form $\mathbb{Z}^{d_1}\ast \ldots \ast \mathbb{Z}^{d_m}Suppose we are given finitely generated groups Γ₁,…,Γ_m equipped with irreducible random walks. Thereby we assume that the expansions of the corresponding Green functions at their radii of convergence contain only logarithmic or algebraic terms as singular terms up to sufficiently large order (except for some degenerate cases). We consider transient random walks on the free product Γ₁* … *Γ_m and give a complete classification of the possible asymptotic behaviour of the corresponding n‐step return probabilities. They either inherit a law of the form ?^nδn log n from one of the free factors Γ_i or obey a ?^nδn^?3/2‐law, where ? < 1 is the corresponding spectral radius and δ is the period of the random walk. In addition, we determine the full range of the asymptotic behaviour in the case of nearest neighbour random walks on free products of the form $\mathbb{Z}^{d_1}\ast \ldots \ast \mathbb{Z}^{d_m}$. Moreover, we characterize the possible phase transitions of the non‐exponential types n log n in the case Γ₁ * Γ₂. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Multicolored trees in complete graphs

A multicolored tree is a tree whose edges have different colors. Brualdi and Hollingsworth 5 proved in any proper edge coloring of the complete graph K_2n(n > 2) with 2n ? 1 colors, there are two edge‐disjoint multicolored spanning trees. In this paper we generalize this result showing that if (a₁,…, a_k) is a color distribution for the complete graph K_n, n ≥ 5, such that , then there exist two edge‐disjoint multicolored spanning trees. Moreover, we prove that for any edge coloring of the complete graph K_n with the above distribution if T is a non‐star multicolored spanning tree of K_n, then there exists a multicolored spanning tree T' of K_n such that T and T' are edge‐disjoint. Also it is shown that if K_n, n ≥ 6, is edge colored with k colors and , then there exist two edge‐disjoint multicolored spanning trees. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 221–232, 2007     

Off‐diagonal and asymptotic results on the Ramsey number r(K2,m,K2,n)

An upper bound on the Ramsey number r(K_2,n‐s,K_2,n) where s ≥ 2 is presented. Considering certain r(K_2,n‐s,K_2,n)‐colorings obtained from strongly regular graphs, we additionally prove that this bound matches the exact value of r(K_2,n‐s,K_2,n) in infinitely many cases if holds. Moreover, the asymptotic behavior of r(K_2,m,K_2,n) is studied for n being sufficiently large depending on m. We conclude with a table of all known Ramsey numbers r(K_2,m,K_2,n) where m,n ≤ 10. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 252–268, 2003     

Blow‐up estimates for a quasi‐linear reaction–diffusion system

In this paper, some sufficient conditions under which the quasilinear elliptic system ‐div(∣?_u∣^p‐2?_u) = uv, ‐div(∣?_u∣^q‐2?_u) = uv in ?^N(N≥3) has no radially symmetric positive solution is derived. Then by using this non‐existence result, blow‐up estimates for a class of quasilinear reaction–diffusion systems u_t = div (∣?_u∣^p‐2?_u)+uv,vt = div(∣?_v∣^q‐2?_v) +uv with the homogeneous Dirichlet boundary value conditions are obtained. Copyright © 2003 John Wiley & Sons, Ltd.     

The genus of the n-octahedron: Regular cases

The n-octahedron O_n, also denoted K(2,2, …, 2) or K_n(2), is the complete n-partite graph with two vertices in each partite set. The formula for the (orientable) genus of O_n is conjectured for all n and proved for n ≠ (mof 3). Triangular embeddigns are possible precisely when n ≠ 2 (mod 3), and the formula is established by exhibiting such embeddings.     

Biembeddings of Abelian groups

We prove that, with the single exception of the 2‐group C, the Cayley table of each Abelian group appears in a face 2‐colorable triangular embedding of a complete regular tripartite graph in an orientable surface. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 71–83, 2010     

Cycle decompositions of complete multigraphs

In this paper we establish necessary and sufficient conditions for decomposing the complete multigraph λK_n into cycles of length λ, and the λ‐fold complete symmetric digraph λK into directed cycles of length λ. As a corollary to these results we obtain necessary and sufficient conditions for decomposing λK_n (respectively, λK) into cycles (respectively, directed cycles) of prime length. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 85–93, 2010     

On the density of 2‐colorable 3‐graphs in which any four points span at most two edges

Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)Let ex₂(n, K) be the maximum number of edges in a 2‐colorable K‐free 3‐graph (where K={123, 124, 134} ). The 2‐chromatic Turán density of K is $\pi_{2}({K}_{4}^-) =lim_{{n}\to \infty} {ex}_{2}({n}, {K}_{4}^-)/\left(_{3}^{n}\right)$. We improve the previously best known lower and upper bounds of 0.25682 and 3/10?ε, respectively, by showing that This implies the following new upper bound for the Turán density of K In order to establish these results we use a combination of the properties of computer‐generated extremal 3‐graphs for small n and an argument based on “super‐saturation”. Our computer results determine the exact values of ex(n, K) for n≤19 and ex₂(n, K) for n≤17, as well as the sets of extremal 3‐graphs for those n. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 105–114, 2010     

Star factorizations of graph products

A k‐star is the graph K_1,k. We prove a general theorem about k‐star factorizations of Cayley graphs. This is used to give necessary and sufficient conditions for the existence of k‐star factorizations of any power (K_q)^s of a complete graph with prime power order q, products C × C ×··· × C of k cycles of arbitrary lengths, and any power (C_r)^s of a cycle of arbitrary length. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 59–66, 2001     

Total relative displacement of vertex permutations of K

Let α denote a permutation of the n vertices of a connected graph G. Define δ_α(G) to be the number , where the sum is over all the unordered pairs of distinct vertices of G. The number δ_α(G) is called the total relative displacement of α (in G). So, permutation α is an automorphism of G if and only if δ_α(G) = 0. Let π(G) denote the smallest positive value of δ_α(G) among the n! permutations α of the vertices of G. A permutation α for which π(G) = δ_α(G) has been called a near‐automorphism of G [ 2 ]. We determine π(K) and describe permutations α of K for which π(K) = δ_α(K). This is done by transforming the problem into the combinatorial optimization problem of maximizing the sums of the squares of the entries in certain t by t matrices with non–negative integer entries in which the sum of the entries in the ith row and the sum of the entries in the ith column each equal to n_i,1≤i≤t. We prove that for positive integers, n₁≤n₂≤…≤n_t, where t≥2 and n_t≥2, where k₀ is the smallest index for which n = n+1. As a special case, we correct the value of π(K_m,n), for all m and n at least 2, given by Chartrand, Gavlas, and VanderJagt [ 2 ]. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 85–100, 2002     

On the critical point‐arboricity graphs

In this paper, we study the critical point‐arboricity graphs. We prove two lower bounds for the number of edges of k‐critical point‐arboricity graphs. A theorem of Kronk is extended by proving that the point‐arboricity of a graph G embedded on a surface S with Euler genus g = 2, 5, 6 or g ≥ 10 is at most with equality holding iff G contains either K_2k?1 or K_2k?4 + C₅ as a subgraph. It is also proved that locally planar graphs have point‐arboricity ≤ 3 and that triangle‐free locally planar‐graphs have point‐arboricity ≤ 2. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 50–61, 2002     

Surface embeddings of Steiner triple systems

A Steiner triple system of order n (STS(n)) is said to be embeddable in an orientable surface if there is an orientable embedding of the complete graph K_n whose faces can be properly 2-colored (say, black and white) in such a way that all black faces are triangles and these are precisely the blocks of the STS(n). If, in addition, all white faces are triangular, then the collection of all white triangles forms another STS(n); the pair of such STS(n)s is then said to have an (orientable) bi-embedding. We study several questions related to embeddings and bi-embeddings of STSs. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 325–336, 1998     

Density of universal classes of series‐parallel graphs

A class of graphs ordered by the homomorphism relation is universal if every countable partial order can be embedded in . It is known (see [ 1 , 3 ]) that the class of k‐colorable graphs, for any fixed , induces a universal partial order. In 4 , a surprisingly small subclass of which is a proper subclass of the series‐parallel graphs (the K₄‐minor‐free graphs) is shown to be universal. On another side, Pan and Zhu in 7 proved a density result that for each rational number , there is a K₄‐minor‐free graph with circular chromatic number equal to a/b. In this note, we show for each rational number a/b within this interval the class of K₄‐minor‐free graphs with circular chromatic number a/b is universal if and only if , 5/2 or 3. This shows yet another surprising richness of the K₄‐minor‐free class that it contains universal classes as dense as the rational numbers. © 2006 Wiley Periodicals, Inc. J Graph Theory