Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (eBook)

Front Cover 1
Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity 4
Copyright Page 5
Contents 8
Preface 6
Chapter 1. Two Sequences of 2-Regular Graceful Graphs Consisting of 4-gons 12
Chapter 2. A Survey of Self-Dual Polyhedra 16
Chapter 3. On Magic Labellings of Convex Polytopes 24
Chapter 4. A Packing Problem and Geometrical Series 28
Chapter 5. On the Bananas Surface B2 34
Chapter 6. Structural Properties and Colorings of Plane Graphs 42
Chapter 7. The Binding Number of Graphs 50
Chapter 8. Note on Algorithmic Solvability of Trahtenbrot-Zykov Problem 56
Chapter 9. Cartesian Dimensions of a Graph 62
Chapter 10. The Steiner Minimal Tree Problem in L2p 70
Chapter 11. On k-Connected Subgraphs of the Hypercube 74
Chapter 12. On Some of My Favourite Problems in Various Branches of Combinatorics 80
Chapter 13. Realizability of Some Starlike Trees 92
Chapter 14. The Construction of All Configurations (124,163) 96
Chapter 15. (p, q)-realizability of Integer Sequences with Respect to Möbius Strip 104
Chapter 16. Vertex Location Problems 114
Chapter 17. On Generation of a Class of Flowgraphs 118
Chapter 18. The Weight of a Graph 124
Chapter 19. On the Kauffman Polynomial of Planar Matroids 128
Chapter 20. On Symmetry Groups of Selfdual Convex Polyhedra 140
Chapter 21. A Remark on 2-(v,k,A) Designs 148
Chapter 22. On a New Class of Intersection Graphs 152
Chapter 23. Asymptotic Normality of Isolated Edges in Random Subgraphs of the n-Cube 156
Chapter 24. On Bounds of the Bisection Width of Cubic Graphs 162
Chapter 25. On Random Cubical Graphs 166
Chapter 26. On the Computational Complexity of Seidel’s Switching 172
Chapter 27. The Harmonious Chromatic Number of a Graph 178
Chapter 28. Arboricity and Star Arboricity of Graphs 182
Chapter 29. Extended 4-Profiles of Hadamard Matrices 186
Chapter 30. Good Family Packing 192
Chapter 31. Solution of an Extremal Problem Concerning Edge-Partitions of Graphs 198
Chapter 32. Balanced Extensions of Spare Graphs 202
Chapter 33. Two Results on Antisocial Families of Balls 216
Chapter 34. Hamiltonicity of Vertex-transitive pq-Graphs 220
Chapter 35. On Nodes of Given Out-Degree in Random Trees 224
Chapter 36. All Leaves and Excesses Are Realizable for k = 3 and All A 234
Chapter 37. The Binding Number of k-Trees 240
Chapter 38. An Extension of Brook’s Theorem 246
Chapter 39. On Sectors in a Connected Graph 248
Chapter 40. lrreconstructability of Finite Undirected Graphs from Large Subgraphs 252
Chapter 41. On Inefficient Proofs of Existence and Complexity Classes 256
Chapter 42. Optimal Coteries on a Network 262
Chapter 43. On Some Heuristics for the Steiner Problem in Graphs 266
Chapter 44. Cycle Covers of Graphs with a Nowhere-Zero 4-Flow (Abstract) 270
Chapter 45. Minimax Results and Polynomial Algorithms in VLSl Routing 272
Chapter 46. Critical Perfect Systems of Difference Sets 286
Chapter 47. Some Operations (Not) Preserving the Integer Rounding Property 292
Chapter 48. Optimal Embedding of a Tree into an Interval Graph in Linear Time 298
Chapter 49. Construction of Polytopal Graphs 304
Chapter 50. More About Two-Graphs 308
Chapter 51. These are the Two-free Trees 320
Chapter 52. A Note on Reconstructing the Characteristic Polynomial of a Graph 326
Chapter 53. Exponential Constructions of Some Nonhamiltonian Minima 332
Chapter 54. Hamiltonicity of Products of Hypergraphs 340
Chapter 55. Non-Hamiltonian Simple 3-Polytopal Graphs with Edges of Only Two Types 344
Chapter 56. On Spectra of Trees and Related Two-Graphs 348
Chapter 57. Metrically Regular Square of Metrically Regular Bigraphs 352
Chapter 58. Embedding of Graphs in the Complements of Their Squares 356
Chapter 59. An 11/6-Approximation Algorithm for the Steiner Problem on Graphs 362
Chapter 60. Distances Between Graphs (Extended Abstract) 366
Chapter 61. Domatic Number of a Graph and its Variants (Extended Abstract) 374
Chapter 62. The Space of Graphs and its Factorizations 382
Chapter 63. Problems Proposed at the Problem Session of the Prachatice Conference on Graph Theory 386
List of Participants 396
Name Index 400
Subject Index 408