Topics in Combinatorics and Graph Theory: Essays in Honour of Gerhard Ringel

Front Matter....Pages I-XIX
On the Problem of Relative Components of Minimal Graphs....Pages 1-27
Irregular Assignments and Two Problems à la Ringel....Pages 29-36
A Recursive Bound for the Number of Complete K-Subgraphs of a Graph....Pages 37-39
One-Factorizations of Tensor Products of Graphs....Pages 41-46
Non-Commutative Geometry and Graphs....Pages 47-57
The Complexity of the Graph Embedding Problem....Pages 59-64
Helly Theorems for Dismantlable Graphs and Pseudo-Modular Graphs....Pages 65-71
On the Level-Oriented Two-Dimensional Packing With Rotation of the Rectangles....Pages 73-78
On Planar Tilings With Finitely Many Sorts of Tiles....Pages 79-85
Examples of Space-Tiling Polyhedra Related to Hilbert’s Problem 18, Question 2....Pages 87-92
The Historical Background to Gerhard Ringel’s Work....Pages 93-99
Around Three Lemmas in Hamiltonian Graph Theory....Pages 101-110
A Note on Metric Properties of Infinite Graphs....Pages 111-115
Automorphism Groups of Directed Cayley Graphs....Pages 117-128
Triangular Embeddings of Tensor Products of Graphs....Pages 129-135
Computing Light Edges in Planar Graphs....Pages 137-144
On the Domination Problem for Bipartite Graphs....Pages 145-152
Polyhedral Maps with Few Edges....Pages 153-162
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....Pages 163-174
Status of Graceful Tree Conjecture in 1989....Pages 175-184
Embedded Graphs, Facial Colorings, and Double Cycle Covers....Pages 185-192
On Peripheral Vertices in Graphs....Pages 193-199
The Vertex-Degrees of Steiner Minimal Trees in Minkowski Planes....Pages 201-206
Unfolding Weighted Consensus Orders into Consistent Numerical Scales....Pages 207-217
Forbidden Ordered Subgraphs....Pages 219-229
On Normal Tournaments with the Least Number of 3-Cycles....Pages 231-237
Two-Irregular Graphs....Pages 239-248
Cell Complexes and Lower Bounds in Computational Geometry....Pages 249-256
Characterizing Directed Postman Tours....Pages 257-262
Some Properties of ”Almost All” Functions From $$_{{{p}_{k}}}$$ ....Pages 263-269
Composition of Facets of the Clique Partitioning Polytope....Pages 271-284
Optimal Edge-Numbering of Binary Trees....Pages 285-289
On Independent Vertices and Edges of a Graph....Pages 291-296
The Outerthickness & Outercoarseness of Graphs I. The Complete Graph & The n -Cube....Pages 297-310
On Some Graphic Aspects of Addition Theorems....Pages 311-318
On the Circumference of Regular Polyhedral Graphs....Pages 319-330
Longest Cycles in Circulant Graphs....Pages 331-338
Spanning Trees of the Complete Bipartite Graph....Pages 339-346
A Combinatorial Theorem Which is Related to the Invariance of the Separating Set for the Plane....Pages 347-352
On Certain Trees in Hypercubes....Pages 353-358
Extending Hall’s Theorem....Pages 359-371
On the Coupling Condition and Hamiltonicity....Pages 373-380
Transversals and Matroids....Pages 381-389
Classification and Construction of Geodetic Block with Diameter Two....Pages 391-395
Graph Distances and Similarity....Pages 397-404
Witt Rings and Semiorderings of Planar Ternary Rings....Pages 405-411
Linear Inequalities Describing the Class of Intersecting Sperner Families of Subsets, I....Pages 413-420
Integral Drawings of the Complete Graph K 6 ....Pages 421-429
On Certain Binomial Sums....Pages 431-434
Colouring of Spider Graphs....Pages 435-441
A Las-Vergnas Type Theorem for Trees....Pages 443-449
Quick Gossiping by Multi-Telegraphs....Pages 451-458
Numberings on Graphs Having Small Edge Weights....Pages 459-469
On Vertexminimal Graphs with Radius r and Connectivity 2m....Pages 471-477
Embedding Schemes and the Jordan Curve Theorem....Pages 479-489
Subgraph Packing — A Survey....Pages 491-503
On the Radius of Random Subgraphs of the n-Cube....Pages 505-511
A Result in Combinatorial Matroid Theory....Pages 513-517
On Graphs Embeddable with Short Faces....Pages 519-529
On Cyclic Representations of Triples by Pairs....Pages 531-540
On the Steiner Periphery and Steiner Eccentricity of a Graph....Pages 541-547
Cycles Containing Three Consecutive Edges in 2k-Edge-Connected Graphs....Pages 549-553
Graph Distance and Euclidean Distance on the Grid....Pages 555-559
About the Complexity of Some Homomorphism Problems on Graphs....Pages 561-567
On an Inequality of Sperner....Pages 569-576
Counting Perfect Matchings in Lattice Graphs....Pages 577-584
Genus — Minimal Edges and Kuratowski Subgraphs of a Graph....Pages 585-593
From Tree Path-Factors and Doubly Exponential Sequences to a Binomial Inequality....Pages 595-603
A Characterization of Point-Colour-Symmetric Hypergraphs....Pages 605-612
A Linear Algorithm for the Pathwidth of Trees....Pages 613-620
The Time Travelling Problem....Pages 621-626
An Aperiodic Triple of Prototiles....Pages 627-633
Representation of Graphs by Integers....Pages 635-640
Special Systems of Linear Equations and Graphs of Convex Polytopes....Pages 641-650
On 2-Embeddable Graphs....Pages 651-661
On an Application of the Boolean Differential Calculus to Digital System Theory....Pages 663-670
Equiareal Sets in ℝ d ....Pages 671-677
On the Piaget Graph....Pages 679-683
On a Characterization of Closure Operators by Identities on Semigroups....Pages 685-692
Symmetries of Group-Triangulations....Pages 693-711
Experimental Mathematics — Tesselations of Convex Polygons in a Hexagonal Lattice....Pages 713-725
Domination in Cubic Graphs....Pages 727-735
A Generalization of the Bodendiek Conjecture About Graceful Graphs....Pages 737-746
A Sparse Gallai-Witt Theorem....Pages 747-755
Edges with at Most One Crossing in Drawings of the Complete Graph....Pages 757-763
Long Cycles in Graphs with Moderate Connectivity....Pages 765-778
Independent Covers in Plane Graphs....Pages 779-785
Back Matter....Pages 786-792