Graph Theory and Applications (eBook)

Front Cover 1
Proceedings of the First Japan Conference on Graph Theory and Applocations 4
Copyright Page 5
Contents 6
Preface 8
Chapter 1. Highly irregular m-chromatic graphs 10
Chapter 2. Explicit construction of linear sized tolerant networks 22
Chapter 3. Sorting in rounds 28
Chapter 4. On edge-Hamiltonian property of Cayley graphs 36
Chapter 5. Gallai theorems for graphs, hypergraphs, and set systems 42
Chapter 6. Edge-packings of graphs and network reliability 56
Chapter 7. Two Hamilton cycles in bipartite reflective Kneser graphs 70
Chapter 8. A result on generalized Latin rectangles 78
Chapter 9. Problems and results in combinatorial analysis and graph theory 88
Chapter 10. Clique partitions and clique coverings 100
Chapter 11. Extremal theory and bipartite graph-tree Ramsey numbers 110
Chapter 12. On conjectures of Graffiti 120
Chapter 13. Small order graph-tree Ramsey numbers 126
Chapter 14. Enumerating phylogenetic trees with multiple labels 136
Chapter 15. Triad count statistics 148
Chapter 16. Score sequences: lexicographic enumeration and tournament construction 158
Chapter 17. Problems on chain partitions 164
Chapter 18. A solution to the Misere Shannon switching game 170
Chapter 19. A graph-theoretical characterization of the order complexes on the 2-sphere 174
Chapter 20. Hard graphs for the maximum clique problem 182
Chapter 21. Doubly regular asymmetric digraphs 188
Chapter 22. Ordering of the elements of a matroid such that its consecutive w elements are independent 194
Chapter 23. An existential problem of a weight-controlled subset and its application to school timetable construction 202
Chapter 24. More non-reconstructible hypergraphs 220
Chapter 25. Constructions of sensitive graphs which are not strongly sensitive 232
Chapter 26. Combinatorial resolution of systems of differential equations. IV. Separation of variables 244
Chapter 27. Labeling angles of planar graphs 258
Chapter 28. Maximal induced trees in sparse random graphs 264
Chapter 29. Generalizations of critical connectivity of graphs 274
Chapter 30. On the Euclidean dimension of a complete multipartite graph 292
Chapter 31. Computation of some Cayley diagrams 298
Chapter 32. Short cycles in digraphs 302
Chapter 33. Subgraph counts in random graphs using incomplete U-statistics methods 306
Chapter 34. Toughness and matching extension in graphs 318
Chapter 35. Bipartite graphs obtained from adjacency matrices or orientations of graphs 328
Chapter 36. Cn-factors of group graphs 338
Chapter 37. An algorithm for solving the jump number problem 344
Chapter 38. Large scale network analysis with applications to transportation, communication and inference networks 354
Chapter 39. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three 362
Chapter 40. p3-factorization of complete bipartite graphs 368
Chapter 41. n-graphs 374
Chapter 42. On point-linear arboricity of planar graphs 388
Chapter 43. On the Littlewood–Richardson rule in terms of lattice path combinatorics 392
Chapter 44. Chromatic polynomials of generalized trees 398
Chapter 45. Packing of graphs – A survey 402
Chapter 46. z-transformation graphs of perfect matchings of hexagonal systems 412
Author Index 424