This volume in the Annals of Discrete Mathematics brings together contributions by renowned researchers in combinatorics, graphs and complexity. The conference on which this book is based was the fourth in a series which began in 1963, which was the first time specialists from East and West were able to come together. The 1990 meeting attracted 170 mathematicians and computer scientists from around the world, so this book represents an international, detailed view of recent research.
Author(s): Jaroslav Neŝetril and Miroslav Fiedler (Eds.)
Series: Annals of Discrete Mathematics 51
Publisher: North-Holland
Year: 1992
Language: English
Pages: ii-v, 1-400
Content:
General Editor
Page ii
Edited by
Page iii
Copyright page
Page iv
Preface
Page v
M. Fiedler, J. Neŝetril
Two Sequences of 2–Regular Graceful Graphs Consisting of 4–gons Original Research Article
Pages 1-4
Jaromir Abram, Aanton Kotzig
A Survey of Self-Dual Polyhedra Original Research Article
Pages 5-12
Dan Archdeacon
On Magic Labellings of Convex Polytopes Original Research Article
Pages 13-16
Martin Baĉa
A Packing Problem and Geometrical Series Original Research Article
Pages 17-21
Vojtech Bálint
On the Bananas Surface B2 Original Research Article
Pages 23-30
R. Bodendiek, K. Wagner
Structural Properties and Colorings of Plane Graphs Original Research Article
Pages 31-37
Oleg V. Borodin
The Binding Number of Graphs Original Research Article
Pages 39-44
Mieczyslaw Borowiecki
Note on Algorithmic Solvability of Trahtenbrot-Zykov Problem Original Research Article
Pages 45-49
Peter Bugata
Cartesian Dimensions of a Graph Original Research Article
Pages 51-57
Gustav Burosch, Pier Vittorio Ceccherini
The Steiner Minimal Tree Problem in L2p Original Research Article
Pages 59-62
Dietmar Cieslik
On k-Connected Subgraphs of the Hypercube Original Research Article
Pages 63-67
Tomáŝar; Dvorák
On Some of my Favourite Problems in Various Branches of Combinatorics Original Research Article
Pages 69-79
P. Erdös
Readability of Some Stariike Trees Original Research Article
Pages 81-83
D. Fronĉek
The Construction of all Configurations (124,163) Original Research Article
Pages 85-91
Harald Gropp
(p, q)-realizability of Integer Sequences with Respect to Möbius Strip Original Research Article
Pages 93-101
Mirko Hornák
Vertex Location Problems Original Research Article
Pages 103-105
Oto Hudec
On Generation of a Class of Flowgraphs Original Research Article
Pages 107-112
A.J.C. Hurkens, C.A.J. Hurkens, R.W. Whitty
The Weight of a Graph Original Research Article
Pages 113-116
Jaroslav Ivanĉo
On the Kauffman Polynomial of Planar Matroids Original Research Article
Pages 117-127
François Jaeger
On Symmetry Groups of Selfdual Convex Polyhedra Original Research Article
Pages 129-135
Stanislav Jendrol'
A Remark on 2-(u,k, λ) Designs Original Research Article
Pages 137-139
Vêaroslav Jurák
On a New Class of Intersection Graphs Original Research Article
Pages 141-143
Manfred Koebe
Asymptotic Normality of Isolated Edges in Random Subgraphs of the n-Cube Original Research Article
Pages 145-149
Urszula Konieczna
On Bounds of the Bisection Width of Cubic Graphs Original Research Article
Pages 151-154
A.V. Kostochka, L.S. Mel'nikov
On Random Cubical Graphs Original Research Article
Pages 155-160
A.V. Kostochka, A.A. Sapozhenko, K. Weber
On the Computational Complexity of Seidel's Switching Original Research Article
Pages 161-166
Jan Kratochvíl, Jaroslav Neŝetril, Ondrej Zýka
The Harmonious Chromatic Number of a Graph Original Research Article
Pages 167-170
Anton Kundrík
Arboricity and Star Arboricity of Graphs Original Research Article
Pages 171-173
Andrzej Kurek
Extended 4-Profiles of Hadamard Matrices Original Research Article
Pages 175-180
Cantian Lin, W.D. Wallis, Zhu Lie
Good Family Packing Original Research Article
Pages 181-186
M. Loebl, S. Poljak
Solution of an Extremal Problem Concerning Edge-Partitions of Graphs Original Research Article
Pages 187-190
Zbigniew Lonc
Balanced Extensions of Spare Graphs Original Research Article
Pages 191-203
Tomasz Luczak, Andrzej Ruciński
Two Results on Antisocial Families of Balls Original Research Article
Pages 205-207
A. Malniĉ, B. Mohar
Hamiltonicity of Vertex-Transitive pq-Graphs Original Research Article
Pages 209-212
Dragan Maruŝiĉ
On Nodes of Given Out-Degree in Random Trees Original Research Article
Pages 213-222
A. Meir, J.W. Moon
All Leaves and Excesses Are Realizable for k = 3 and all λ Original Research Article
Pages 223-228
Eric Mendelsohn, Nabil Shalaby, Shen Hao
The Binding Number of k-Trees Original Research Article
Pages 229-233
Danuta Michalak
An Extension of Brook's Theorem Original Research Article
Pages 235-236
Peter Mihók
On Sectors in a Connected Graph Original Research Article
Pages 237-240
Ladislav Nebeský
Irreconstructability of Finite Undirected Graphs from Large Subgraphs Original Research Article
Pages 241-244
Václav Nýdl
On Inefficient Proofs of Existence and Complexity Classes Original Research Article
Pages 245-250
Christos H. Papadimitriou
Optimal Coteries on a Network Original Research Article
Pages 251-253
Christos H. Papadimitriou, Martha Sideri
On Some Heuristics for the Steiner Problem in Graphs Original Research Article
Pages 255-257
Ján Plesník
Cycle Covers of Graphs with a Nowhere-Zero 4-Flow (Abstract) Original Research Article
Page 259
André Raspaud
Minimax Results and Polynomial Algorithms in VLSI Routing Original Research Article
Pages 261-273
András Recski
Critical Perfect Systems of Difference Sets Original Research Article
Pages 275-279
D.G. Rogers
Some Operations (Not) Preserving the Integer Rounding Property Original Research Article
Pages 281-285
Anna Rycerz
Optimal Embedding of a Tree into an Interval Graph in Linear Time Original Research Article
Pages 287-291
Petra Scheffler
Construction of Polytopal Graphs Original Research Article
Pages 293-296
W. Schöne
More About Two-Graphs Original Research Article
Pages 297-307
J.J. Seidel
These are the Two-free Trees Original Research Article
Pages 309-313
J. Sheehan, C.R.J. Clapham
A Note on Reconstructing the Characteristic Polynomial of a Graph Original Research Article
Pages 315-319
Slobodan K. Simić
Exponential Constructions of some Nonhamiltonian Minima Original Research Article
Pages 321-328
Z. Skupień
Hamiltonicity of Products of Hypergraphs Original Research Article
Pages 329-332
Martin Sonntag
Non-Hamiltonian Simple 3-Polytopal Graphs with Edges of Only Two Types Original Research Article
Pages 333-335
Michal Tkáĉ
On Spectra of Trees and Related Two-Graphs Original Research Article
Pages 337-340
S.V. Tsaranov
Metrically Regular Square of Metrically Regular Bigraphs Original Research Article
Pages 341-344
Vladimír Vetchý
Embedding of Graphs in the Complements of Their Squares Original Research Article
Pages 345-349
Mariusz Woźniak
An 11/6-Approximation Algorithm for the Steiner Problem on Graphs Original Research Article
Pages 351-354
A.Z. Zelikovsky
Distances Between Graphs (Extended Abstract) Original Research Article
Pages 355-361
Bohdan Zelinka
Domatic Number of a Graph and its Variants (Extended Abstract) Original Research Article
Pages 363-369
Bohdan Zelinka
The Space of Graphs and its Factorizations Original Research Article
Pages 371-374
Alexander A. Zykov
Problems Proposed at the Problem Session of the Prachatice Conference on Graph Theory Original Research Article
Pages 375-384
List of Participants
Pages 385-388
Name Index
Pages 389-395
Subject Index
Pages 397-400
