Hyperbolic spatial graphs in 3-manifolds

For any closed connected orientable 3-manifold M, we present a method for constructing infinitely many hyperbolic spatial embeddings of a given finite graph with no vertex of degree less than two from hyperbolic spatial graphs in S³ via the Heegaard splitting theory. These spatial embeddings are adjustable so as to take cycle subgraphs into specified homotopy classes of loops in M.     

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.     

Regular maps of graphs of order 4<Emphasis Type="Italic">p</Emphasis>

A 2-cell embedding f : X → S of a graph X into a closed orientable surface S can be described combinatorially by a pair M = (X;ρ ) called a map, where ρ is a product of disjoint cycle permutations each of which is the permutation of the arc set of X initiated at the same vertex following the orientation of S . It is well known that the automorphism group of M acts semi-regularly on the arc set of X and if the action is regular, then the map M and the embedding f are called regular. Let p and q be primes. Du et al. [J. Algebraic Combin., 19, 123-141 (2004)] classified the regular maps of graphs of order pq . In this paper all pairwise non-isomorphic regular maps of graphs of order 4 p are constructed explicitly and the genera of such regular maps are computed. As a result, there are twelve sporadic and six infinite families of regular maps of graphs of order 4 p ; two of the infinite families are regular maps with the complete bipartite graphs K2p,2p as underlying graphs and the other four infinite families are regular balanced Cayley maps on the groups Z4p , Z22 × Zp and D4p .     

Almost all quartic half-arc-transitive weak metacirculants of Class II are of Class IV

A half-arc-transitive graph is a vertex- and edge- but not arc-transitive graph. A weak metacirculant is a graph admitting a transitive metacyclic group that is a group generated by two automorphisms ρ and σ, where ρ is (m,n)-semiregular for some integers m≥1 and n≥2, and where σ normalizes ρ. It was shown in [D. Maruši?, P. Šparl, On quartic half-arc-transitive metacirculants, J. Algebr. Comb. 28 (2008) 365-395] that each connected quartic half-arc-transitive weak metacirculant X belongs to one (or possibly more) of four classes of such graphs, reflecting the structure of the quotient graph X_ρ relative to the semiregular automorphism ρ. The first of these classes, called Class I, coincides with the class of so-called tightly attached graphs. Class II consists of the quartic half-arc-transitive weak metacirculants for which the quotient graph X_ρ is a cycle with a loop at each vertex. Class III consists of those graphs for which each vertex of the quotient graph X_ρ is connected to three other vertices, to one with a double edge. Finally, Class IV consists of those graphs for which X_ρ is a simple quartic graph.This paper consists of two results concerning graphs of Class II. It is shown that, with the exception of the Doyle-Holt graph and its canonical double cover, each quartic half-arc-transitive weak metacirculant of Class II is also of Class IV. It is also shown that although quartic half-arc-transitive weak metacirculants of Class II which are not tightly attached exist they are “almost tightly attached”. More precisely, their radius is at most four times their attachment number.     

The Semi-Arc Automorphism Group of a Graph with Application to Map Enumeration

A map is a connected topological graph cellularly embedded in a surface. For a given graph Γ, its genus distribution of rooted maps and embeddings on orientable and non-orientable surfaces are separately investigated by many researchers. By introducing the concept of a semi-arc automorphism group of a graph and classifying all its embeddings under the action of its semi-arc automorphism group, we find the relations between its genus distribution of rooted maps and genus distribution of embeddings on orientable and non-orientable surfaces, and give some new formulas for the number of rooted maps on a given orientable surface with underlying graph a bouquet of cycles B_n, a closed-end ladder L_n or a Ringel ladder R_n. A general scheme for enumerating unrooted maps on surfaces(orientable or non-orientable) with a given underlying graph is established. Using this scheme, we obtained the closed formulas for the numbers of non-isomorphic maps on orientable or non-orientable surfaces with an underlying bouquet B_n in this paper.     

Graphs of given genus and arbitrarily large maximum genus

The maximum genus of a connected graph G is the maximum among the genera of all compact orientable 2-manifolds upon which G has 2-cell embeddings. In the theorems that follow the use of an edge-adding technique is combined with the well-known Edmonds' technique to produce the desired results. Planar graphs of arbitrarily large maximum genus are displayed in Theorem 1. Theorem 2 shows that the possibility for arbitrarily large difference between genus and maximum genus is not limited to planar graphs. In particular, we show that the wheel graph, the standard maximal planar graph, and the prism graph are upper embeddable. We then show that given m and n, there is a graph of genus n and maximum genus larger than mn.     

Classification of regular embeddings of hypercubes of odd dimension

By a regular embedding of a graph into a closed surface we mean a 2-cell embedding with the automorphism group acting regularly on flags. Recently, Kwon and Nedela [Non-existence of nonorientable regular embeddings of n-dimensional cubes, Discrete Math., to appear] showed that no regular embeddings of the n-dimensional cubes Q_n into nonorientable surfaces exist for any positive integer n>2. In 1997, Nedela and Škoviera [Regular maps from voltage assignments and exponent groups, European J. Combin. 18 (1997) 807-823] presented a construction giving for each solution of the congruence a regular embedding M_e of the hypercube Q_n into an orientable surface. It was conjectured that all regular embeddings of Q_n into orientable surfaces can be constructed in this way. This paper gives a classification of regular embeddings of hypercubes Q_n into orientable surfaces for n odd, proving affirmatively the conjecture of Nedela and Škoviera for every odd n.     

A Polynomial Invariant of Graphs On Orientable Surfaces

We consider cyclic graphs, that is, graphs with cyclic ordersat the vertices, corresponding to 2-cell embeddings of graphsinto orientable surfaces, or combinatorial maps. We constructa three variable polynomial invariant of these objects, thecyclic graph polynomial, which has many of the useful propertiesof the Tutte polynomial. Although the cyclic graph polynomialgeneralizes the Tutte polynomial, its definition is very different,and it depends on the embedding in an essential way. 2000 MathematicalSubject Classification: 05C10.     

Classification of reflexible regular embeddings and self-Petrie dual regular embeddings of complete bipartite graphs

In this paper, we classify the reflexible regular orientable embeddings and the self-Petrie dual regular orientable embeddings of complete bipartite graphs. The classification shows that for any natural number n, say (p₁,p₂,…,p_k are distinct odd primes and a_i>0 for each i?1), there are t distinct reflexible regular embeddings of the complete bipartite graph K_n,n up to isomorphism, where t=1 if a=0, t=2^k if a=1, t=2^k+1 if a=2, and t=3·2^k+1 if a?3. And, there are s distinct self-Petrie dual regular embeddings of K_n,n up to isomorphism, where s=1 if a=0, s=2^k if a=1, s=2^k+1 if a=2, and s=2^k+2 if a?3.     

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.     

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.     

Annular embeddings of permutations for arbitrary genus

In the symmetric group on a set of size 2n, let P2n denote the conjugacy class of involutions with no fixed points (equivalently, we refer to these as “pairings”, since each disjoint cycle has length 2). Harer and Zagier explicitly determined the distribution of the number of disjoint cycles in the product of a fixed cycle of length 2n and the elements of P2n. Their famous result has been reproved many times, primarily because it can be interpreted as the genus distribution for 2-cell embeddings in an orientable surface, of a graph with a single vertex attached to n loops. In this paper we give a new formula for the cycle distribution when a fixed permutation with two cycles (say the lengths are p,q, where p+q=2n) is multiplied by the elements of P2n. It can be interpreted as the genus distribution for 2-cell embeddings in an orientable surface, of a graph with two vertices, of degrees p and q. In terms of these graphs, the formula involves a parameter that allows us to specify, separately, the number of edges between the two vertices and the number of loops at each of the vertices. The proof is combinatorial, and uses a new algorithm that we introduce to create all rooted forests containing a given rooted forest.     

Automorphisms of Maps with a Given Underlying Graph and Their Application to Enumeration

A graph is called a semi-regular graph if its automorphism group action on its ordered pair of adjacent vertices is semi-regular. In this paper, a necessary and sufficient condition for an automorphism of the graph F to be an automorphism of a map with the underlying graph F is obtained. Using this result, all orientation-preserving automorphisms of maps on surfaces (orientable and non-orientable) or just orientable surfaces with a given underlying semi-regular graph F are determined. Formulas for the numbers of non-equivalent embeddings of this kind of graphs on surfaces (orientable, non-orientable or both) are established, and especially, the non-equivalent embeddings of circulant graphs of a prime order on orientable, non-orientable and general surfaces are enumerated.     

On IP-graphs of association schemes and applications to group theory

Let G be a group acting transitively on a set X such that all subdegrees are finite. Isaacs and Praeger (1993) [5] studied the common divisor graph of (G,X). For a group G and its subgroup A, based on the results in Isaacs and Praeger (1993) [5], Kaplan (1997) [6] proved that if A is stable in G and the common divisor graph of (A,G) has two components, then G has a nice structure. Motivated by the notion of the common divisor graph of (G,X), Camina (2008) [3] introduced the concept of the IP-graph of a naturally valenced association scheme. The common divisor graph of (G,X) is the IP-graph of the association scheme arising from the action of G on X. Xu (2009) [8] studied the properties of the IP-graph of an arbitrary naturally valenced association scheme, and generalized the main results in Isaacs and Praeger (1993) [5] and Camina (2008) [3]. In this paper we first prove that if the IP-graph of a naturally valenced association scheme (X,S) is stable and has two components (not including the trivial component whose only vertex is 1), then S has a closed subset T such that the thin residue O?(T) and the quotient scheme (X/O?(T),S//O?(T)) have very nice properties. Then for an association scheme (X,S) and a closed subset T of S such that S//T is an association scheme on X/T, we study the relations between the closed subsets of S and those of S//T. Applying these results to schurian schemes and common divisor graphs of groups, we obtain the results of Kaplan [6] as direct consequences.     

Complete regular dessins of odd prime power order

A dessin is a 2-cell embedding of a connected 2-coloured bipartite graph into an orientable closed surface. A dessin is regular if its group of colour- and orientation-preserving automorphisms acts regularly on the edges. In this paper we employ group-theoretic method to determine and enumerate the isomorphism classes of regular dessins with complete bipartite underlying graphs of odd prime power order.     

Regular embeddings of complete multipartite graphs

In this paper, we classify all regular embeddings of the complete multipartite graphs K_p,…,p for a prime p into orientable surfaces. Also, the same work is done for the regular embeddings of the lexicographical product of any connected arc-transitive graph of prime order q with the complement of the complete graph of prime order p, where q and p are not necessarily distinct. Lots of regular maps found in this paper are Cayley maps.     

Convexity in oriented graphs

For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a u−v geodesic or v−u geodesic in D. For S⊆V(D), I[S] is the union of all closed intervals I[u,v] with u,v∈S. A set S is convex if I[S]=S. The convexity number con(D) is the maximum cardinality of a proper convex set of V(D). The nontrivial connected oriented graphs of order n with convexity number n−1 are characterized. It is shown that there is no connected oriented graph of order at least 4 with convexity number 2 and that every pair k, n of integers with 1⩽k⩽n−1 and k≠2 is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph G, the lower orientable convexity number con⁻(G) is the minimum convexity number among all orientations of G and the upper orientable convexity number con⁺(G) is the maximum such convexity number. It is shown that con⁺(G)=n−1 for every graph G of order n⩾2. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.     

Total embedding distributions of Ringel ladders

The total embedding distributions of a graph consists of the orientable embeddings and non-orientable embeddings and are known for only a few classes of graphs. The orientable genus distribution of Ringel ladders is determined in [E.H. Tesar, Genus distribution of Ringel ladders, Discrete Mathematics 216 (2000) 235–252] by E.H. Tesar. In this paper, using the overlap matrix, we obtain nonhomogeneous recurrence relation for rank distribution polynomial, which can be solved by the Chebyshev polynomials of the second kind. The explicit formula for the number of non-orientable embeddings of Ringel ladders is obtained. Also, the orientable genus distribution of Ringel ladders is re-derived.