Irregularity in Graphs (SpringerBriefs in Mathematics)

Die Theorie der regularen Graphen (The Theory of Regular Graphs), written by the Danish Mathematician Julius Petersen in 1891, is often considered the first strictly theoretical paper dealing with graphs. In the 130 years since then, regular graphs have been a common and popular area of study. While regular graphs are typically considered to be graphs whose vertices all have the same degree, a more general interpretation is that of graphs possessing some common characteristic throughout their structure. During the past several decades, however, there has been some increased interest in investigating graphs possessing a property that is, in a sense, opposite to regularity. It is this topic with which this book deals, giving rise to a study of what might be called irregularity in graphs. Here, various irregularity concepts dealing with several topics in graph theory are described, such as degrees of vertices, graph labelings, weightings, colorings, graph structures, Eulerian and Hamiltonian properties, graph decompositions, and Ramsey-type problems. Preface Contents 1 Introduction 1.1 Prologue 1.2 Degrees and Degree Sets 1.3 Regular and Irregular Graphs 1.4 Antiregular Graphs References 2 Locally Irregular Graphs 2.1 Highly Irregular Graphs 2.2 Link-Regular Graphs 2.3 Link-Irregular Graphs References 3 F-Irregular Graphs 3.1 F-Degrees 3.2 F-Irregularity 3.3 Variations of F-Degrees References 4 Irregularity Strength 4.1 Multigraphs and Weighted Graphs 4.2 Irregular Weightings 4.3 Bounds 4.4 Regular Weightings References 5 Rainbow Mean Index 5.1 Rainbow Mean Colorings 5.2 Complete Graphs and Complete Bipartite Graphs 5.3 Bipartite Graphs References 6 Royal Colorings 6.1 The Majestic Index of a Graph 6.2 The Royal Index of a Graph References 7 Traversable Irregularity 7.1 Introduction 7.2 The Chinese Postman Problem 7.3 Irregular Eulerian Walks 7.4 Optimal Irregular Eulerian Walks 7.5 Irregular Hamiltonian Walks References 8 Ascending Subgraph Decompositions 8.1 Isomorphic Decompositions 8.2 Irregular Decompositions 8.3 The Ascending Subgraph Decomposition Conjecture 8.4 Decomposition Digraphs 8.5 Monochromatic Ascending Subgraph Sequences References Index