Search

A tight Heffter array H(m,n) is an m×n matrix with nonzero entries from Z2mn+1 such that (i) the sum of the elements in each row and each column is 0, and (ii) no element from {x,−x} appears twice. We prove that H(m,n) exist if and only if both m and n are at least 3. If H has the property that all entries are integers of magnitude at most mn, every row and column sum is 0 over the integers, and H also satisfies (ii), we call H an integer Heffter array. We show integer Heffter arrays exist if and only if mn≡0,3(mod4). Finally, an integer Heffter array is shiftable if each row and column contains the same number of positive and negative integers. We show that shiftable integer arrays exists exactly when both m,n are even.

A Heffter array $$H(m,n;s,t)$$H(m,n?s,t) is an $$m \times n$$m×n matrix with nonzero entries from $$\mathbb {Z}_{2ms+1}$$Z2ms+1 such that (i) each row contains $$s$$s filled cells and each column contains $$t$$t filled cells, (ii) every row and column sum to 0, and (iii) no element from $$\{x,-x\}$${x,-x} appears twice. Heffter arrays are useful in embedding the complete graph $$K_{2ms+1}$$K2ms+1 on an orientable surface where the embedding has the property that each edge borders exactly one s-cycle and one t-cycle. Archdeacon, Boothby and Dinitz proved that these arrays can be constructed in the case when $$s=m$$s=m, i.e every cell is filled. In this paper we concentrate on square arrays with empty cells where every row sum and every column sum is $$0$$0 in $${\mathbb {Z}}$$Z. We solve most of the instances of this case.

Minimal obstructions for embedding 4-regular Eulerian digraphs on the plane are considered in relation to the partial order defined by the cycle removal operation. Their basic properties are provided and all obstructions with parallel arcs are classified., Comment: 13 pages

Gauss first studied representations of self-intersecting curves in the plane using only lists of their crossings in the sequence as they occur when traversing a curve, i.e., representations using Gauss words. The characterisation of words that are Gauss words has been elusive for a long time, and only in recent decades have some good characterizations been established. Together with these, the interest in Gauss paragraphs, i.e., representations of sets of curves by sets of words listing their sequences of crossings, has came to light, and we are unaware of a (good) characterization of abstract sets of words that are Gauss paragraphs. We establish such a characterization and we show that characterizing Gauss paragraphs is algorithmically equivalent to characterizing Gauss words, as there exists a word ?$W$? that can be obtained from a set of words ?$P$? in linear time, such that ?$P$? is a Gauss paragraph if and only if ?$W$? is a Gauss word. Gauss je prvi študiral reprezentacije samo-sekajočih se krivulj v ravnini zgolj s pomočjo seznamov njihovih križišč v zaporedju, kot jih srečujemo, ko potujemo po krivulji, t.j. reprezentacij z uporabo Gaussovih besed. Karakterizacija besed, ki so Gaussove, je bila dolgo odprt problem in šele v zadnjih desetletjih je bilo odkritih nekaj dobrih karakterizacij. Obenem s tem se je okrepilo zanimanje za Gaussove paragrafe, t.j. reprezentacije množic krivulj z množicami besed, ki navajajo njihova zaporedja križišč. Ne zavedamo se nobene (dobre) karakterizacije abstraktnih množic besed, ki so Gaussovi paragrafi. Podamo takšno karakterizacijo in pokažemo, da je karakterizirati Gaussove paragrafe algoritmično ekvivalentno karakterizaciji Gaussovih besed, saj obstaja beseda ?$W$?, ki jo lahko dobimo iz množice besed ?$P$? v linearnem času, tako da je ?$P$? Gaussov paragraf, če in samo če je ?$W$? Gaussova beseda.

We prove lower bounds on the maximum genus of a graph in terms of its connectivity and Betti number (cycle rank). These bounds are tight for all possible values of edge-connectivity and vertex-connectivity and for both simple and non-simple graphs. The use of Nebeský's characterization of maximum genus gives us both shorter proofs and a description of extremal graphs. An additional application of our method shows that the maximum genus is almost additive over the edge cuts. Določimo spodnje meje za maksimalni rod grafa v smislu njegove povezanosti in Bettijevega števila (cikličnega ranga). Te meje so ostre za vse možne vrednosti povezavne-povezanosti in vozliščne-povezanosti ter veljajo tako za enostavne kot tudi ne-enostavne grafe. Uporaba Nebeskýjeve karakterizacije maksimalnega rodu nam daje ne samo krajše dokaze ampak tudi opis ekstremalnih grafov. Dodatna aplikacija naše metode pokaže, da je maksimalni rod skoraj aditiven nad povezavnimi rezi.

A cellular embedding of a connected graph (also known as a map) on an orientable surface has trinity symmetry if it is isomorphic to both its dual and its Petrie dual. A map is regular if for any two incident vertex-edge pairs there is an automorphism of the map sending the first pair onto the second. Given a map M with all vertices of the same degree d, for any e relatively prime to d the power map Me is formed from M by replacing the cyclic rotation of edges at each vertex on the surface with the e th power of the rotation. A map is kaleidoscopic if all of its power maps are pairwise isomorphic. In this paper, we present a covering construction that gives infinite families of kaleidoscopic regular maps with trinity symmetry.

We consider complete multigraphs $${K_n^m}$$ K n m on n vertices with every pair joined by m edges. We embed these graphs to triangulate $${S_n^k}$$ S n k , a pinched surface with n pinch points each having k sheets. These embeddings have a vertex at each pinch point and any two sheets at a pinch point have the same number of edges. Moreover, we want to 2m-color the faces such that each color class is a Steiner triple system. These embeddings generalize in two ways biembeddings of Steiner triple systems, the case m = 1, k = 1 of simple graphs in surfaces without pinch points.

Let G = (V, E) be a simple graph and let T = (P, B) be a Steiner triple system. Let ? be a one-to-one function from V to P. Any edge e = {u, v} has its image {?(u), ?(v)} in a unique block in B. We also denote this induced function from edges to blocks by ?. We say that T represents G if there exists a one-to-one function ? : V ? P such that the induced function ? : E ? B is also one-to-one; that is, if we can represent vertices of the graph by points of the triple system such that no two edges are represented by the same block. In this paper we examine when a graph can be represented by an STS. First, we find a bound which ensures that every graph of order n is represented in some STS of order f(n). Second, we find a bound which ensures that every graph of order n is represented in every STS of order g(n). Both of these answers are related to finding an independent set in an STS. Our question is a generalization of finding such independent sets. We next examine which graphs can be represented in STS's of small orders. Finally, we give bounds on the orders of STS's that are guaranteed to embed all graphs of a given maximum degree.

Steinitz's theorem states that a graph is the 1-skeleton of a convex polyhedron if and only if it is 3-connected and planar. The polyhedron is called a geometric realization of the embedded graph. Its faces are bounded by convex polygons whose points are coplanar. A map on the torus does not necessarily have such a geometric realization. In this paper we relax the condition that faces are the convex hull of coplanar points. We require instead that the convex hull of the points on a face can be projected onto a plane so that the boundary of the convex hull of the projected points is the image of the boundary of the face. We also require that the interiors of the convex hulls of different faces do not intersect. Call this an exhibition of the map. A map is polyhedral if the intersection of any two closed faces is simply connected. Our main result is that every polyhedral toroidal map can be exhibited. As a corollary, every toroidal triangulation has a geometric realization.

The spindle surface S is the pinched surface formed by identifying two points on the sphere. In this paper we examine cubic graphs that minimally do not embed on the spindle surface. We give the complete list of 21 cubic graphs that form the topological obstruction set in the cubic order for graphs that embed on S.A graph G is nearly planar if there exists an edge e such that G−e is planar. We show that a cubic obstruction for near-planarity is the same as an obstruction for embedding on the spindle surface. Hence we also give the topological obstruction set for cubic nearly planar graphs.

An open ribbon is a square with one side called the seam. A closed ribbon is a cylinder with one boundary component called the seam. We sew an open (resp. closed) ribbon onto a graph by identifying the seam with an open (resp. closed) walk in the graph. A ribbon complex is a graph with a finite number of ribbons sewn on. We investigate when a ribbon complex embeds in 3-dimensional Euclidean space. We give several characterizations of such spatial complexes which lead to algorithms. We examine special cases where (1) each edge of the graph is incident with at most three ribbons, and (2) every ribbon is closed together with a connectivity condition.

Let G be a graph embedded in the sphere. A k-nest of a point x not in G is a collection C1,…,Ck of disjoint cycles such that for each Ci, the side containing x also contains Cj for each j

A Heffter array is an m by n matrix with nonzero entries from Z_{2mn+1} such that i) every row and column sum to 0, and ii) no element from {x,-x} appears twice. We construct some Heffter arrays. These arrays are used to build current graphs used in topological graph theory. In turn, the current graphs are used to embed the complete graph K_{2mn+1} so that the faces can be 2-colored, called a biembedding. Under certain conditions each color class forms a cycle system. These generalize biembeddings of Steiner triple systems. We discuss some variations including Heffter arrays with empty cells, embeddings on nonorientable surfaces, complete multigraphs, and using integer in place of modular arithmetic., Comment: 18 pages

It is shown that ⌈β(G)/3⌉ is the tight lower bound on the maximum genus γM(G) of 2-edge-connected simplicial graphs, where β(G) is the cycle rank of the graph G. Also, a systematic method is developed to construct 3-vertex-connected simplicial graphs G satisfying the equality γM(G) = ⌈β(G)/3⌉. These two results combine with previously known results to yield a complete picture of the tight lower bounds on the maximum genus of simplicial graphs.

The orientable genus of a graph is the minimum number of handles needed to embed that graph on a surface. Determining the genus of a graph is a fundamental yet very difficult problem. In this paper we show that the orientable genus of a randomly selected graph on n vertices has a strong tendency towards n2/24. More strongly, we give upper and lower bounds on the genus which hold for almost all graphs. We extend our results to the graph model in which the edge-probability varies with the order of the graph and to the model in which the number of edges is preordained. We also give the analogous bounds for the nonorientable genus. Loosely speaking, a random graph almost always has embeddings on both orientable and nonorientable surfaces which are nearly triangulations.

In this paper we examine self-dual embeddings of complete multipartite graphs, focusing primarily on Km(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 triple system ( v , 3, λ) is indecomposable if it is not the union of two triple systems ( v , 3,λ 1 ), ( v , 3, λ 2 .) with λ = λ 1 + λ 2 . A triple system is simple if it has no repeated blocks. In this paper we show the existence of simple indecomposable triple systems for all v and λ satisfying the necessary conditions with v large. Specifically, for each λ we show that there is a v 0 (λ) (where v 0 (λ) = O(λ 4 )) such that there exists a simple indecomposable triple system ( v , 3, λ) for each v ⩾ v 0 (λ) with λ v ( v - 1) ≡ 0 (mod 6) and λ( v - 1) ≡ 0 (mod 2). We then concentrate on the case of λ = 5 and show that v 0 (5) ⩽ 25.

In this paper we examine self-dual embeddings of the complete bipartite graph K n , m on both orientable and nonorientable surfaces. It can be quickly established that such an embedding can exist only if both n and m are even integers exceeding 2. We show by construction that these necessary conditions are sufficient, except that there is no orientable self-dual embedding of K 6,6 .

In this paper we consider spherical polyhedra, or equivalently 3-connected embedded planar graphs. A self-duality map sends vertices to faces and faces to vertices while preserving incidence. We give six constructions of polyhedra with self-duality maps and show that these constructions yield all such polyhedra. Included is the construction of polyhedra which admit only self-duality maps of large order.

Let G be a graph embedded in a surface S . The face-width of the embedding is the minimum size | C ⋔ G | over all noncontractible cycles C in S . The face-width measures how densely a graph is embedded in a surface, equivalently, how well an embedded graph represents a surface. In this paper we present a construction of densely embedded graphs with a variety of interesting properties. The first application is the construction of embeddings where both the primal and the dual graph have large girth. A second application is the construction of a graph with embeddings on two different surfaces, each embedding of large face-width. These embeddings are counterexamples to a conjecture by Robertson and Vitray. In the third application we examine the number of triangles needed to triangulate a surface S such that every noncontractible cycle is of length at least k . Surprisingly, for large g the number is approximately 4 g , regardless of k . The fourth application is the construction of trivalent polygonal graphs. We close with some observations and directions for further research.

The complete multigraph λK 2n has 2n vertices and λ edges joining each pair of vertices. In this paper we examine 1-factorizations of λK 2n is equivalent to a collection of 1-factors of K 2n such that every edge of K 2n appears in exactly λ 1-factors. This collection of 1-factors is simple if no 1-factor is repeated. It is indecomposable if no subset of 1-factors contains each edge λ' times where 1≤λ'≤λ−1

A covering is a graph map φ: G→H that is an isomorphism when restricted to the star of any vertex of G. If H is connected then |φ −1 (v)| is constant. This constant is called the fold number. In this paper we prove that if G is a planar graph that covers a nonplanar H, then the fold number must be even

This paper surveys recent results on self-dual polyhedra. These results include a complete set of constructions for spherical self-dual polyhedra. We discuss similar constructions for projective-planar polyhedra. We next give a construction of involutory polyhedra for general surfaces. We describe an additive construction and a recursive construction. We give some specific results concerning embeddings where both the primal and dual graphs are either complete graphs or complete bipartite graphs. Finally, we give some directions for future research.

We investigate the computational complexity of determining if a graph G on v vertices embeds in a surface S. Robertson and Seymour have given an O(v 3) decision algorithm for this embedding problem. We show here how the use the yes/no output from their algorithm to construct the embedding, that is, we self-reduce the search algorithm to the decision algorithm. We conclude that for each fixed surface S there exists an O(v 10) algorithm for constructing an embedding or answering that no embedding exists.

Let Σ denote a surface. A graph G is irreducible for Σ provided that G does not embed in Σ, but any proper subgraph does so embed. Let I ( Σ ) denote the set of graphs without degree two vertices which are irreducible for Σ. Observe that a graph embeds in Σ if and only if it does not contain a subgraph homeomorphic to a member of I ( Σ ). For example, Kuratowski's theorem shows that I ( Σ ) = { K 3,3 , K 5 } when Σ is the sphere. In this paper we prove that the set I ( Σ ) is finite for each nonorientable surface, setting in part a conjecture of Erdos from the 1930s.

A graph G is a k-amalgamation of two graphs G1 and G2 if G = G1 ∪ G2 and G1 ∩G2 is a set of k vertices. In this paper we show that γ(G) differs from γ(G1) + γ(G2) by at most a quadratic on k, where γ denotes the nonorientable genus of a graph. In the sequel to this paper we show that no such bound holds for the orientable genus of k-amalgamations.

Row-complete Latin squares of orders 9, 15, 21 and 27 are given. The square of order 9 is the smallest possible odd order row-complete Latin square.

A graph G is a k-amalgamation of two graphs G1 and G2 if G = G1 ∪ G2 and G1 ∩ G2 is a set of k vertices. In this paper we construct 3-amalgamations Gn = Hn ∪ Hn such that γ(Gn) = 5n and γ(Hn) = 3n, where γ denotes the orientable genus of a graph. Thus γ(G1 ∪ G2) may differ from γ(G1) + γ(G2) by an arbitrarily large amount for amalgamations over 3 (or more) vertices. In contrast, an earlier paper shows that the nonorientable genus of a k-amalgamation differs from the sum of the nonorientable genera of its parts by at most a quadratic on k.

For an integer n ⩾ 1, a graph G has an n-constant crossing number if, for any two good drawings ϕ and ϕ′ of G in the plane, μ(ϕ) ≡ μ(ϕ′) (mod n), where μ(ϕ) is the number of crossings in ϕ. We prove that, except for trivial cases, a graph G has n-constant crossing number if and only if n = 2 and G is either Kp or Kq,r, where p, q, and r are odd.