Two maps on one surface

Two embeddings of a graph in a surface S are said to be “equivalent” if they are identical under an homeomorphism of S that is orientation‐preserving for orientable S. Two graphs cellularly embedded simultaneously in S are said to be “jointly embedded” if the only points of intersection involve an edge of one graph transversally crossing an edge of the other. The problem is to find equivalent embeddings of the two graphs that minimize the number of these edge‐crossings; this minimum we call the “joint crossing number” of the two graphs. In this paper, we calculate the exact value for the joint crossing number for two graphs simultaneously embedded in the projective plane. Furthermore, we give upper and lower bounds when the surface is the torus, which in many cases give an exact answer. In particular, we give a construction for re‐embedding (equivalently) the graphs in the torus so that the number of crossings is best possible up to a constant factor. Finally, we show that if one of the embeddings is replaced by its “mirror image,” then the joint crossing number can decrease, but not by more than 6.066%. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 198–216, 2001     

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.     

Lower Bound of the Number of Maximum Genus Embeddings and Genus Embeddings of K 12s+7

In this paper, we study lower bound of the number of maximum orientable genus embeddings (or MGE in short) for a loopless graph. We show that a connected loopless graph of order n has at least \frac14^g_M(G)?_{v ? V(G)}(d(v)-1)!{\frac{1}{4^{\gamma_M(G)}}\prod_{v\in{V(G)}}{(d(v)-1)!}} distinct MGE’s, where γ _M (G) is the maximum orientable genus of G. Infinitely many examples show that this bound is sharp (i.e., best possible) for some types of graphs. Compared with a lower bound of Stahl (Eur J Combin 13:119–126, 1991) which concerns upper-embeddable graphs (i.e., embedded graphs with at most two facial walks), this result is more general and effective in the case of (sparse) graphs permitting relative small-degree vertices. We also obtain a similar formula for maximum nonorientable genus embeddings for general graphs. If we apply our orientable results to the current graph G _s of K _12s+7, then G _s has at least 2^3s distinct MGE’s.This implies that K _12s+7 has at least (22) ^s nonisomorphic cyclic oriented triangular embeddings for sufficient large s.     

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     

On disjoint configurations in infinite graphs

For a graph A and a positive integer n, let nA denote the union of n disjoint copies of A; similarly, the union of ?₀ disjoint copies of A is referred to as ?₀A. It is shown that there exist (connected) graphs A and G such that nA is a minor of G for all n??, but ?₀A is not a minor of G. This supplements previous examples showing that analogous statements are true if, instead of minors, isomorphic embeddings or topological minors are considered. The construction of A and G is based on the fact that there exist (infinite) graphs G₁, G₂,… such that G_i is not a minor of G_j for all i ≠ j. In contrast to previous examples concerning isomorphic embeddings and topological minors, the graphs A and G presented here are not locally finite. The following conjecture is suggested: for each locally finite connected graph A and each graph G, if nA is a minor of G for all n ? ?, then ?₀A is a minor of G, too. If true, this would be a far‐reaching generalization of a classical result of R. Halin on families of disjoint one‐way infinite paths in graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 222–229, 2002; DOI 10.1002/jgt.10016     

Dual imbeddings and wrapped quasi-coverings of graphs

This paper gives a new method for constructing imbeddings of graphs which are “nearly” coverings of given imbedded graphs. The method is based on the dual theories of current graphs and voltage graphs. Some applications are given, in particular the following theorem: Let G be any graph which has a triangular imbedding in the sphere. Then there are infinitely many integers n for which the composition G[nK₁] has a triangular (orientable surface) imbedding.     

Trading crossings for handles and crosscaps

Let c_k = cr_k (G) denote the minimum number of edge crossings when a graph G is drawn on an orientable surface of genus k. The (orientable) crossing sequence c_o, c₁,c₂…encodes the trade‐off between adding handles and decreasing crossings. We focus on sequences of the type c_o > c₁ > c₂ = 0; equivalently, we study the planar and toroidal crossing number of doubly‐toroidal graphs. For every ? > 0 we construct graphs whose orientable crossing sequence satisfies c₁/c_o > 5/6??. In other words, we construct graphs where the addition of one handle can save roughly 1/6th of the crossings, but the addition of a second handle can save five times more crossings. We similarly define the non‐orientable crossing sequence ?₀,?₁,?₂, ··· for drawings on non‐orientable surfaces. We show that for every ?₀ > ?₁ > 0 there exists a graph with non‐orientable crossing sequence ?₀, ?₁, 0. We conjecture that every strictly‐decreasing sequence of non‐negative integers can be both an orientable crossing sequence and a non‐orientable crossing sequence (with different graphs). © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 230–243, 2001     

Embeddings of covering projections of graphs

It is shown that any given k-fold covering projection of graphs p: G₁ → G₂ can be embedded in a k-fold covering projection of closed orientable surfaces π: S₁ → S₂ in the sense that there are embeddings of G₁ in S₁ and G₂ in S₂ such that p is the restriction of π. In the case of a regular covering projection p, which is the quotient map with respect to some group action on G₁, it is shown that there is a regular covering projection π of surfaces in which p can be embedded.     

Orientation embedding of signed graphs

A signed graph Σ consists of a graph and a sign labeling of its edges. A polygon in Σ is “balanced” if its sign product is positiive. A signed graph is “orientatio embedded” in a surface if it is topologically embedded and a polygon is balanced precisely when traveling once around it preserves orientation. We explore the extension to orientation embedding of the ordinary theory of graph embedding. Let d(Σ) be the demigenus (= 2 - x(S)) of the unique smallest surface S in which Σ has an orientation embedding. Our main results are an easy one, that if Σ has connected components Σ₁, Σ[2], ?, then d(Σ) = d(Σ₁) + ?, and a hard one, that if Σ has a cut vertex v that splits Σ into Σ₁, Σ₂, ?, then d(Σ) = d(Σ₁) + d(Σ₂) + ? -δ, where δ depends on the number of Σ_i in which v is “loopable”, that is, in which d(Σ_i) = d(Σ_{i with a negative loop added to v}). This is as with ordinary orientable grpah embedidng except for the existence of the term δ in the cut-vertex formula. Since loopability is crucial, we give some partial criteria for it. (A complete characterization seems difficult.) We conclude with an application to forbidden subgraphs and minors for orientation embeddability in a given surface. © 1929 John Wiley & Sons, Inc.     

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.     

A note on Ki-perfect graphs

Ki-perfect graphs are a special instance of F - G perfect graphs, where F and G are fixed graphs with F a partial subgraph of G. Given S, a collection of G-subgraphs of graph K, an F - G cover of S is a set of T of F-subgraphs of K such that each subgraph in S contains as a subgraph a member of T. An F - G packing of S is a subcollection S′? S such that no two subgraphs in S′ have an F-subgraph in common. K is F - G perfect if for all such S, the minimum cardinality of an F - G cover of S equals the maximum cardinality of an F - G packing of S. Thus K_i-perfect graphs are precisely K_i-1 - K_i perfect graphs. We develop a hypergraph characterization of F - G perfect graphs that leads to an alternate proof of previous results on K_i-perfect graphs as well as to a characterization of F - G perfect graphs for other instances of F and G.     

The 3‐connectivity of a graph and the multiplicity of zero “2” of its chromatic polynomial

Let G be a graph of order n, maximum degree Δ, and minimum degree δ. Let P(G, λ) be the chromatic polynomial of G. It is known that the multiplicity of zero “0” of P(G, λ) is one if G is connected, and the multiplicity of zero “1” of P(G, λ) is one if G is 2‐connected. Is the multiplicity of zero “2” of P(G, λ) at most one if G is 3‐connected? In this article, we first construct an infinite family of 3‐connected graphs G such that the multiplicity of zero “2” of P(G, λ) is more than one, and then characterize 3‐connected graphs G with Δ + δ?n such that the multiplicity of zero “2” of P(G, λ) is at most one. In particular, we show that for a 3‐connected graph G, if Δ + δ?n and (Δ, δ₃)≠(n?3, 3), where δ₃ is the third minimum degree of G, then the multiplicity of zero “2” of P(G, λ) is at most one. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Enumerating reflexible 2-cell embeddings of connected graphs

Two 2-cell embeddings:X → S and j:X → S of a connected graph X into a closed orientable surface S are congruent if there are an orientation-preserving surface homeomorphism h on S and a graph automorphism γ of X such that h = γj.A 2-cell embedding:X → S of a graph X into a closed orientable surface S is described combinatorially by a pair(X;ρ) called a map,where ρ is a product of disjoint cycle permutations each of which is the permutation of the darts of X initiated at the same vertex following the orientation of S.The mirror image of a map(X;ρ) is the map(X;ρ 1),and one of the corresponding embeddings is called the mirror image of the other.A 2-cell embedding of X is reflexible if it is congruent to its mirror image.Mull et al.[Proc Amer Math Soc,1988,103:321-330] developed an approach for enumerating the congruence classes of 2-cell embeddings of graphs into closed orientable surfaces.In this paper we introduce a method for enumerating the congruence classes of reflexible 2-cell embeddings of graphs into closed orientable surfaces,and apply it to the complete graphs,the bouquets of circles,the dipoles and the wheel graphs to count their congruence classes of reflexible or nonreflexible(called chiral) embeddings.     

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     

On the orientable genus of graphs embedded in the klein bottle

Let G be a graph embedded in the Klein bottle with “representativity” at least four. We give a formula for the orientable genus of G, which also implies a polynomially bounded algorithm. The formula is in terms of the number of times certain closed curves on the Klein bottle intersect the graph. In particular, it shows that a cut-and-paste technique for re-embedding graphs is the best possible.     

Triangular embeddings of K((i-2) n,n,…,n)

For complete i-partite graphs of the form K(n₁, n, n, …, n) the largest value of n₁ that allows the graph to be triangularly-embedded into a surface is (i-2)n. In this paper the author constructs triangular embeddings into surfaces of some complete partite graphs of the form K((i-2)n, n, …, n). The embeddings are exhibited using embedding schemes but the surfaces into which K((i-2)n, n, …, n) are triangularly embedded can be seen to be particularly nice branched covers of a surface into which K(i-2, 1, 1,…,1) is triangularly embedded.     

Sequences,claws and cyclability of graphs

A subset S of vertices of a graph G is called cyclable in G if there is in G some cycle containing all the vertices of S. We give two results on the cyclability of a vertex subset in graphs, one of which is related to “hamiltonian-nice-sequence” conditions and the other of which is related to “claw-free” conditions. They imply many known results on hamiltonian graph theory. Moreover, the analogous results related to the hamilton-connectivity or to the existence of dominating cycle are also given. © 1996 John Wiley & Sons, Inc.     

On superperfect noncomparability graphs

The class of superperfect graphs, which was previously studied by A. J. Hoffman, E. L. Johnson, and M. C. Golumbic, is a proper subclass of the class of perfect graphs; further, it properly contains the class of comparability graphs. In his book, Golumbic proves that, for split graphs, G is a comparability graph if and only if G is superperfect. Moreover, the fact that split graphs are exactly those graphs which are both triangulated and cotriangulated motivated Golumbic to ask if it is true or false that, for triangulated (or cotriangulated) graphs, G is a comparability graph if and only if G is superperfect. In the present paper, we determine those members of Gallai's list of minimal noncomparability graphs which are superperfect and, as a consequence, we find that the answer to the above question is “false” for triangulated and “true” for cotriangulated graphs.     

Search algorithm for Ramsey graphs by union of group orbits

An algorithm for the construction of Ramsey graphs with a given automorphism group G is presented. To find a graph on n vertices with no clique of k vertices, K_k, and no independent set of l vertices, ¯K_l, k, l ≤ n, with an automorphism group G, a Boolean formula α based on the G-orbits of k-subsets and l-subsets of vertices is constructed from incidence matrices belonging to G. This Boolean formula is satisfiable if and only if the desired graph exists, and each satisfying assignment to α specifies a set of orbits of pairs of vertices whose union gives the edges of such a graph. Finding these assignments is basically equivalent to the conversion of α from CNF to DNF (conjunctive to disjunctive normal form). Though the latter problem is NP-hard, we present an “efficient” method to do the conversion for the formulas that appear in this particular problem. When G is taken to be the dihedral group D_n for n ≤ 101, this method matches all of the previously known cyclic Ramsey graphs, as reported by F. R. K. Chung and C. M. Grinstead [“A Survey of Bounds for Classical Ramsey Numbers,” Journal of Graph Theory, 7 (1983), 25–38], in dramatically smaller computer time when compared to the time required by an exhaustive search. Five new lower bounds for the classical Ramsey numbers are established: R(4, 7) ? 47, R(4, 8) ? 52, R(4, 9) ? 69, R(5,7) ? 76, and R(5, 8) ? 94. Also, some previously known cyclic graphs are shown to be unique up to isomorphism.     

Cochromatic Number and the Genus of a Graph

The cochromatic number of a graph G, denoted by z(G), is the minimum number of subsets into which the vertex set of G can be partitioned so that each sbuset induces an empty or a complete subgraph of G. In this paper we introduce the problem of determining for a surface S, z(S), which is the maximum cochromatic number among all graphs G that embed in S. Some general bounds are obtained; for example, it is shown that if S is orientable of genus at least one, or if S is nonorientable of genus at least four, then z(S) is nonorientable of genus at least four, then z(S)≤χ(S). Here χ(S) denotes the chromatic number S. Exact results are obtained for the sphere, the Klein bottle, and for S. It is conjectured that z(S) is equal to the maximum n for which the graph G_n = K₁ ∪ K₂ ∪ … ∪ K_n embeds in S.