main-content

## Über dieses Buch

Graph Theory is a part of discrete mathematics characterized by the fact of an extremely rapid development during the last 10 years. The number of graph theoretical paper as well as the number of graph theorists increase very strongly. The main purpose of this book is to show the reader the variety of graph theoretical methods and the relation to combinatorics and to give him a survey on a lot of new results, special methods, and interesting informations. This book, which grew out of contributions given by about 130 authors in honour to the 70th birthday of Gerhard Ringel, one of the pioneers in graph theory, is meant to serve as a source of open problems, reference and guide to the extensive literature and as stimulant to further research on graph theory and combinatorics.

## Inhaltsverzeichnis

### On the Problem of Relative Components of Minimal Graphs

1935, D.König asked the question on page 199 in his famous book with the title “Theorie der endlichen und unendlichen Graphen” whether there exists a Kuratowski-type theorem for every closed orientable surface Fp, p ∈ N0. The modern version of Kuratowski’s theorem is:The minimalbasis M1(F0) consists of exactly two graphs, the so-called Kuratowski graphs K3,3 and K5 with M1(F0) = {K3,3,K5}, where the minimalbasis M1(F0) is defined as the set of all >1-minimal graphs of the set Γ(F0) ⊂ Γ of all nonplanar graphs. Γ stands for the set of all finite undirected graphs without loops and multiple edges and >1 is the well-known subdivision relation on Γ or Γ(F0), respectively.

R. Bodendiek, K. Wagner

### Irregular Assignments and Two Problems à la Ringel

One of the best-known facts in graph theory states that any (simple) graph with at least two vertices contains two vertices of the same degree. Hence the following problem, initiated in [5], arises: Consider a weighting w: E(G) → {1,..., m} and denote by $$w(v)=\sum\limits_{\ell \in e}{w(e)}$$ the weighted degree of the vertex υ ∈ V. We call the weighting w admissible or an irregular assignment if all weighted degrees are distinct. What is the minimum number m for which an admissible weighting exists? This number s(G) is called the irregularity strength of G. Our observation above shows s(G) ≥ 2 for any graph G, and it is an easy exercise to show that s(G) < ∞ iff G has no isolated edge and at most one isolated vertex.

M. Aigner, E. Triesch

### A Recursive Bound for the Number of Complete K-Subgraphs of a Graph

The following inequality was conceived as a tool in determining coloring numbers in the sense of Ahlswede, Cai, Zhang ([1]), but developed into something of a seemingly basic nature.

R. Ahlswede, N. Cai, Z. Zhang

### One-Factorizations of Tensor Products of Graphs

A very natural question raised about products of graphs is the following. Do there exist necessary and sufficient conditions on a pair (G,H) of graphs for their product to have some specified property? In particular, for which graphs is the product one-factorizable? Sufficient conditions have been investigated for the cartesian, lexicographic, and tensor products in [3], [4], and [5]. However, the conditions for the tensor product to be one-factorizable are significantly more scanty than those for the other products. The purpose of this paper is to correct this situation somewhat.

B. Alspach, J. C. George

### Non-Commutative Geometry and Graphs

Objects of this paper are complete digraphs (directed simple graphs). A colouring of such a digraph is a mapping from the vertices and the arcs onto a set F of colours. We assume that vertices and arcs are differently coloured but do provisionally no further restrictions. Following J. Pfalzgraf [8] we denote this mapping by <,>. Thus <x,x’> is the colour of the arc (x,x’) if x ≠ x’ and of the vertex x if x = x’. Such a coloured complete digraph is also called a P-space. We interpret the vertices and colours as proper and improper points resp. and define the line (Linie) x□x’ by (2.1), (2.2). Generally x□x’ ≠ x’□x, i.e. the space need not be commutative. A simple example of such a (noncommutative) space is the circle-space: Here X :=R2 and the line xqx’ is the circle through x’ with the center x, and its improper point is its radius. Two lines with the same improper point are parallel. Two different parallel lines, however, need not have an empty intersection. The first two sections give a brief introduction to the P-spaces, for more details (with further references) see [2]. Subspaces are point sets being closed with respect to drawing of lines and parallels. A straight line (Gerade) is a line which is also a subspace (sect.3). Arbitrary P-spaces are too general for establishing a reasonable theory. Therefore we additionally assume geometrical conditions which are generalizations of the well known Desargues theorem in affine spaces: We define a sequence Simq (q∈N)of geometrical conditions. The simplest non trivial case q = 2 leads to the skewaffine spaces. A skewaffine space with commutative □ is affine. An application of the theory of Ramsey-numbers leads to a theorem that a finite selfadjoint skewaffine space in which the number of proper points is large to that of improper points possesses a staight line (Theorem 6.1). The following Theorem 6.2 specializes this property to permutation groups. In the two concluding sections we consider finite P-spaces and their connections to adjaceny-matrizes and hence to algebraic graph theory. A geometric characterization of distance regular graphs is stated in Theorem 8.2. It might be fruitful to enlarge this theory in order to obtain further relations between graph theory and geometry.

J. André

### The Complexity of the Graph Embedding Problem

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(v3) 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(v10) algorithm for constructing an embedding or answering that no embedding exists.

D. Archdeacon

### Helly Theorems for Dismantlable Graphs and Pseudo-Modular Graphs

The geodesic convexity of a graph consists of all those subsets of the vertex-set which contain all geodesics (i.e., shortest paths) joining any two of its elements. The Helly number of this convexity is trivially bounded from below by the clique number (i.e., the size of a largest clique). We show that equality between the two numbers hold for graphs which are dismantlable (alias cop-win) or pseudo-modular. This generalizes previously known results for chordal graphs and distance-hereditary graphs, due to Čepoj, Duchet, Jamison and Nowakowski, respectively.

H.-J. Bandelt, H. M. Mulder

### On the Level-Oriented Two-Dimensional Packing With Rotation of the Rectangles

Coffman, Garey, Johnson and Tarjan /1/ have considered the following two-dimensional packing problem: Given a collection of rectangles and a bin with fixed width and unbounded height, pack the rectangles into the bin so that no two rectangles overlap and so that the height to which the bin is filled is as small as possible. We assume that the given rectangles are oriented, each having a specified side that must be parallel to the bottom of the bin. We also assume, with no loss of generality, that the bin width has been normalized to 1 and that width and height of all rectangles are generally less than or equal to 1.

G. Bär

### On Planar Tilings With Finitely Many Sorts of Tiles

The area of mathematical tilings has been of interest for a long time. It is not only an exciting collection of a great deal of artistic tilings but it contains deep theorems and a lot of interesting open problems. Although quite complicated new tilings and theorems are being found there is still much to be discovered.

K. Bezdek

### Examples of Space-Tiling Polyhedra Related to Hilbert’s Problem 18, Question 2

Let P be a connected polyhedron in the d-dimensional Euclidean space Ed. A system {Pi} of congruent copies of P, whose union is Ed and whose interiors are mutually disjoint, is called a tiling. If each Pi is a translate of P, then {Pi} is a tiling by translates. If there exists a subgroup G of the group of isometries of Ed, such that {Pi} = {m(P): m∈ G}, then {Pi} is a tiling by a group of motions,also called (see [5]) a tile-transitive tiling or an isohedral tiling.

A. Bezdek, W. Kuperberg

### The Historical Background to Gerhard Ringel’s Work

The ancestry of Ringel’s work on the Heawood formula can be traced back to the Ancient Greeks. The Greeks were interested in the mathematical properties of regular polyhedra (where all the faces are congruent regular polygons), and found that there are just five such solids. A full account was written by Theaetetus around 400 BC, and it has been argued that Euclid’s Elements (c. 320 BC) was primarily an introduction to the study of these regular polyhedra. But there is no evidence that the Greeks knew the simple formula relating the numbers v, e and f of vertices, edges and faces of a polyhedron — namely,that v−e + f = 2.

N. L. Biggs, E. K. Lloyd, R. J. Wilson

### Around Three Lemmas in Hamiltonian Graph Theory

Three recent lemmas have led to results in hamiltonian graph theory which generalize and unify many previous results. Several applications of the lemmas, especially to 1-tough graphs, occur in a survey by Bauer, Schmeichel and Veldman. Recent additional applications are surveyed here. In particular, the lemmas are used to obtain an alternative proof of a recent result of Flandrin, Jung and Li.

D. Bauer, H. J. Broersma, H. J. Veldman

### A Note on Metric Properties of Infinite Graphs

Throughout this note by a graph G we mean an undirected connected graph without loops or multiple edges, defined on a countably infinite vertex set V(G). The edge set of G is denoted by E(G) and the valency of a vertex x of G by v(x:G). A graph G is said to have universally bounded valencies if there is positive number L such that v(x:G) = L for all x ∈ V(G).

T. Böhme

### Automorphism Groups of Directed Cayley Graphs

A famous result of R. Frucht (1938) initiated a widespread interest for investigating automorphism groups of graphs. Cayley graphs are essential to the construction of graphs whose automorphism groups are isomorphic with a given abstract group. Many authors realized the proposal of L. Babai /2/ to investigate properties of Cayley graphs. In this field it is obvious to concern with automorphism groups of these graphs, N. Biggs, W. Imrich, M. Watkins et al. obtained interesting results for.

U. Baumann, M. Lesch, I. Schmeichel

### Triangular Embeddings of Tensor Products of Graphs

Given triangular embeddings of graphs G and H and an assignment of signs ±1 to the angles of the embedding of G,with the property that the sum of the signs around each vertex of G is ±1 and the product of the four signs at each edge is +1, triangular embeddings of the tensor (also called categorical) product G⊗H of G and H are constructed. This generalizes previously known results about embeddings of tensor products of graphs.

A. Bouchet, B. Mohar

### Computing Light Edges in Planar Graphs

We consider planar graphs and pseudographs with the sets of vertices V, edges E, and faces F. Remind that unlike pseudographs, graphs do not contain loops and multiple edges. The weight w(e) of an edge e=(a,b) is defined to be the degree sum s(a)+s(b) of its end vertices. Kotzig proved [5] that each 3-connected planar graph contains an edge of the weight at most 13, the bound being the best possible. This result was further developed in various directions by Kotzig and his followers [1–6,8,10]. The interest to these investigations increased recently due to discovering its applications in coloring problems [1]. Thus, Kronk and Mitchem’s conjecture Xvef(G)≤Δ(G)+4 [7] on entire coloring the vertices, edges, and faces of planar graphs with the maximal degree,Δ(G) was proved [1] for Δ(G)≥12. (The case Δ(G)=3 was solved in [7].) Moreover, for Δ(G)≥18 we have the precise bound Xvef(G)≤Δ(G)+2 [1].

O. V. Borodin

### On the Domination Problem for Bipartite Graphs

The Domination problem on graphs is one of the basic algorithmic problems on graphs and can be formulated as follows: Let G=(V,E) be a graph which is finite, undirected and simple (i.e. without self-loops and multiple edges).

A. Brandstädt

### Polyhedral Maps with Few Edges

We give a lower bound for the number of edges which a polyhedral map of given topological type can have. For several manifolds we find the exact minimal value for the number of edges.

U. Brehm

### Aut G m,n for the Hasse Graph G m,n of the Subword Poset B m,n of an m-Ary Cyclic Word of Length n

There exists a rich literature on automorphism groups for (undirected) graphs. This subject is specially developed for distance transitive graphs (one of them is the n-cube). We consider here a non distance transitive graph Gm,n obtained from the hypercube by identifying some of its vertices and we charcaterise its automorphism group in terms of Sp the symmetric group on p elements. Starting point for this study has been when investigating the poset Bm,n of all sub-words from a given word of length n: $${{\text{u}}_{\text{m,n}}}=....\left( \text{m-1} \right)01....\left( \text{m-1} \right)............01....\left( \text{m-1} \right)01...\left( \text{r-1} \right),$$ where n=qm+r with 0≤r<m. Gm,n is just the Hasse graph of Bm,n . Gm,n for n≤m is an n-dimensional cube Qn . The automorphism group of Bm,n (as a poset) were characterised for m=2 in [Bu Fr Rö] and in general in [Bu Gr La].

G. Burosch, J.-M. Laborde

### Status of Graceful Tree Conjecture in 1989

The root of graph labellings go back to a problem stated by Gerhard Ringel. Let T be a given tree with n vertices; then the edges of K2n−1 can be partitioned into (2n−1) trees isomorphic to T [1]. A.Rosa in his well-known 1966 paper mentioned stronger version of this conjecture which was attributed to A. Kotzig. Let T be a given tree with n vertices, then the edges of K2n−1 can be partitioned cyclically into (2n−1) trees isomorphic to T [2]. Rosa was first to give the connections of these conjectures with certain valuations (labellings) of the vertices of a tree [2] but the name “graceful” was coined by Golomb [3] which popularizes the β-labelling (in terms of Rosa’s terminolgy) problem of trees. As today well over 100 papers have appeared in the literature around these conjectures but none of them have triggered any single hope towards its resolution (e.g., see surveys [4], [5], [10]).

I. Cahit

### Embedded Graphs, Facial Colorings, and Double Cycle Covers

We use the notation of Bondy and Murty [4], except that graphs have no loops. Let H be a subgraph of G. The contractionG/H is the graph obtained from G by contracting all edges of H and deleting any resulting loops. Denote $$O(G)=\{odd-\deg ree\,vertices\,of\,G\}.$$

P. A. Catlin

### On Peripheral Vertices in Graphs

The periphery of a graph G is the subgraph of G induced by the vertices in G whose eccentricity equals the diameter of G. Graphs that are peripheries of graphs with specified diameter are characterized. For a graph G, the antipodal graph A(G) of G is the graph having the same vertex set as G and edge set E(A(G)) = {uv ∣ u, v ∈ V(G) and dG(u, v) = diam G}. For a graph G and positive integer n, the nth iterated antipodal graph An(G) of G is defined as the graph A(An−1(G)) where Al(G) is A(G) and A0(G) denotes G. It is shown that there exist nonnegative integers n1 and n2 such that n1 < n2 and $${{A}^{{{{n}_{1}}}}}(G) \cong {{A}^{{{{n}_{2}}}}}(G)$$. The smallest postitive integer k for which there exists an integer ℓ such that Aℓ(G) ≅ Aℓ+k(G) is called the antipodal period of G. It is shown that for every positive integer k there exists a graph with antipodal period k.

G. Chartrand, G. Johns, O. R. Oellermann

### The Vertex-Degrees of Steiner Minimal Trees in Minkowski Planes

The Steiner problem of minimal trees has been considered in the plane with Euclidean and rectilinear norm (c.f. for instance /1/ and /2/). We intend to discuss this problem for arbitrary Minkowski planes.

D. Cieslik

### Unfolding Weighted Consensus Orders into Consistent Numerical Scales

The aim of this paper is twofold: first, to introduce an apparently new model in the factor analysis of preference data; second, to establish several related theoretical results about ordered sets, which seem to be of independent mathematical interest.

J. Czyzowicz, A. Pelc, I. Rival

### Forbidden Ordered Subgraphs

There are many special classes of undirected graphs which occur permanently in the literature in several contexts. These classes are interesting for their structural properties, and they are motivated from applications.

P. Damaschke

### On Normal Tournaments with the Least Number of 3-Cycles

We prove that all but one of the hamiltonian tournaments of order n (n>4) with the least number of 3-cycles are normal tournaments and we characterize these tournaments among normal tournaments.

D. C. Demaria, G. M. Gianella

### Two-Irregular Graphs

One of the most elementary results in graph theory is that a graph on n vertices must have at least two it its vertices with the same degree. Thus, it seems natural to consider those graphs in which no more than two of its vertices have the same degree for each possible degree, and we call such a graph 2—irregular.

R. J. Faudree, R. J. Gould, M. S. Jacobson, R. H. Schelp

### Cell Complexes and Lower Bounds in Computational Geometry

The characterization of the intrinsic complexity of computation problems by upper and lower bounds is one of the major tasks in computational geometry. In the model of algebraic computation trees almost all known nontrivial lower bounds are of order Ω(n log n), where n is a parameter associated with the input size of such problems. The main purpose of this paper is to present a combinatorial technique which allows to derive lower bounds exceeding this barriere.

Th. Fischer

### Characterizing Directed Postman Tours

In 1960 Guan Meigu proved a characterization of postman tours in (undirected) graphs, which does not hold for digraphs. We present a characterization of directed postman tours analogous to the undirected case.

H. Fleischner, E. Wenger

### Some Properties of ”Almost All” Functions From

This paper treats some properties of “almost all” k-valued functions connected to the different kinds of dependence of functions on their arguments.

I. D. Giudjenov

### Composition of Facets of the Clique Partitioning Polytope

In [1] we have introduced the clique partitioning problem and studied the associated polyhedron, the so-called clique partitioning polytope. In this paper we continue these polyhedral investigations; in particular, we present new classes of facets and methods to construct new facet-defining inequalities from given facet-defining inequalities.

M. Grötschel, Y. Wakabayashi

### Optimal Edge-Numbering of Binary Trees

Let G = (V,E) be a graph with vertex-set V(G) and edge-set E(G). A 1-1 mapping f: E(G)→{1,2,..., |E(G)|} will be called an edge-numbering of G. E(v) means the set of all edges of G which are incident to the vertex v of G. Define $$\begin{gathered} {{D}_{f}}(v) = \max \quad \left| {f(e) - f(e')} \right|\;and \hfill \\ \quad \quad \quad \;e,e' \in E(v) \hfill \\ {{W}_{f}}(G) = \max \quad {{D}_{f}}(v)\; \cdot \hfill \\ \quad \quad \quad \;v \in V(G) \hfill \\ \end{gathered}$$$${{W}_{f}}\left( G \right)=\max {{D}_{f}}\left( v\right).$$

N. Grünwald

### On Independent Vertices and Edges of a Graph

Let the numbers of k-element sets of independent vertices and edges of a graph G be denoted by n(G,k) and m(G,k), respectively. Some properties of the numbers n(G,k) and m(G,k) are outlined. In particular, it is shown that the circuits are the only connected graphs for which the equality n(G,k) = m(G,k) is satisfied for all values of k.

I. Gutman

### The Outerthickness & Outercoarseness of Graphs I. The Complete Graph & The n-Cube

Many of the results of this paper were announced without proof in [9]; a parallel paper, discussing the complete bipartite graph, will appear in [11]. Some results were also obtained independently by L.S. Mel’nikov and presented at the 6th Hungarian Combinatorics Colloquium in Eger on 81-07-10.

R. K. Guy, R. J. Nowakowski

### On Some Graphic Aspects of Addition Theorems

During the last fifty years, Davenport, Mann, Kempermann and many others proved some inequalities relating the cardinality of the sum of two sets in a group to the cardinalities of the original sets. This subject is known as Additive Group Theory.Almost all these questions have a natural interpretation as statements about the connectivity of Cayley directed graphs.The Cauchy-Davenport theorem is equivalent to the fact that a Cayley graph with prime order has connectivity equal to the outdegree. Chowla’s Theorem says that the same property holds for Cayley graphs on ℤn defined by subsets of ℤn*.We was able to prove a common generalization to several addition theorems with the following graphic interpretation.Let G be a finite Abelian group and B⊂G\0. There exists a nonnull subgroup H of G such that any cut separating two elements of H has cardinality at least $$\left| B \right|$$. In other words the local connectivities inside H are optimal.This subgroup exists also when the group is not Abelian and B=B−1.

Y. O. Hamidoune

### On the Circumference of Regular Polyhedral Graphs

Consider the class Γ of all 3-regular polyhedral graphs, that is, the class of the planar 3-connected graphs in which each vertex has degree 3. Let C be a circuit of a graph G∈Γ. If one removes from G the vertices of C and all edges incident with them, the resulting graph G-C disintegrates into connected components K1,K2,...,KK. If C is a hamiltonian circuit of G (that is a circuit containing all vertices), then G-C is obviously empty, but in all other cases, however, k > 0 holds. Let Ci be the set of those vertices of C having at least one neighbour in Ki. Since each vertex has the degree 3 in G, a vertex from Ci is incident with exactly one edge which does not belong to C, that is, this vertex is adjacent to one vertex from Ki. In addition, there exists for any vertex x∈ C at most one index i such that x is adjacent to one vertex of Ki. If one adds to Ki the vertices of Ci and also all edges whose one end-vertex belongs to Ci and the other one to Ki, then the resulting graph Bi is called a bridge of G over C. Calling also an edge whose two end-vertices belong to C, but not the edge itself, a bridge, then we see that to each vertex of C there exists exactly one bridge in which this vertex lies. A vertex belonging to both C and Bi is called a touch point of the bridge Bi. Let a bridge over a path be defined accordingly. Let Γ (w) be the class of graphs G in in which there exists for any longest circuit C of G a bridge B over C with at least w touch points.

J. Harant, H.-J. Walther

### Longest Cycles in Circulant Graphs

In 1969 L. LOVASZ /2/ conjectured that every connected vertex transitive graph has a Hamilton path. L.BABAI /1/ proved the validity of this conjecture for graphs with a prime number of vertices. In the same paper he stated, that no useful results on the length of longest cycles in vertex transitive graphs are known. In this paper we generalize the result of /1/ in two directions.

W. Harnau, D. Jordan

### Spanning Trees of the Complete Bipartite Graph

A new proof that the number of spanning trees of K m,n is mn−1nm−1 is presented. The proof is similar to Prüfer’s proof of Cayley’s formula for the number of spanning trees of K n .

N. Hartsfield, J. S. Werth

### A Combinatorial Theorem Which is Related to the Invariance of the Separating Set for the Plane

In this paper we present a theorem, which is related to theorems which were proved in [2]. The starting point of the latter paper was the qualitative part of the separation theorem of Jordan/Brouwer/Alexander, that means the invariance of the (non-) separating set:(I) If K is a compact subset of ℝn which does not separate ℝn, and if f: K→ℝn is an injective and continuous mapping, then f(K) also does not separate ℝn.

E. Harzheim

### On Certain Trees in Hypercubes

The aim of this contribution is to give a survey of some basic notions, known facts, conjectures and open problems about embedding trees into hypercubes, and the related problem of spanning trees of hypercubes. A new result in this direction is also presented.

I. Havel

### Extending Hall’s Theorem

Let G be a finite simple graph. Suppose that to each vertex v ∈ V(G) there is assigned a finite set (or “list”) C(v) of colours (or “symbols”). The general problem is: what conditions on G and the colour-set assignment C guarantee that the vertices of G can be coloured so that each v ∈ V(G) is coloured with a colour from C(v), and adjacent vertices are coloured differently? Such a colouring of V(G) will be called a C-colouring of G.

A. J. W. Hilton, P. D. Johnson

### On the Coupling Condition and Hamiltonicity

The coupling condition is a necessary and sufficient condition for a graph to be hamiltonian. It is shown that the condition also applies to directed graphs and hypergraphs.

C. Hoede, H. J. Smit

### Transversals and Matroids

The first application of matroids in transversal theory goes back to the early forties and since then they have played the essential role in this area. As a matter of fact, there are two fundamental results concerning both transversals and matroids. In [9] Rado established a necessary and sufficient condition for a finite family of sets to possess a transversal which is independent in a given matroid. The second result, stated by Edmonds and Fulkerson [3], says that the partial transversals of a finite family of sets form a matroid. The two theorems lie at the very heart of transversal theory and therefore there are many variations and generalizations of them. A comprehensive survey of this field is in [7], for later ones see e.g. [10]. Yet, the generalizations of these classical results seem to go in different directions. In this paper it is shown that by means of k-transversals, introduced by Asratian [1] and originally called compatible transversals, it is possible to obtain “parallel” generalization of them.

P. Horák

### Classification and Construction of Geodetic Block with Diameter Two

In this paper we have been pointed out the classification and construction of geodetic block with diameter two and given the necessary and sufficient condition of the existence of geodetic block with diameter two. So we completely answered the questions of J.G.Stemple offered in the 1974.

M. Jingzhong

### Graph Distances and Similarity

How similar are the two graphs given in Figure 1? Of course this question has no unique answer. At first we must specify in what sense similarity between graphs is meant.

### Witt Rings and Semiorderings of Planar Ternary Rings

As we have seen in [3,4,5,6] a good part of the algebraic theory of reduced quadratic forms, orderings, and real places of commutative fields, as presented by, say Prestel [14] or Lam [8,9], goes over to arbitrary planar ternary rings (PTRs). One of the fundamental tools within these theories is the concept of quadratic semiorderings of fields, which allows sophisticated proofs of the representation criterion or the isotropy principle ([1,2]). For these reasons, it seems desirable, to establish and to study the notion of quadratic semiorderings also over arbitrary, formally-real PTRs.

F. B. Kalhoff

### Linear Inequalities Describing the Class of Intersecting Sperner Families of Subsets, I

Let X be a finite set of n elements. We say that the family A = {A1,..., A m } of its distinct subsets is intersecting if A i ∩ A j ≠ Ø holds for any 1 ≤ i ≤ j ≤ m. A classic theorem of Erdós Ko and Rado [2] states that an intersecting family A consisting of k-element subsets, where k ≤ n/2, has at most ($$\left( \begin{matrix} n-1 \\ k-1 \\ \end{matrix} \right)$$) members.

G. O. H. Katona, G. Schild

### Integral Drawings of the Complete Graph K6

A drawing D(G) of a graph G is such a realization of G in the plane that the vertices of G are mapped into different points, called vertices of D(G), and the edges of G are mapped into Jordan curves connecting the maps of the incident vertices, called edges of D(G), and two edges of D(G) have at most one point in common, either a vertex or a crossing.

A. Kemnitz

### On Certain Binomial Sums

We investigate the following binomial sums: $${{A}_{p}}\left( m,n \right)=\underset{k=0}{\overset{n}{\mathop{\sum }}}\,{{k}^{p}}\left( \overset{m}{\mathop{k}}\, \right)k!{{m}^{n-k}},$$ where p, n are nonnegative integers, and m is a real number. These sums arise in complexity estimates of tests for equal entries of n-tuples (2). We derive recursive formulas (Theorem 1) and asymptotic representations (Theorem 2) of Ap(m,n) = Ap.

W. Klotz

### Colouring of Spider Graphs

Intersection graphs are an interesting topic of algorithmic graph theory: On the one side many well — known graph — theoretic problems which are NP — complete for general graphs become polynomially solvable if they are restricted to a class of intersection graphs. Hence studying intersection graphs can give information about the borderline between P and NP — if there is one. On the other side, intersection graphs are very useful to model problems in the natural, social and technical sciences (see e.g. [3]).

M. Koebe

### A Las-Vergnas Type Theorem for Trees

Let G be a connected simple graph. We study the maximal order of a subisce T ⊂ G with a given maximum degree Δ T . We obtained conditions on the degree sequence of a graph which are similar to that of Bondy and Las-Vergnas on the Hamilton cycle, and strengthen early results of Win |10| and the authors [4].

I. Krasikov, Y. Roditty

### Quick Gossiping by Multi-Telegraphs

Entringer and Slater /1/ considered the following communication problem: Suppose each of n≥2 points (persons) 1,2,...,n knows are item of information which is not known to all the others. They exchange information using telegrams arranged in consecutive rounds whereby in every round: (1)each point can either send or receive telegrams, i.e. it is impossible for a given point to send some and to receive other telegrams in the same round;(2)any pair r,s∈V={1,2,.,..,n} is allowed to communicate by a telegram, and if s sends a telegram to r, then in that round, r learns all information which s knows at this time;(3)every point can communicate with at most k different points (k≥1), i.e. depending on whether it is a sender or a receiver in that round the point can either send at most k telegrams or receive at most k telegrams.

R. Labahn, I. Warnke

### Numberings on Graphs Having Small Edge Weights

Numbering problems on graphs have been investigated intensively for the past three decades. One of the best known of these problems, the RINGEL—tree—numbering—problem, remains unsolved to he present. It consists in proving that all trees are graceful ([3],[7]). Another significant numbering problem on graphs is the bandwidth problem ([2]).

R. Lang

### On Vertexminimal Graphs with Radius r and Connectivity 2m

What is the minimal number of vertices in a graph with prescribed radius and with prescribed connectivity? In this paper we show following result: The minimal graph with radius r, r>7, and even connectivity 2m has 2m(r−1)+2 vertices and is unique.

G. Lassmann

### Embedding Schemes and the Jordan Curve Theorem

We survey several combinatorial embedding schemes that encode and generalize the concept of a map, and attempt to unify them. We also show that two combinatorial generalizations of the Jordan curve theorem arising from such schemes are in fact equivalent.

C. H. C. Little, A. Vince

### Subgraph Packing — A Survey

The research on factors of graphs concentrated mostly on factors satisfying certain local degree conditions, like regular factors or factors with degrees within prescribed intervals. More recently, also other kinds of factors have been investigated. Here we survey results on factors with prescribed components. Let F be a family of graphs. A graph G is said to have an F — factor if it has a factor each component of which is isomorphic to a member of family F The F — factor problem is to decide whether a given graph G admits an F — factor. The F — packing problem is to find a subgraph of maximum order which admits an F — factor.

M. Loebl, S. Poljak

### On the Radius of Random Subgraphs of the n-Cube

Dyer, Frieze and Foulds (cf. [1_]) introduced a general model of random subgraphs Gn of the n-cube graph Qn. We determine the radius R(Gn) of these random subgraphs Gn of Qn for fixed probabilities pv, pe satisfying 1/2 ≤ Pv pe< 1: With probability tending to one as n tends to infinity we haveR(Gn) = n − 1 if 1/2<Pv<1,R(Gn) = n if Pv = 1 and Pe>1/2,n − 1 ≤ R(Gn) ≤ n if Pv = 1 and Pe = 1/2 andn − 2 ≤ R(Gn) ≤ n − 1 if Pv = 1/2 and Pe = 1.

K. Mahrhold, K. Weber

### A Result in Combinatorial Matroid Theory

Defining the orthogonality in a matroid, we show that if an element is orthogonal to a set A, then it is also orthogonal to the span Ā of A.

D. Marcu

### On Graphs Embeddable with Short Faces

Genus embeddings of graphs whose genus is known are, for the most part, either triangular or quadrilateral, or differ from these in several exceptional faces. In order to determine all orientable surfaces in which such graphs have 2-cell embeddings it is sufficient to compute their maximum genus. So far, it has been known that every graph which triangulates some closed surface is upper embeddable, that is, its maximum genus is equal to [β/2], where β is its Betti number (Khomenko and Glukhov [2], Nebeský [3]). The main objective of the present paper is to generalize this result. We shall show that every graph admitting a 2-cell embedding in in some closed surface so that the length of every face does not exceed four is upper embeddable.

R. Nedela, M. Skoviera

### On Cyclic Representations of Triples by Pairs

The cyclic representation R(n,3,2) of triples by pairs is a system of pairs on a set E = {1,2,...,n} such that a)any triple T⊂E contains(is represented by) a pair D∈ R(n,3,2), b) the system R(n,3,2) posseses the automorphism π(i)=i+1,i=1,2,...,n,where the numbers i+1 are reduced modulo n.

J. Novák

### On the Steiner Periphery and Steiner Eccentricity of a Graph

Let G by a connected graph and S a nonempty set of vertices of G. Then the Steiner distance d(S) of S is the minimum number of edges in a connected subgraph of G that contains S. If n ≥ 2 is an integer, and G is a graph with at least n vertices, then the n-eccentricity e(n;v) of a vertex v is defined as max{d(S)|S ⊆ V(G), |S| = n and v ∈ S}. The n-radius rad n G is the minimum n-eccentricity over all vertices of G while the n-diameter is the maximum n-eccentricity over all vertices of G. The subgraph induced by those vertices with n- eccentricity rad n G is called the n-centre C(n;G) of G and the subgraph induced by those vertices with n- eccentricity diam n G is called the n-periphery P(n;G) of G. A vertex v is called n-eccentric if there exists a vertex u in C(n;G) and a set S of n vertices that contains both u and v such that d(S) = e(n;u) = rad n G. The subgraph of G induced by all n-eccentric vertices of G is called the n-eccentricity of G and is denoted by EC(n;G). It is shown that for a tree T of order at least n, P(n;T) = EC(n;T). Further, it is shown that all possible set-inclusion relations between P(n;G) and EC(n;G) may occur if G is not a tree.

O. R. Oellermann, H. C. Swart

### Cycles Containing Three Consecutive Edges in 2k-Edge-Connected Graphs

We consider finite undirected graphs possibly with multiple edges but without loops. Let G be a graph and let V=V(G) and E=E(G) be the set of vertices and edges of G respectively. We allow repetition of vertices (but not edges) in a path and cycle. λ(G) denotes the edge-connectivity of G. For X, Y⊂ V(G), with X ∩ Y= ø, ∂(X,Y) denotes the set of edges between X and Y. ∂(X) denotes ∂(X,V(G)−X), and is called a cut. A cut ∂(X) is called an n-cut if |∂(X)|=n, and will be called nontrivial if |X|≥ 2 and |V(G)−X| ≥2. We set e(X,Y):= |∂ (X,Y)| and e(X)= |∂(X)|. For an f ∈ E(G), V(f) denotes the set of end vertices of f. Cycles containing two (adjacent) edges in 2k-(k-)edgeconnected graphs reducing the edge-connectivity at most two are investigated in [3] ([2] and Mader [1]). We here consider cycles containing three consecutive edges.

H. Okamura

### Graph Distance and Euclidean Distance on the Grid

Given a connected graph G = (V, E),V = Z2, on the lattice points of the plane, let d G (p, q) and d(p,q) denote the graph distance and the Euclidean distance between p and q respectively. In this note we prove that for every є > 0 there is a graph G = Gє and a constant d = dє such that $$\left| {{d}_{G}}(p,q)-d(p,q) \right|<\varepsilon d(p,q)$$ for every pair p, q ∈ V with d(p, q) ≥ d. It remains open whether or not there is a graph G and a suitable constant K which satisfies $$\left| {{d}_{G}}(p,q)-d(p,q) \right|<K$$ for all p, q ∈ Z2 .

J. Pach, R. Pollack, J. Spencer

### About the Complexity of Some Homomorphism Problems on Graphs

Sometimes a graph may be considered as the discretization of some continuous structure, and it may be interesting to settle some problems, which appear to be mainly combinatorial in nature, in a discrete context. We deal here with the extension of homomorphism problems, the fixed point and the pursuit games problem, subwriting the connections which may exist between these questions, and discussing their respective complexity.

A. Quilliot

### On an Inequality of Sperner

Let n be an integer and let N be an n-element set. We will assume N={1,2,...,n}. We consider subsets of the set $$\left[ _{k}^{N} \right]$$ of all k-element subsets of N. Furthermore, we define the lower shadow ΔF of a family $$F\subseteq \left[ _{k}^{N} \right]$$ by ΔF={F:∃ G∈F, F⊂G, |G\F|=1}.

A. Rausche

### Counting Perfect Matchings in Lattice Graphs

This is partly joint work with Khaled Al-Khnaifes from Damascus who investigated relations between graph theory and linear algebra in his doctoral dissertation [1].

H. Sachs

### Genus — Minimal Edges and Kuratowski Subgraphs of a Graph

An edge e of a graph G will be said to be genus-minimal if $$\gamma \left( G-e \right)<\gamma \left( G \right)or\widetilde{\gamma }\left( G-e \right)<\widetilde{\gamma }(G)$$ where γ and $$\widetilde{\gamma }$$ denote the genus and the crosscap number ( = nonorientable genus), respectively. A graph G will be called minimal with respect to a closed surface S if G does not embed on S but every proper subgraph of G embeds on S. In particular, every edge of a minimal graph ( with respect to some closed surface) is genus-minimal.

J. Širaň

### From Tree Path-Factors and Doubly Exponential Sequences to a Binomial Inequality

The aim of this note is to report on a research that led to the formulation of the following constrained inequality between products of some binomial coefficients.

Z. Skupien

### A Characterization of Point-Colour-Symmetric Hypergraphs

A hypergraph X is a finite non-empty set V(X) together with a collection E(X) of distinct non-empty subsets of V(X). Elements of V(X) are called vertices and those of E(X) edges of the hypergraph X. An edge consisting of only one vertex is called a loop.

S. Sze-Chin

### A Linear Algorithm for the Pathwidth of Trees

The pathwidth is a graph parameter only recently studied but closely related to other characteristics of graphs like tree, band- or cutwidth, interval thickness or search number ([S]). The graphs considered here are finite, undirected and simple. First the preliminaries are given. Section 2 contains our main results on the pathwidth of trees, the basis for the algorithm described in section 3.

P. Scheffler

### The Time Travelling Problem

For some practical applications (see [l]) a problem is interesting wich can be illustrated in a not nessesarily physically correct way like follows: Suppose an organization for time travels wants to carry out some trips into the past. There shall be visited the points of time x1,x2,...,xf where x1<x2 <...xf. In order to execute these trips there are time travellers in r stations s1,s2,...,sr (their number is not limited in any station). But only the station can bring a traveller into the past. A traveller in the point xi can jump only, in the forward direction, that means jumping to a point xj is possible only if xi<xj (wich means i<j) or he can return to his station into the present time. Taking a traveller from station sk into point xi there are c0ik energy units nessesary, jumping from xi to xj a traveller needs cij energy units and jumping from xi to sk he needs ci0k units. We want to find a set of time travels such that every point xi is visited exactly one times and such that the amount of energy is as small as possible.

G. Schild

### An Aperiodic Triple of Prototiles

Based on R. M. Robinson’s well-known aperiodic set of six prototiles an aperiodic triple of prototiles is constructed. Further applications of the method are indicated.

P. Schmitt

### Representation of Graphs by Integers

In this paper by graph we always mean a graph without loops and without multiple lines. Such a graph will be conceived as a pair (V,ρ) where V is a set and ρ is an irreflexive symmetric relation on V. The elements of V are the vertices and ρ represents the adjacency. Concerning other basic concepts we will use the common terminology.

R. Schnabel

### Special Systems of Linear Equations and Graphs of Convex Polytopes

Let be $$\bar{A}=({{\bar{a}}_{1}},{{\bar{a}}_{2}},...,{{\bar{a}}_{n}})$$ a Gale transform in the Euclidean space $${{\bar{E}}^{n-d-1}}$$ with dim aff $$\bar{A}=n-1-d,2\le d\le n-1$$ and the following property. For every open halfspace H of $${{\bar{E}}^{n-d-1}}$$ with 0 ∈ bd H the condition 1$$card\{k:\text{ }{{\bar{a}}_{K}}\in \text{ }H\}\ge \text{ }2$$ is valid. We consider the equations 2$$\sum\limits_{k=1}^{n}{{{{\bar{a}}}_{k}}}\text{ }{{\text{x}}_{\text{k}}}\text{ = }\vartheta \text{ }\sum\limits_{k=1}^{n}{{{x}_{k}}}\text{ = 1,}$$ where xk are real variables, which we interpret as coordinates of a rectangular Cartesian coordinate system with the origin 0 in the euclidean space En. The equations (2) are equivalent to the system 3$$[A\text{ x = b}$$ with the (n−d)×n − matrix A which has the form $$A\text{ = (}\begin{matrix} {{{\bar{a}}}_{1}} & {{{\bar{a}}}_{2}} & ... & {{{\bar{a}}}_{3}} \\ 1 & 1 & ... & 1 \\ \end{matrix}\text{) , }\overline{\text{A}}\text{ = (}{{\bar{a}}_{1}}\text{ }{{\bar{a}}_{1}}...{{\bar{a}}_{n}}\text{), }\sum\limits_{k=1}^{n}{{{{\bar{a}}}_{k}}}\text{ = }\vartheta \text{ ,}$$ where $$\bar{A}$$ is a submatrix of A. The vector b∈En−d is given by bT = (0 0...0 1). The rank of A is equal n−d. We denote by X+(A) the set of all non negative solutions of the system (3). We understand under a solution xI∈X+(A) with I⊆N = {1,2,...,n) a n-dimensional vector with the coordinates xkI = 0 for k∈I and xkI>0 for k∈ N\I.

W. Schöne

### On 2-Embeddable Graphs

Let there be a graph without loops G and a closed surface F of the charac-teristic N.1) G is called embeddable in F if G can be represented (drawn) on F in such a way that none of G’s edges is crossing over another edge of G. In more general terms, G is called n-embeddable in F (n ∈ N), if G can be represented on F in such a way that each edge of G crosses a maximum of n other edges of G. On each edge of G, all intersections (points where edges are crossing) are counted; if one edge is crossed i times by another, this will be counted i times, if an edge is crossed by j multiple edges e1,e2,....,ej2) this will be counted j times.

H. Schumacher

### On an Application of the Boolean Differential Calculus to Digital System Theory

Modern microelectronics providing low cost complex digital devices has at least equalized the previously most important task to minimize the expense of devices with other criteria such as dynamic properties, the ability of decomposition,test comfortability and others. With the existence of several criteria enjoying equal rigths the design of switching systems will become a optimization process. The Boolean differential calculus has turned out to be a suitable means for optimization in an analytic way /1/, /2/, /3/, /4/.This paper involves two central points of interest: firstly,reduction of any kind of derivations of Boolean functions to the derivation with exclusive disjunction operation and secondly, application of the differential equation based on this derivation to the analytic description of the stability of binary systems

B. Stiefel

### Equiareal Sets in ℝd

Seidel and Blokhuis investigated in [1,2] the problem of finding an upper bound for the cardinality of the so-called equidistant sets. These are subsets of the unit sphere in ℝd such that the distance between any two of its vectors is always the same.

G. W. Teumer

### On the Piaget Graph

Jean Piaget (1896–1980) is the founder of genetic epistemology and psychology in Geneva. His scientific interest was devoted to the question of the rise and development of human knowledge. His statements on the genesis of knowledge in children are world-renowned. ‘Piaget puts the diversity of the correlations of living thinking into classes and relations’ (Aebli, 1978,608). To explain the cognitive structures of children, Piaget uses the grouping concept, which he describes in both colloquial terms and with mathematical terminology and graph-theoretical methods (Fig. 1).

C. Thies

### On a Characterization of Closure Operators by Identities on Semigroups

For a semigroup S it is well known, that the operator C on the power set P(S) of S, which assigns to every U ∈ P(S) the subsemigroup C(U) of S generated by U, is a closure operator (cf. [2], [4]). Let T ∈ P(S). Then U is called to be a generating set of T with respect to C if and only if U ⫅ T and T ⫅ C(U). Let GEN(T) be the system of all generating sets of T. To give a more detailed description of the generating sets of T the so-called isolated sets of T are considered. I is called to be isolated in T if and only if Ø ≠I ⫅ T and I ∩C(T\I) = Ø. Let ISO(T) be the system of all I such that I is isolated in T. Then there holds

R. Thron, J. Koppitz

### Symmetries of Group-Triangulations

Many authors dealt with groups and graphs. Here we shall assign to a finite group triangulations of some oriented (closed) surfaces in the sense of H. Sachs [1]. This assignment was intensively studied by W. Voss [9] – [14]. A survey on old and new results is given in H.-J. Voss [6]

H.-J. Voss

### Experimental Mathematics — Tesselations of Convex Polygons in a Hexagonal Lattice

The following considerations can be seen in the context of a world wide demand put forward by mathematics educators to give more room in mathematics education to problem solving.

G. Walther

### Domination in Cubic Graphs

In this paper we shall study the domatic number, the total domatic number and the connected domatic number of cubic graphs, i. e. regular graphs of degree 3. We consider finite undirected graphs without loops and multiple edges.

### A Generalization of the Bodendiek Conjecture About Graceful Graphs

R. Bodendiek conjectured that every graph consisting of a cycle plus a chord is graceful, and various proofs have been given.[1]MHere we use GL-matrix as a tool in proving the following generalization:Apart from four exceptional cases,simple graphs consisting of three independent paths joining two vertices are graceful.

C. Zhi-Zeng

### A Sparse Gallai-Witt Theorem

Generalizing a result of the authors (Trans. Am. Math. Soc. 309,113–137, 1988) and simplifying the proof thereof a sparse Gallai-Witt theorem is proved.

H.-J. Prömel, B. Voigt

### Edges with at Most One Crossing in Drawings of the Complete Graph

In 1963 G. Ringel ([3]) determined 2n−2 to be the maximum number of edges without crossings in drawings D(Kn) of the complete graph Kn in the plane. A drawing D(G) is a realization of G in the plane with distinct points (also called vertices) for the vertices of G, and curves (also called edges) for the edges of G such that two edges have at most one point in common, either an endpoint or a crossing. As generalizations it may be asked for the maximum numbers Hs(n) or the minimum num-bers hs(n) of edges with at most s crossings in drawings D(Kn). In [1] h0(n) is determined, and hs(n)=0 for n≧4s+8 holds in general ([2]). Here we will give an alternative proof of Ringel’s result, H0(n)=2n−2, and estimations of H1(n).

H. Harborth, I. Mengersen

### Long Cycles in Graphs with Moderate Connectivity

In this paper we supply bounds for the length of a longest cycle C in G in terms of the structure of G-V(C).

H. A. Jung

### Independent Covers in Plane Graphs

A subset W of vertices of a plane graph G is said to be a face-independent vertex cover (FIVC) if each face-boundary contains exactly one vertex of W. A FIVC naturally corresponds to a vertex-independent face cover (VIFC) in the dual graph G* of G. In this paper we review the results on the existence of such covers in arbitrary planar graphs and in outerplanar graphs, in particular.

M. M. Syslo

### Backmatter

Weitere Informationen