اصلی
Algebraic Graph Theory: Morphisms, Monoids and Matrices (De Gruyter Studies in Mathematics)
Algebraic Graph Theory: Morphisms, Monoids and Matrices (De Gruyter Studies in Mathematics)
Ulrich Knauer
0 /
0
دا کتاب تاسو ته څنګه خواښه شوه؟
د بار شوي فایل کیفیت څه دئ؟
تر څو چې د کتاب کیفیت آزمایښو وکړئ، بار ئې کړئ
د بار شوو فایلونو کیفیتی څه دئ؟
Graph models are extremely useful for a large number of applications as they play an important role as structuring tools. They allow to model net structures like roads, computers, telephones, social networks instances of abstract data structures like lists, stacks, trees and functional or object oriented programming. The focus of this highly selfcontained book is on homomorphisms and endomorphisms, matrices and eigenvalues.
درجه (قاطیغوری(:
کال:
2019
خپرونه:
2nd Rev. and Ext. ed.
خپرندویه اداره:
de Gruyter
ژبه:
english
صفحه:
349 / 352
ISBN 10:
3110616122
ISBN 13:
9783110616125
لړ (سلسله):
De Gruyter Studies in Mathematics (Book 41)
فایل:
PDF, 2.44 MB
ستاسی تیګی:
کاپی کول (pdf, 2.44 MB)
 په براوزیر کې خلاص شی
 Checking other formats...
 EPUB کاپی شی
 FB2 کاپی شی
 MOBI کاپی شی
 TXT کاپی شی
 RTF کاپی شی
 د اصلی او کاپی شوی فایل فرق کیږی، د امکان په صورت کې بهتره ده په اصل بڼه کاپی شی.
د پروبلم په اړوند خبر ورکول
This book has a different problem? Report it to us
Check Yes if
Check Yes if
Check Yes if
Check Yes if
you were able to open the file
the file contains a book (comics are also acceptable)
the content of the book is acceptable
Title, Author and Language of the file match the book description. Ignore other fields as they are secondary!
Check No if
Check No if
Check No if
Check No if
 the file is damaged
 the file is DRM protected
 the file is not a book (e.g. executable, xls, html, xml)
 the file is an article
 the file is a book excerpt
 the file is a magazine
 the file is a test blank
 the file is a spam
you believe the content of the book is unacceptable and should be blocked
Title, Author or Language of the file do not match the book description. Ignore other fields.
Are you sure the file is of bad quality? Report about it
Change your answer
Thanks for your participation!
Together we will make our library even better
Together we will make our library even better
د ۱ ۵ دقیقو په جریان کې فایل ستاسی ایمل ته دررسیږی.
د ۱ ۵ دقیقو په جریان کې فایل ستاسی کیندل ته دررسیږی.
ملاحظه هر کتاب چي تاسي Kindle ته ليږئ باید تصدیق شی. خپله الکترونیکی پوسته تفتیش کړئ چې پکښې باید د Amazon Kindle Support له خوا مکتوب وی.
ملاحظه هر کتاب چي تاسي Kindle ته ليږئ باید تصدیق شی. خپله الکترونیکی پوسته تفتیش کړئ چې پکښې باید د Amazon Kindle Support له خوا مکتوب وی.
Conversion to is in progress
Conversion to is failed
ممکن تاسی علاقمند شی Powered by Rec2Me
مهمي جملي
graph^{1048}
graphs^{958}
cay^{636}
theorem^{485}
vertex^{408}
aut^{354}
authenticated download^{332}
university library^{332}
stockholm university^{332}
library authenticated^{332}
download date^{332}
groups^{300}
proof^{290}
cayley^{266}
example^{265}
vertices^{261}
definition^{249}
product^{246}
semigroups^{232}
lemma^{230}
planar^{226}
send^{226}
transitive^{207}
edges^{202}
edge^{190}
matrix^{181}
theory^{176}
cayley graphs^{167}
semigroup^{160}
category^{159}
vertex transitive^{154}
regular^{147}
thus^{142}
connected^{139}
exists^{138}
elements^{133}
products^{133}
path^{129}
undirected^{127}
sets^{125}
directed^{122}
genus^{121}
monoids^{119}
implies^{118}
homomorphism^{118}
monoid^{117}
remark^{116}
graph theory^{110}
element^{106}
corollary^{104}
homomorphisms^{103}
endomorphism^{102}
mapping^{100}
generating^{98}
finite^{94}
cycle^{93}
diagram^{91}
د کتابونو مرتبط لیسټونه
0 comments
تاسی کولی شی د کتاب په اړوند نظر څرګند کړی او خپله تجربه زمونږ سره شریکه کړی، نورو لوستونکو ته به زړه راښکونکی (دلچسپه) وی چې د لوستل شوو کتابونو په اړوند ستاسی په نظر پوه شی. بدون له دی چې کتاب مو خوښ شو اویا خوش نه شو، که تاسی صادقانه په دی اړوند مفصله قصه وکړی، خلک کولی شی د ځان لپاره نوی کتابونه بیدا کړی، چې هغوی ته زړه راښکونکی (دلچسپه) دی.
1

2

Ulrich Knauer and Kolja Knauer Algebraic Graph Theory De Gruyter Studies in Mathematics  Edited by Carsten Carstensen, Berlin, Germany Gavril Farkas, Berlin, Germany Nicola Fusco, Napoli, Italy Fritz Gesztesy, Waco, Texas, USA Niels Jacob, Swansea, United Kingdom Zenghu Li, Beijing, China KarlHermann Neeb, Erlangen, Germany Volume 41 Ulrich Knauer and Kolja Knauer Algebraic Graph Theory  Morphisms, Monoids and Matrices 2nd edition Mathematics Subject Classification 2010 05C05, 05C10, 05C12, 05C20, 05C25, 05C12, 05C38, 05C50, 05C62, 05C75, 05C90, 20M17, 20M19, 20M20, 20M30, 18B10, 18B40 Authors Prof. Dr. Dr. h.c. Ulrich Knauer Carl von Ossietzky Universität Institut für Mathematik Ammerländer Heerstr. 114–118 26129 Oldenburg Germany ulrich.knauer@unioldenburg.de Dr. Kolja Knauer Université AixMarseille Laboratoire d’Informatique et des Systèmes, LIS UMR 7020 163 avenue de Luminy 13288 Marseille Cedex 9 France kolja.knauer@lislab.fr ISBN 9783110616125 eISBN (PDF) 9783110617368 eISBN (EPUB) 9783110616286 ISSN 01790986 Library of Congress Control Number: 2019946001 Bibliographic information published by the Deutsche Nationalbibliothek The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data are available on the Internet at http://dnb.dnb.de. © 2019 Walter de Gruyter GmbH, Berlin/Boston Typesetting: VTeX UAB, Lithuania Printing and binding: CPI books GmbH, Leck www.degruyter.com Preface This book is a collection of the lectures I have given on algebraic graph theory. These lectures were designed for mathematics students in a Master’s program, but they may also be of interest to undergraduates in the final year of a Bachelor’s curriculum. The lectures cover topics which can be used as starting points for a Master’s or Bachelor’s thesis. Some questions raised in the text could even be suitable as subjects of doctoral dissertations. The advantage afforded by the field of algebraic graph theory is that it allows man; y questions to be understood from a general mathematical background and tackled almost immediately. In fact, my lectures have also been attended by graduate students in informatics with a minor in mathematics. In computer science and informatics, many of the concepts associated with graphs play an important role as structuring tools—they enable us to model a wide variety of different systems, such as the structure of physical networks (of roads, computers, telephones, etc.) as well as abstract data structures (e. g., lists, stacks, trees); functional and object oriented programming are also based on graphs as a means of describing discrete entities. In addition, category theory is gaining more and more importance in informatics; therefore, these lectures also include a basic and concrete introduction to categories, with numerous examples and applications. I gave the lectures first at the University of Bielefeld and then, in various incarnations, at the Carl von Ossietzky Universität Oldenburg. They were sometimes presented in English and in several other countries, including Thailand and New Zealand. Selection of topics The choice of topics is in part standard, but it also reflects my personal preferences. Many students seem to have found the chosen topics engaging, as well as helpful and useful in getting started on thesis research at various levels. To mark the possibilities for further research, I have inserted many “Questions,” as well as “Exercises” that lead to illuminating examples. Theorems for which I do not give proofs are sometimes titled “Exerceorem,” to stress their role in the development of the subject. I have also inserted some “Projects,” which are designed as exercises to guide the reader in beginning their own research on the topic. I have not, however, lost any sleep over whether to call each result a theorem, proposition, exerceorem, or something else, so readers should neither deduce too much from the title given to a result nor be unduly disturbed by any inconsistencies they may discover—this beautiful English sentence I have adopted from the introduction of John Howie’s An Introduction to Semigroup Theory, published by Academic Press in 1976. https://doi.org/10.1515/9783110617368201 VI  Preface Homomorphisms, especially endomorphisms, form a common thread throughout the book; you will meet this concept in almost all the chapters. Another focal point is the standard part of algebraic graph theory dealing with matrices and eigenvalues. In some parts of the book, the presentation will be rather formal; my experience is that this can be very helpful to students in a field where concepts are often presented in an informal verbal manner and with varying terminology. Content of the chapters We begin, in Chapter 1, with basic definitions, concepts, and results. This chapter is very important, as standard terminology is far from being established in graph theory. One reason for this is that graph models are so extremely useful in a great number of applications in diverse fields. Many of the modelers are not mathematicians and have developed their own terminology and results, without necessarily caring much about existing theory. Chapter 1 contains some new variants of results on graph homomorphisms and the relations among them, connecting them, in turn, to the combinatorial structure of the graph. Chapter 2 makes connections to linear algebra by discussing the different matrices associated to graphs. We then proceed to the characteristic polynomial and eigenvalues, topics that will be encountered again in Chapters 5 and 8. There is no intention to be complete, and the content of this chapter is presented at a relatively elementary level. In Chapter 3, we introduce some basic concepts from category theory, focusing on what will be helpful for a better understanding of graph concepts. In Chapter 4, we look at graphs and their homomorphisms, in particular binary operations such as unions, amalgams, products, and tensor products; for the latter two operations I use the illustrative names cross product and box product. It turns out that, except for the lexicographic products and the corona, all of these operations have a categorytheoretical meaning. Moreover, adjointness leads to socalled Mor constructions; some of the ones presented in this chapter are new, as far as I know, and I call them diamond and power products. In Chapter 5, we focus on unary operations such as the total graph, the tree graph and, principally, line graphs. Line graphs are dealt with in some detail; in particular, their spectra are discussed. Possible functorial properties are left for further investigation. In Chapter 6, the fruitful notion of duality, known from and used in linear algebra, is illustrated with the socalled cycle and cocycle spaces. We then apply the concepts to derive Kirchhoff’s laws and to “square the rectangle.” The chapter finishes with a short survey of applications to transportation networks. Chapter 7 discusses several connections between graphs and groups and, more generally, semigroups or monoids. We start with Cayley graphs and Fruchttype re Selection of topics  VII sults, which are also generalized to monoids. We give results relating the groups to combinatorial properties of the graph as well as to algebraic aspects of the graph. In Chapter 8, we continue the investigation of eigenvalues and the characteristic polynomial begun in Chapters 2 and 5. Here, we present more of the standard results. Many of the proofs in this chapter are omitted, and sometimes we mention only the idea of the proof. In Chapter 9, we present some results on endomorphism monoids of graphs. We study von Neumann regularity of endomorphisms of bipartite graphs, locally strong endomorphisms of paths, and strong monoids of arbitrary graphs. The chapter includes a fairly complete analysis of the strong monoid, with the help of lexicographic products on the graph side and wreath products on the monoid side. In Chapter 10, we discuss unretractivities, i. e., under what conditions on the graph do its different endomorphism sets coincide? We also investigate questions such as how the monoids of composed graphs (e. g., product graphs) relate to algebraic compositions (e. g., products) of the monoids of the components. This type of question can be interpreted as follows: when is the formation of the monoid productpreserving? In Chapter 11, we come back to the formation of Cayley graphs of a group or semigroup. This procedure can be considered as a functor. As a side line, we investigate (in Section 11.2) preservation and reflection properties of the Cayley functor. This is applied to Cayley graphs of right and left groups and is used to characterize Cayley graphs of certain completely regular semigroups and strong semilattices of semigroups. In Chapter 12, we resume the investigation of transitivity questions from Chapter 8 for Cayley graphs of strong semilattices of semigroups, which may be groups or right or left groups. We start with Aut and ColAutvertex transitivities and finish with endomorphism vertex transitivity. Detailed examples are used to illustrate the results and open problems. Chapter 13 considers a more topological question: what are planar semigroups? This concerns extending the notion of planarity from groups to semigroups. We choose semigroups that are close to groups, i. e., which are unions of groups with some additional properties. So we investigate right groups and Clifford semigroups, which were introduced in Chapter 9. We note that the more topological questions about planarity, embeddings on surfaces of higher genus, or colorings are touched on only briefly in this book. We use some of the results in certain places where they relate to algebraic analysis of graphs—the main instances are planarity in Section 6.4 and Chapter 13, and the chromatic number in Chapter 7 and some other places. Each chapter ends with a “Comments” section, which mentions open problems and some ideas for further investigation at various levels of difficulty. I hope they will stimulate the reader’s interest. VIII  Preface How to use this book The text is meant to provide a solid foundation for courses on algebraic graph theory. It is highly selfcontained, and includes a brief introduction to categories and functors and even some aspects of semigroup theory. Different courses can be taught based on this book. Some examples are listed below. In each case, the prerequisites are some basic knowledge of linear algebra. – Chapters 1 through 8—a course covering mainly the matrix aspects of algebraic graph theory. – Chapters 1, 3, 4, 7, and 9 through 13—a course focusing on the semigroup and monoid aspects. – A course skipping everything on categories, namely Chapter 3, the theorems in Sections 4.1, 4.2, 4.3, and 4.6 (although the definitions and examples should be retained) and Sections 11.1 through 11.2. – Complementary to the preceding option, it is also possible to use this text as a short and concrete introduction to categories and functors, with many (somewhat unusual) examples from graph theory, by selecting exactly those parts skipped above. About the literature The literature on graphs is enormous. In the bibliography at the end of the book, I give a list of reference books and monographs, almost all on graphs, ordered chronologically starting from 1936; it is by no means complete. As can be seen from the list, a growing number of books on graph theory are published each year. Works from this list are cited in the text by author name(s) and publication year enclosed in square brackets. Here, I list some books, not all on graphs, which are particularly relevant to this text; some of them are quite similar in content and are cited frequently. – N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge 1996. – M. Behzad, G. Chartrand, L. LesniakForster, Graphs and Digraphs, Prindle, Weber & Schmidt, Boston 1979. New (fifth) edition: G. Chartrand, L. Lesniak, P. Zhang, Graphs and Digraphs, Chapman and Hall, London 2010. – D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs, Academic Press, New York 1979. – C. Godsil, G. Royle, Algebraic Graph Theory, Springer, New York 2001. – G. Hahn, G. Sabidussi (eds.), Graph Symmetry, Kluwer, Dordrecht 1997. – P. Hell, J. Nešetřil, Graphs and Homomorphisms, Oxford University Press, Oxford 2004. – H. Herrlich, G. Strecker, Category Theory, Allyn and Bacon, Boston 1973. – W. Imrich, S. Klavžar, Product Graphs, Wiley, New York 2000. Acknowledgments  IX – – – – R. Kaschek, U. Knauer (eds.), Graph Asymmetries, Discrete Mathematics 309 (special issue) (2009) 5349–5424. M. Kilp, U. Knauer, A. V. Mikhalev, Monoids, Acts and Categories, De Gruyter, Berlin 2000. M. Petrich, N. Reilly, Completely Regular Semigroups, Wiley, New York 1999. D. B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, NJ 2001. Papers, theses, book chapters, and other references are given in the text where they are used. Acknowledgments This book was originally planned as a joint work with Lothar Budach. But the untimely death of Lothar, before we could really get started, cut short our collaboration. First of all, I thank the De Gruyter publishing house and especially the Mathematics Editor Friederike Dittberner, as well as Anja Möbius, for their cooperation and help. Thanks go to all mathematicians, living or dead, whose work I have cannibalized freely—starting with Horst Herrlich, from whose book Axiom of Choice (Springer, Heidelberg 2006) I have taken this sentence. Moreover, I thank all the students who have contributed over the years to improving the course—especially Barbara Langfeld, who looked through a final version of the text. One of my first students was Roland Kaschek, who became a professor in New Zealand, and one of most recent was Xia Zhang, who is now a professor in China. I thank all the colleagues who have used parts of my notes for their own courses and lectures. I thank Mati Kilp (Estonia) for his contributions to several parts of the book, and I am grateful to Kolja Knauer for his comments, suggestions and contributions specially to Chapter 13. I also thank Sayan Panma (Thailand) who contributed many results to Chapters 11 and 12 while he was a PhD student at Oldenburg. I thank Theresia Meyer for doing much of the typesetting of earlier versions, drawing pictures and providing various other sorts of technical help. Above all, I thank my wife, Jane Richter, for her many good ideas as a nonmathematician, her encouragement, and her patience with me during the intense periods of work. Oldenburg and Berlin, April 2011 Ulrich Knauer Preface for the second edition We made the authorship younger, without changing their names too much. We corrected mistakes and misprints as they were pointed out to us or found by ourselves. The list of literature is no longer ordered by appearance date, but by author’s names. And it is updated. Still we mention all books relevant to our subjects as we know or found them, whether cited or not in the List of books. In addition, we collect the works cited in the text, which do not go in the list of books in a new List of cited papers, theses etc. In both lists we noted the pages where the items are cited. We made some minor rearrangements. So, for example, we added a section on the genus of graphs to Chapter 1, thereby shortening later parts. We broadened the scope of the chapters on Cayley graphs of semigroups by several new hints. We thoroughly worked over the Section “Planar Clifford semigroups” and completed it with new results, and added a section on planar semilattices. And, hopefully, we improved formulations, proofs and statements, and added more examples, figures, and pictures. Also Index and Symbol Index became longer. We will publish mistakes and corrections found after appearance of the book on the following webpage: http://www.degruyter.com/books/9783110616125 We again thank De Gruyter and the Mathematics Editor, Dr. Apostolos Damialis, who initiated the second edition of this work, as well as Nadja Schedensack and, in particular, the Project Manager Ina Talandienė, for their cooperation and help. We also repeat our thanks to Jane Richter, who patiently ignored our frequent discussions about the book. Note added in proof We want to keep the memory of our friend and teacher Horst Herrlich (11.09.1937– 13.03.2015). Berlin, Marseille, Barcelona, 2019 https://doi.org/10.1515/9783110617368202 Ulrich Knauer and Kolja Knauer Contents Preface  V Preface for the second edition  XI 1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 3 3.1 Directed and undirected graphs  1 Formal description of graphs  1 Connectedness and equivalence relations  4 Some special graphs  5 Homomorphisms  8 Half, locally, quasistrong, and metric homomorphisms  12 The factor graph, congruences, and the homomorphism theorem  15 Factor graphs  15 The homomorphism theorem  17 The endomorphism type of a graph  19 On the genus of a graph  24 Comments: homomorphisms produce models  27 Graphs and matrices  29 Adjacency matrix  29 Isomorphic graphs and the adjacency matrix  30 Components and the adjacency matrix  31 Adjacency list  33 Incidence matrix  33 Distances in graphs  34 The adjacency matrix and paths  35 The adjacency matrix, the distance matrix, and circuits  35 Endomorphisms and commuting graphs  36 The characteristic polynomial and eigenvalues  37 Circulant graphs  41 Eigenvalues and the combinatorial structure  44 Cospectral graphs  44 Eigenvalues, diameter, and regularity  45 Automorphisms and eigenvalues  46 Comments  47 Categories and functors  49 Categories  49 Categories with sets and mappings, I  50 Constructs, and small and large categories  50 XIV  Contents 3.2 3.3 3.4 4 4.1 4.2 4.3 4.4 4.5 4.6 4.7 Special objects and morphisms  51 Categories with sets and mappings, II  51 Categories with graphs  52 Other categories  53 Products & Co.  54 Coproducts  54 Products  56 Tensor products  58 Categories with sets and mappings, III  58 Functors  59 Covariant and contravariant functors  59 Composition of functors  59 Special functors—examples  60 Mor functors  60 Properties of functors  61 Comments  63 Binary graph operations  65 Unions  65 The union  65 The join  67 The edge sum  67 Products  71 The cross product  71 The coamalgamated product  73 The disjunction of graphs  75 Tensor products and the product in EGra  75 The box product  75 The boxcross product  78 The complete product  79 Synopsis of the results  79 Product constructions as functors in one variable  80 Lexicographic products and the corona  80 Lexicographic products  80 The corona  82 Algebraic properties  83 Mor constructions  84 Diamond products  84 Left inverses for tensor functors  86 Power products  87 Left inverses to product functors  88 Comments  89 Contents  XV 5 5.1 5.2 5.3 5.4 5.5 5.6 6 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 7 7.1 7.2 7.3 7.4 7.5 7.6 7.7 Line graph and other unary graph operations  91 Complements, opposite graphs, and geometric duals  91 The line graph  92 Determinability of G by LG  95 Spectra of line graphs  97 Which graphs are line graphs?  100 The total graph  102 The tree graph  103 Comments  103 Graphs and vector spaces  105 Vertex space and edge space  105 The boundary and co.  106 Matrix representation  107 Cycle spaces, bases & Co.  108 The cycle space  108 The cocycle space  110 Orthogonality  111 The boundary operator & Co.  113 Application: MacLane’s planarity criterion  114 Homology of graphs  116 Exact sequences of vector spaces  117 Chain complexes and homology groups of graphs  117 Application: number of spanning trees  119 Application: electrical networks  123 Application: squared rectangles  128 Application: transport and shortest paths  132 Comments  135 Graphs, groups, and monoids  137 Groups of a graph  137 Edge group  138 Asymmetric graphs and rigid graphs  138 Cayley graphs  145 Fruchttype results  147 Frucht’s theorem and its generalization for monoids  148 Graphtheoretic requirements  149 Smallest graphs for given groups  149 Additional properties of grouprealizing graphs  150 Transformation monoids and permutation groups  154 Actions on graphs  156 Transitive actions on graphs  157 XVI  Contents 7.8 8 8.1 8.2 8.3 8.4 8.5 8.6 8.7 8.8 9 9.1 9.2 9.3 9.4 9.5 9.6 Regular actions  158 Fixed pointfree actions on graphs  160 Comments  161 The characteristic polynomial of graphs  163 Eigenvectors of symmetric matrices  163 Eigenvalues and connectedness  164 Regular graphs and eigenvalues  165 Interpretation of the coefficients of chapo(G)  166 Interpretation of the coefficients for undirected graphs  167 Characteristic polynomials of trees  169 The spectral radius of undirected graphs  170 Subgraphs  170 Upper bounds  171 Lower bounds  172 Spectral determinability  173 Spectral uniqueness of Kn and Kp,q  173 Eigenvalues and group actions  175 Groups, orbits, and eigenvalues  176 Transitive graphs and eigenvalues  177 Derogatory graphs  178 Graphs with Abelian groups  179 Comments  180 Graphs and semigroups  183 Semigroups  183 Endregular bipartite graphs  187 Regular endomorphisms and retracts  187 Endregular and Endorthodox connected bipartite graphs  188 Locally strong endomorphisms of paths  189 Undirected paths  190 Directed paths  192 Algebraic properties of LEnd  195 Wreath product of monoids over an act  197 Structure of the strong monoid  200 The canonical strong decomposition of G  200 Decomposition of SEnd  202 A generalized wreath product with a small category  204 Cardinality of SEnd(G)  205 Regularity and more for TA  206 Regularity and more for SEnd(G)  206 Comments  208 Contents  XVII 10 10.1 10.2 10.3 10.4 10.5 10.6 11 11.1 11.2 11.3 11.4 12 12.1 12.2 12.3 12.4 12.5 13 13.1 13.2 Compositions, unretractivities, and monoids  209 Lexicographic products  209 Unretractivities and lexicographic products  211 Monoids and lexicographic products  214 The union and the join  217 The sum of monoids  217 The sum of endomorphism monoids  218 Unretractivities  219 The box product and the cross product  220 Unretractivities  221 The product of endomorphism monoids  222 Comments  223 Cayley graphs of semigroups  225 The Cay functor  225 Reflection and preservation of morphisms  227 Does Cay produce strong homomorphisms?  228 Products and equalizers  229 Categorical products  229 Equalizers  231 Other product constructions  232 Characterizations of Cayley graphs  234 Cayley graphs of right and left groups  235 Cayley graphs of strong semilattices of semigroups  237 Generating connection sets  238 Examples of strong semilattices of (right or left) groups  241 Comments  245 Vertex transitive Cayley graphs  247 Vertex transitivity  247 Application to strong semilattices of right groups  248 ColAut(S, C)vertex transitivity  250 Aut(S, C)vertex transitivity  251 Application to strong semilattices of left groups  253 Application to Clifford semigroups  256 End (S, C)vertex transitive Cayley graphs  257 Comments  260 Embeddings of Cayley graphs—genus of semigroups  261 The genus of a group  261 Various results and questions about genera  268 On the genus of right groups  269 XVIII  Contents 13.3 13.4 Planar right groups  270 Right groups generated by products on the torus and the plane  279 On planar Clifford semigroups  284 Planar semilattices  285 Planar Clifford semigroups with two groups  287 Comments  300 List of cited papers, theses etc.  303 List of books  307 Index  319 Index of symbols  327 1 Directed and undirected graphs In this chapter, we collect some important basic concepts. These concepts are essential for all mathematical modeling based on graphs. The language and visual representations of graphs are such powerful tools that graph models can be encountered almost everywhere in mathematics and informatics, as well as in many other fields. The most obvious phenomena that can be modeled by graphs are binary relations. Moreover, graphs and relations between objects in a formal sense can be considered the same. The concepts of graph theory also play a key role in the language of category theory, where we consider objects and morphisms. It is not necessary to read this chapter first. Anybody who is familiar with the basic notions may just refer back to this chapter as needed for a review of notation and concepts. 1.1 Formal description of graphs We shall use the word “graph” to refer to both directed and undirected graphs. Only when discussing concepts or results that are specific to one of the two types of graph we will use the corresponding adjective explicitly. Definition 1.1.1. A directed graph or digraph or also oriented graph is a triple G = (V, E, p) where V and E are sets and p : E → V2 is a mapping. We call V the set of vertices or points and E the set of edges or arcs of the graph. Sometimes we will write these sets as V(G) and E(G). The mapping p is called the incidence mapping. The mapping p defines two more mappings o, t : E → V by (o(e), t(e)) := p(e); these are also called incidence mappings. We call o(e) ∈ V the origin or source and t(e) ∈ V the tail or end of e ∈ E. As p defines the mappings o and t, these in turn define p by p(e) := (o(e), t(e)). We will mostly be using the first of the two alternatives G = (V, E, p) or G = (V, E, o, t). We say that the vertex x and the edge e are incident if x is the source or the tail of e. The edges e and e are said to be incident if they have a common vertex. An undirected graph is a triple G = (V, E, p) such that p : E → {V ⊆ V  1 ≤ V  ≤ 2}. An edge e with o(e) = t(e) is called a loop. The preimage p−1 (x, y) is called a multiple edge if p−1 (x, y) > 1. In this case, elements of p−1 (x, y) are said to be parallel. https://doi.org/10.1515/9783110617368001 Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 2  1 Directed and undirected graphs Let G = (V, E, o, t) be a directed graph, let e be an edge, and let x = o(e) and y = t(e); then we also write e : x → y. The vertices of graphs are drawn as points or circles; directed edges are arrows from one point to another, and undirected edges are lines, or sometimes twosided arrows, joining two points. The name of the vertex or edge may be written in the circle or close to the point or edge. See Figure 1.1 for an illustration. Figure 1.1: From left to right: A directed graph, its underlying undirected multigraph, and the simple graph obtained by forgetting multiedges. Definition 1.1.2. Let G = (V, E, p) be a graph. If G has no multiple edges, then we call G a simple graph. Otherwise, we call G a multigraph or multiple graph; sometimes the term pseudograph is used. If G = (V, E, p) is a simple graph, we can consider E as a subset of V 2 , identifying p(E) with E. We then write G = (V, E) or G = (VG , EG ), and for the edge e with p(e) = (x, y) we write (x, y). Simple graphs can now be defined as follows: a simple directed graph is a pair G = (V, E) with E ⊆ V 2 = V × V. Then we again call V the set of vertices and E the set of edges. A simple undirected graph is a simple directed graph G = (V, E) such that (x, y) ∈ E ⇔ (y, x) ∈ E. The edge (x, y) may also be written as {x, y} or xy. This undirected graph is denoted by G and is called the completion of G or the underlying (undirected) graph of G. Mappings w : E → W or w : V → W are called weight functions. Here, W is any set, called the set of weights, and w(x) is called the weight of the edge x or of the vertex x. Definition 1.1.3. A path a from x to y or an x, y path in a graph G is a sequence a = (e1 , e2 , . . . , en ) of edges with o(e1 ) = x, t(en ) = y and t(ei−1 ) = o(ei ) for i = 2, . . . , n. We write a : x → y and call x the start (origin, source) and y the end (tail, sink) of the path a. The sequence x0 , . . . , xn is called the trace of the path a. The set {x0 , . . . , xn } of all vertices of the trace is called the support of the path a, denoted by supp a. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 1.1 Formal description of graphs  3 A path is said to be simple if every vertex appears at most once on the path. A path is said to be closed, or is called a cycle, if the start and end of the path coincide. A simple closed path, i. e., a simple cycle, is called a circuit. The words (simple) semipath, semicycle, or semicircuit will be used if, in the sequence of edges, the tail or origin of each edge equals the origin or tail of the next edge. This means that at least two consecutive edges have opposite directions. The notions of trace and support remain unchanged. In a simple graph, every (semi)path is uniquely determined by its trace. We can describe a path also by its vertices x0 , . . . , xn where (x0 , x1 ), . . . , (xn−1 , xn ) are edges of the path. For undirected graphs, the notions of path and semipath are identical. For the sake of completeness, we also mention the following definition: the trivial x, x path is the path consisting only of the vertex x. It is also called a lazy path. The reader should be aware that, in the literature, the words “cycle” and “circuit” are often used in different ways by different authors. Lemma 1.1.4. For x, y ∈ G, every x, y path contains a simple x, y path. Every cycle in G is the union of circuits. Proof. Take x, y ∈ G. Start on an x, y path from x and proceed until one vertex z is met for the second time. If this does not happen, we already have a simple path; otherwise, we have also traversed a circuit. Remove this circuit, together with all its vertices but z, from the path. Continuing this procedure yields a simple x, y path. If we start with a cycle, we remove one edge e = (y, x), and this gives an x, y path. Now collect the circuits as before. At the end, we have a simple x, y path, which together with e gives the last circuit. Definition 1.1.5. Let G = (V, E), and let a = (e1 , . . . , er ) be a path with ei ∈ E. Then ℓ(a) := r is called the length of a. We denote by F(x, y) the set of all x, y paths in G. Then d(x, y) := min{ℓ(a)  a ∈ F(x, y)} is called the distance from x to y. We call diam(G) := maxx,y∈G d(x, y) the diameter of G. The length of a shortest cycle of G is called the girth of G. In German the figurative word Taillenweite, meaning circumference of the waist, is used. Remark 1.1.6. In connected, symmetric graphs the distance d : V × V → ℝ+0 is a metric, if we set d(x, x) = 0 for all x ∈ V. In this way, (V, d) becomes a metric space. If {ℓ(a)  a ∈ F(x, y)} = 0, then d(x, y) is not defined. Often one sets d(x, y) = ∞ in this case. Definition 1.1.7. For a vertex x of a graph G, the outset of x is the set out(x) := outG (x) := {e ∈ E  o(e) = x}. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 4  1 Directed and undirected graphs The elements of N + (x) := NG+ (x) := {t(e)  e ∈ outG (x)} are called the successors of x in G. The outdegree of a vertex x is the number of successors of x; that is, ← d (x) = outdeg(x) := out(x). Definition 1.1.8. The graph Gop := (V, E, t, o) is called the opposite graph to G. The inset of a vertex x is the outset of x in the opposite graph Gop , so in(x) = inG (x) := outGop (x) = {e ∈ E  t(e) = x}. The elements of N − (x) := NG− (x) := NG+op (x) := {o(e)  e ∈ inG (x)} are called predecessors of x in G. The indegree of a vertex x is the number of predecessors of x; that is, → d (x) = indeg(x) := in(x). A vertex which is a successor or a predecessor of the vertex x is said to be adjacent to x. Definition 1.1.9. In an undirected graph G, a predecessor of a vertex x is at the same time a successor of x. Therefore, in this case, in(x) = out(x) and N(x) := N + (x) = N − (x). We call the elements of N(x) the neighbors of x. Similarly, indeg(x) = outdeg(x). The common value dG (x) = d(x) =: deg(x) is called the degree of x in G. An undirected graph is said to be regular or dregular if all of its vertices have degree d. For directed graphs, similar notation can be defined. 1.2 Connectedness and equivalence relations Here, we make precise some very natural concepts, in particular, how to reach certain points from other points. Definition 1.2.1. A directed graph G is said to be: – weakly connected if for all x, y ∈ V there exists a semipath from x to y; – onesided connected if for all x, y ∈ V there exists a path from x to y or from y to x; – strongly connected if for all x, y ∈ V there exists a path from x to y and from y to x. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 1.3 Some special graphs  5 For undirected graphs, the three concepts coincide. We then simply say that the graph is connected; we shall also use this word as a common name for all three concepts. If G satisfies none of the above three conditions, it is said to be unconnected or disconnected. Example 1.2.2. The following three graphs illustrate the three properties above, in the order given. Definition 1.2.3. A connected graph is said to be nvertex connected if at least n vertices must be removed to obtain an unconnected graph. Analogously, one can define nedge connected graphs. Remark 1.2.4. A binary relation on a set X is usually defined as a subset of the Cartesian product X × X. This often bothers beginners, since it seems too simple a definition to cover all the complicated relations in the real world that one might wish to model. It is immediately clear, however, that every binary relation is a directed graph and vice versa. This is one reason that much of the literature on binary relations is actually about graphs. Arbitrary relations on a set can similarly be described by multigraphs. An equivalence relation on a set X, i. e., a reflexive, symmetric and transitive binary relation in this setting, corresponds to a disjoint union of various graphs with loops at every vertex (reflexivity) which are undirected (symmetry), and such that any two vertices in each of the disjoint graphs are adjacent (transitivity). Note that the above mentioned disjoint union is due to the fact that an equivalence relation on a set X provides a partition of the set X into disjoint subsets and vice versa. 1.3 Some special graphs We now define some standard graphs. These come up everywhere, in virtually any discussion about graphs, so will serve as useful examples and counterexamples. Definition 1.3.1. In the complete graph Kn(l) with n vertices and l loops, where 0 ≤ l ≤ n, any two vertices are adjacent and l of the vertices have a loop. The totally disconnected or discrete graph K n with n vertices and l loops has no edges between distinct vertices and has loops at l vertices. If l = 0, we write Kn or K n . A simple, undirected path with n edges is denoted by Pn . An undirected circuit with n edges is denoted by Cn . An rpartite graph admits a partition of the vertex set V into r disjoint subsets V1 , . . . , Vr such that no two vertices in one subset are adjacent. (l) Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 6  1 Directed and undirected graphs An rpartite graph is said to be complete rpartite if all pairs of vertices from different subsets are adjacent. The complete bipartite graph with V1  = m and V2  = n is denoted by Km,n ; similarly for complete rpartite graphs. A picture of the complete 3partite graph K1,2,3 is in Example 9.5.6. Example 1.3.2 (Some special graphs). Definition 1.3.3. For n ≥ 0, the ncube Qn has a vertex set the set {0, 1}n of 0, 1vectors of length n. We have Q0 = K1 , Q1 = P1 , and Q2 = C4 . A drawing of Q3 can be found in Figure 1.7 and a drawing of Q4 is given in Figure 13.9. Definition 1.3.4. For n ≥ 4 and n2 > k ≥ 1 the generalized Petersen graph G(n, k) is the graph on 2n vertices {v0 , w0 , v1 , w1 , . . . , vn−1 , wn−1 } with edges {vi vj } if i −j is 1 modulo n, edges when indices are seen modulo {wi wj } if i − j is k modulo n, and edges {vi wi } for all 0 ≤ i ≤ n − 1. See Figure 1.2 below, for G(8, 3). The Petersen graph itself is G(5, 2); see Figure 5.1, page 94. We have Q3 = G(4, 1) and more generally one calls G(n, 1) the nprism; see Figure 13.3, page 263, for further examples. The Dodecahedron is the graph G(10, 2); see Figure 5.2, page 94. Definition 1.3.5. A graph without (semi)circuits is called a forest. A connected forest is called a tree of G. A connected graph G with the same vertex set as G is called a spanning tree if it is a tree. If G is not connected, the union of spanning trees for the components of G is called a spanning forest. We give the following wellknown result without proof. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 1.3 Some special graphs  7 Figure 1.2: The Möbius–Kantor graph is the generalized Petersen graph G(8, 3). Theorem 1.3.6. Let G be a graph with n vertices. The following statements are equivalent: (i) G is a tree. (ii) G contains no semicircuits and has n − 1 edges. (iii) G is weakly connected and has n − 1 edges. (iv) Any two vertices of G are connected by exactly one semipath. (v) Adding any edge to G produces exactly one semicircuit. Theorem 1.3.7. A graph is bipartite if and only if it has no semicircuits with an odd number of edges. Proof. For “⇒,” let V = V1 ⋃ V2 . Since edges exist only between V1 and V2 , all circuits must have an even number of edges. For “⇐,” let G be connected and take x ∈ V. Take V1 to be the set of all vertices which can be reached from x along paths using an odd number of edges. Set V2 := V \V1 . If G is not connected, proceed in the same way with its connected parts. Isolated vertices can be assigned arbitrarily. If there is an edge {y, z} in one of the Vi , then take a path from x to y, then the edge {y, z} and then a path from y to x, such that both paths have lengths of the same parity. The resulting semicycle is odd. Lemma 1.1.4 implies that this semicycle contains an odd semicircuit. We recall the following definition: a pair (P, ≤), where P is a set with a reflexive, antisymmetric, transitive binary relation ≤, is called a partially ordered set or a poset. For x, y, z ∈ P, we write x < y if x ≤ y and x ≠ y. We say that y covers x, written x ≺ y, if x < y and if x ≤ z < y implies x = z. See also Remark 1.2.4. We give several graphical representations of a poset. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 8  1 Directed and undirected graphs Definition 1.3.8. The comparability graph of (P, ≤) is an undirected simple graph with vertex set P and edge set {{x, y}  x < y}. The cover graph of a poset (P, ≤) is the graph defined on the vertex set P and edge set {{x, y}  x ≺ y}. The Hasse diagram H P of (P, ≤) is a graphical representation of the cover graph of the poset (P, ≤), such that such that y is above x if x ≺ y. Defining the edge set by {(y, x)  x ≺ y} gives a Hasse diagram where arcs are directed “down.” See Figure 1.3 for an illustration. Figure 1.3: From left to right: comparability graph, cover graph, and Hasse diagram of the poset on P = {x, y, z, w} with x ≤ y, x ≤ z, y ≤ z. Definition 1.3.9. A rooted tree is a triple (T, ≤, r) such that: – (T, ≤) is a partially ordered set; – HT is a tree; and – r ∈ T is an element, the root of the tree, where x ≤ r for all x ∈ T. A marked rooted tree is a quadruple (T, ≤, r, λ) such that (T, ≤, r) is a rooted tree and λ : T → M, with M being a set, is a mapping (weight function), which in this context is called the marking function. We call λ(x) a marking of x. 1.4 Homomorphisms In mathematics, as in the real world, mappings produce images. In such images, certain aspects of the original may be suppressed, so that the image is in general simpler than the original. But some of the structures of the original, those which we want to study, should be preserved. Structurepreserving mappings are usually called homomorphisms. For graphs, it turns out that preservation of different levels of structure or different intensities of preservation quite naturally lead to different types of homomorphism. First, we give a very general definition of homomorphisms. We will then introduce the socalled covering, which has some importance in the field of informatics. The general definition will then be specialized in various ways, and later we will use almost exclusively these variants. A reader who is not especially interested in the general aspects of homomorphisms may wish to start with Definition 1.4.3. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 1.4 Homomorphisms  9 Definition 1.4.1. Let G1 = (V1 , E1 , o1 , t1 ) and G2 = (V2 , E2 , o2 , t2 ) be two directed graphs. A graph homomorphism θ : G1 → G2 is a pair θ = (θV , θE ) of mappings θV : V1 → V2 θE : E1 → E2 such that o2 (θE (e)) = θV (o1 (e)) and t2 (θE (e)) = θV (t1 (e)) for all e ∈ E1 . If θ : G1 → G2 is a graph homomorphism and v is a vertex of G1 , then θE (outG1 (v)) ⊆ outG2 (θV (v)) and θE (inG1 (v)) ⊆ inG2 (θV (v)). Definition 1.4.2. If θE outG (v) is bijective for all v ∈ V, we call θ a covering of G2 . If 1 θE outG (v) is only injective for all v ∈ V, then it is called a precovering. 1 For simple directed or undirected graphs, we will mostly be working with the following formulations and concepts rather than the preceding two definitions. The main idea is that homomorphisms have to preserve edges. If, in the following, we replace “homo” by “ega,” we have the possibility of identifying adjacent vertices as well. This could also be achieved with usual homomorphisms if we consider graphs that have a loop at every vertex. Illustrating pictures follow in Example 1.5.3. Definition 1.4.3. Let G = (V, E) and G = (V , E ) be two graphs. A mapping f : V → V is called a: – graph homomorphism if (x, y) ∈ E ⇒ (f (x), f (y)) ∈ E ; – graph egamorphism (weak homomorphism) if (x, y) ∈ E and f (x) ≠ f (y) ⇒ (f (x), f (y)) ∈ E ; – graph comorphism (continuous graph mapping) if (f (x), f (y)) ∈ E ⇒ (x, y) ∈ E; – strong graph homomorphism if (x, y) ∈ E ⇔ (f (x), f (y)) ∈ E ; – strong graph egamorphism if (x, y)∈E and f (x) =f̸ (y)⇔(f (x), f (y))∈E ; – graph isomorphism if f is a strong graph homomorphism and bijective or, equivalently, if f and f −1 are graph homomorphisms. When G = G , we use the prefixes “endo,” “auto” instead of “homo,” “iso.” We note that the term “continuous graph mapping” is borrowed from topology; there continuous mappings reflect open sets, whereas here they reflect edges. Remark 1.4.4. Note that, in contrast to algebraic structures, bijective graph homomorphisms are not necessarily graph isomorphisms. This can be seen from Example 1.4.9; there the nonstrong subgraph can be mapped bijectively onto the graph G without being isomorphic to it. Remark 1.4.5. Denote by Hom(G, G ), Com(G, G ), EHom(G, G ), SHom(G, G ), SEHom(G, G ), and Iso(G, G ) the homomorphism sets. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 10  1 Directed and undirected graphs Analogously, let End(G), EEnd(G), Cnd(G), SEnd(G), SEEnd(G), and Aut(G) denote the respective sets when G = G . These form monoids. Indeed, End(G) and SEnd(G), as well as EEnd(G) and SEEnd(G), are monoids, i. e., sets with an associative multiplication (the composition of mappings) and an identity element (the identical mapping). Clearly, End(G) is closed. Also, SEnd(G) is closed, since for f , g ∈ SEnd(G) we get f strong g strong (fg(x), fg(y)) ∈ E ⇐⇒ (g(x), g(y)) ∈ E ⇐⇒ (x, y) ∈ E. Definition 1.4.6. For f0 ∈ EHom(G, G ), which identifies exactly two adjacent vertices, the graph f0 (G) is also called an elementary contraction of G. The result of a series of elementary contractions fn (fn−1 (. . . (f0 (G)) . . . )) is called a contraction of G. It is denoted by G/E if E ⊆ E is the set of contracted edges. A graph H is called a (graph) minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges. Subdividing an edge e = xy in a graph G means replacing e by a path xzy, where z is a new vertex. A graph H is a subdivision of G is H can be obtained from G by subdividing a sequence of edges. See Figure 1.4 for an illustration. Figure 1.4: Left: Deleting gray edges and vertices and contracting gray bubbles yields a K5 minor. Right: Deleting gray edges and vertices yields a subdivision of K3,3 . Note that if H is a subdivision of G, then G can be obtained from H by contractions. In particular, G is a minor of its subdivisions but the converse does not hold. For instance, the graph in Figure 1.4 does not contain a subdivision of K5 because it has maximum degree 3. Proposition 1.4.7. Let G and G be graphs and f : G → G a graph isomorphism. For x ∈ G, we have indeg(x) = indeg(f (x)) and outdeg(x) = outdeg(f (x)). Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 1.4 Homomorphisms  11 Proof. We prove the statement for undirected graphs. As f is injective, we get NG (x) = f (NG (x)). As f is a homomorphism, we get f (NG (x)) ⊆ NG (f (x)), i. e., f (NG (x)) ≤ NG (f (x)). As f is surjective, we have NG (f (x)) ⊆ f (G); and, since f is strong, we get NG (f (x)) ≤ NG (x). Putting the above together, using the statements consecutively, we obtain NG (x)= NG (f (x)). Now we use deg(x) = NG (x) and deg(f (x)) = NG (f (x)) to get the result. Subgraphs The different sorts of homomorphisms lead to different sorts of subgraphs. First, let us explicitly define subgraphs and strong subgraphs. Definition 1.4.8. Let G = (V, E). A graph G = (V , E ) is called a subgraph (or partial subgraph) of G if there exists an injective graph homomorphism f : V → V. A graph G is called a strong subgraph (or induced subgraph or vertex induced subgraph) if there exists an injective strong graph homomorphism f : V → V. Example 1.4.9 (Subgraphs). is a not strong subgraph while is a strong subgraph of G: Remark 1.4.10. A (nontrivial) strong subgraph has fewer vertices than the original graph, but all edges of the original graph between these vertices are contained in the strong subgraph. A subgraph in general contains fewer vertices or fewer edges than the original graph. (Semi)paths, (semi)cycles and (semi)circuits are subgraphs. Definition 1.4.11. A strong, onesided, or weak component of a graph is, respectively, a maximal strongly, onesided or weakly connected subgraph. Compare Example 1.2.2. A complete subgraph is also called a clique of G. The number of vertices ω(G) of a largest clique of G is called the clique number of G. Now we introduce the “edge dual” concept of a clique. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 12  1 Directed and undirected graphs Definition 1.4.12. Two vertices x, y ∈ V are called independent vertices if (x, y) ∉ E and (y, x) ∉ E. The vertex independence number is defined as β0 (G) := max{U : U ⊆ V, independent}. Analogously, two nonincident edges are called independent edges, and we can define the edge independence number β1 (G). A set of pairwise independent edges of G is called a matching in G. A kregular spanning subgraph is called a kfactor of G; a 1factor of G is called a perfect matching of G. 1.5 Half, locally, quasistrong, and metric homomorphisms In addition to the usual homomorphisms, we introduce the following four sorts of homomorphisms. As always, homomorphisms are used to investigate the structure of objects. The large number of different homomorphisms of graphs shows how rich and variable the structure of a graph can be. In Section 1.9, we summarize which of these homomorphisms have appeared where and under which names; we also suggest how they might be used in modeling. The motivation for these other homomorphisms comes from the concept of strong homomorphisms or, more precisely, the notion of comorphism, i. e., the continuous mapping. A continuous mapping “reflects” edges of graphs. The following types of homomorphism reduce the intensity of reflection. In other words, an ordinary homomorphism f : G → G does not reflect edges at all. This means it could happen that (f (x), f (y)) is an edge in G even though (x, y) is not an edge in G, and there may not even exist any preimage of f (x) which is adjacent to any preimage of f (y) in G. The following three concepts “improve” this situation step by step. From the definitions, it will become clear that there exist intermediate steps that would refine the degree of reflection. Definition 1.5.1. Let G = (V, E) and G = (V , E ) be graphs, and let f ∈ Hom(G, G ). For x, y ∈ V, set X := f −1 (f (x)), Y := f −1 (f (y)). Let (f (x), f (y)) ∈ E . Then f is said to be: – halfstrong if there exists x̃ ∈ X and ỹ ∈ Y such that (x,̃ y)̃ ∈ E; ∀ x ∈ X, ∃ yx ∈ Y such that (x, yx ) ∈ E and – locally strong if { ∀ y ∈ Y, ∃ xy ∈ X such that (xy , y) ∈ E; ∃ x̃0 ∈ X such that ∀ ỹ ∈ Y, (x̃0 , y)̃ ∈ E and – quasistrong if { ∃ ỹ0 ∈ Y such that ∀ x̃ ∈ X, (x,̃ ỹ0 ) ∈ E. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 1.5 Half, locally, quasistrong, and metric homomorphisms  13 We call x̃0 and ỹ0 central vertices or, in the directed case, a central source and a central sink in X and in Y with respect to (f (x), f (y)). Remark 1.5.2. With the obvious notation, one has Hom(G, G ) ⊇ HHom(G, G ) ⊇ LHom(G, G ) ⊇ QHom(G, G ) ⊇ SHom(G, G ) ⊇ Iso(G, G ), End(G) ⊇ HEnd(G) ⊇ LEnd(G) ⊇ QEnd(G) ⊇ SEnd(G) ⊇ Aut(G) ⊇ {idG }. Note that apart from SEnd(G), Aut(G), and {idG }, the other subsets of End(G) are, in general, not submonoids of End(G). We will talk about the group and the strong monoid of a graph, and about the quasistrong monoid, locally strong monoid, and halfstrong monoid of a graph if these really are monoids. Example 1.5.3 (Different homomorphisms). We give three of the four examples for undirected graphs. The example for the halfstrong homomorphism in the directed case shows that the other concepts can also be transferred to directed graphs. From the definitions, we immediately obtain the following theorem. To get an idea of the proof, one can refer to the graphs in Example 1.5.3. Theorem 1.5.4. Let G ≠ K1 be a bipartite graph with V = V1 ⋃ V2 . Let (x1 , x2 ) be an edge with x1 ∈ V1 and x2 ∈ V2 . We define an endomorphism r of G by r(V1 ) = {x1 } and r(V2 ) = {x2 }. Obviously, r ∈ HEnd(G). Moreover, the following hold: Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 14  1 Directed and undirected graphs – – – r ∈ LEnd(G) if and only if G has no isolated vertices; r ∈ QEnd(G) if and only if V1 has a central vertex x̃0 with N(x̃0 ) = V2 and correspondingly for V2 ; r ∈ SEnd(G) if and only if G is complete bipartite. Proposition 1.5.5. A noninjective endomorphism f of G is strong if and only if for all x ∈ V with f (x) = f (x ) one has NG (x) = NG (x ). Note that for adjacent vertices x and x , this is possible only if both have loops. Proof. Necessity is clear from the definition. Now suppose that NG (x) = NG (x ) for x, x ∈ V(G). Construct f by setting f (x) = x and f (y) = y for all y ≠ x, x . It is clear that f ∈ SEnd(G). Definition 1.5.6. A homomorphism f from G to G is said to be metric if for any vertices x, y ∈ V(G) there exist x ∈ f −1 f (x) and y ∈ f −1 f (y) such that d(f (x), f (y)) = d(x , y ). Denote by MEnd(G) the set of metric endomorphisms of G and by Idpt(G) the set of idempotent endomorphisms, i. e., f ∈ End(G) with f 2 = f , of G. Corollary 1.5.7. If Aut(G) ≠ SEnd(G), thenSEnd(G) \ Aut(G) contains at least two idempotents. As usual we make the following definition. Definition 1.5.8. A homomorphism f from G to f (G) ⊆ H is called a retraction if there exists an injective homomorphism g from f (G) to G such that fg = idf (G) . In this case, f (G) is called a retract of G, and then G is called a coretract of f (G) while g is called a coretraction. If H is an unretractive retract of G, i. e., if End(H) = Aut(H), then H is also called a core of G. Remark 1.5.9. It is straightforward to check that G is a retract of G if and only if there exists f ∈ End(G) such that G ≅ f (G) and f restricted to f (G) is the identity. Remark 1.5.10. One has Idpt(G), LEnd(G) ⊆ MEnd(G) ⊆ HEnd(G). Example 1.5.11 (HEnd, LEnd, QEnd are not monoids). The sets HEnd, LEnd, QEnd are not closed with respect to composition of mappings. To see this, consider the following graph G: Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 1.6 The factor graph, congruences, and the homomorphism theorem  15 together with the mappings f = ( 31 42 35 44 55 ) and g = ( 11 22 33 42 55 ). Now f ∈ QEnd(G) and g ∈ HEnd(G) but f 2 ∈ HEnd(G)\LEnd(G) and g∘f ∈ End(G)\HEnd(G). These properties are not changed if we add another vertex 0 to the graph which we make adjacent to every other vertex. The graph is then connected but no longer bipartite. Question. Do Idpt and MEnd always form monoids? Can you describe graphs where this is the case? 1.6 The factor graph, congruences, and the homomorphism theorem The study of factor graphs by graph congruences turns out to be fundamental for the general investigation of homomorphisms. The connection to arbitrary homomorphisms is established through the canonical epimorphisms, and this leads to the homomorphism theorem for graphs. We formulate the theorem only for ordinary graph homomorphisms. Factor graphs Definition 1.6.1. Let ϱ ⊆ V × V be an equivalence relation on the vertex set V of a graph G = (V, E), and denote by xϱ the equivalence class of x ∈ E with respect to ϱ. Then Gϱ = (Vϱ , Eϱ ) is called the factor graph of G with respect to ϱ, where Vϱ = V/ϱ and (xϱ , yϱ ) ∈ Eϱ if there exist x ∈ xϱ and y ∈ yϱ with (x , y ) ∈ E, where ϱ is called a graph congruence. Example 1.6.2 (Congruence classes, factor graphs). In Figure 1.5, we exhibit some graphs together with congruence classes (encircled vertices) and the corresponding factor graphs: Remark 1.6.3. By the definition of Gϱ , the canonical epimorphism πϱ : G → Gϱ x → xϱ (which is always surjective) is a halfstrong graph homomorphism. Note that, in general, a graph congruence ϱ is just an equivalence relation. If we have a graph G = (V, E) and a congruence ϱ ⊆ V × V such that there exist x, y ∈ V with (x, y) ∈ E and x ϱ y, then (xϱ , xϱ ) ∈ Eϱ , i. e., Gϱ has loops. If we want to use only loopless graphs, then πϱ : G → Gϱ is a graph homomorphism only if x ϱ y ⇒ (x, y) ∉ E. Therefore, we make the following definition. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 16  1 Directed and undirected graphs Figure 1.5: Three congruence relations in a graph and the corresponding factor graphs. Definition 1.6.4. A (loopfree) graph congruence ϱ is an equivalence relation with the additional property that x ϱ y ⇒ (x, y) ∉ E. Definition 1.6.5. Let Gϱ be the factor graph of G with respect to ϱ. If the canonical mapping πϱ : G → Gϱ is a strong (respectively quasistrong, locally strong, or metric) graph homomorphism, then the graph congruence ϱ is called a strong (resp., quasistrong, locally strong, or metric) graph congruence. Example 1.6.6 (Connectedness relations). On G = (V, E), with x, y ∈ V, consider the following relations: x ϱ1 y ⇔ there exists an x, y path and a y, x path or x = y; x ϱ2 y ⇔ there exists an x, y semipath or x = y. x ϱ3 y ⇔ there exists an x, y path or a y, x path. The relation ϱ1 is an equivalence relation; the factor graph Gϱ1 is called a condensation of G. The relation ϱ2 is an equivalence relation; the factor graph Gϱ2 consists only of isolated vertices with loops. The relation ϱ3 is not transitive and, therefore, not an equivalence relation. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 1.6 The factor graph, congruences, and the homomorphism theorem  17 The homomorphism theorem For convenience, we start with the socalled mapping theorem, i. e., the homomorphism theorem for sets, preceded by the usual result on mappinginduced congruence relations. Then, as for sets, we formulate the homomorphism theorem for graphs. Proposition 1.6.7. Let G and H be sets, and let f : G → H be a mapping. Using f we obtain an equivalence relation on G, the socalled induced congruence, if we define, for x, y ∈ G, x ϱf y ⇔ f (x) = f (y). Moreover, by setting πϱf (x) = xϱf for x ∈ G, we get a surjective mapping onto the factor set Gϱf = G/ϱf . Here, xϱf denotes the equivalence class of x with respect to ϱf and G/ϱf the set of all these equivalence classes. Proof. It is straightforward to check that ϱf is reflexive, symmetric, and transitive, i. e., it is an equivalence relation on G. Surjectivity of πϱf follows from the definition of the factor set. Proposition 1.6.8. Let G and H be graphs, and let f : G → H be a graph homomorphism. Using f , we obtain a graph congruence by defining, for x, y ∈ V(G), x ϱf y ⇔ f (x) = f (y). Moreover, by setting πϱf (x) = xϱf for x ∈ G, we get a surjective graph homomorphism onto the factor graph Gϱf = G/ϱf . Here, xϱf denotes the congruence class of x with respect to ϱf and Gϱf the factor graph formed by these congruence classes. Proof. As for sets, we know that ϱf is an equivalence relation and πϱf is a surjective mapping by Proposition 1.6.7. Now use Remark 1.6.3. Proposition 1.6.9 (The homomorphism theorem for sets). For every mapping f : G → H from a set G to a set H, there exists exactly one injective mapping f : Gϱf → H, with f (xϱf ) = f (x) for x ∈ G, such that the following diagram is commutative, i. e., f = f ∘ πϱf : Moreover, the following statements hold: (a) If f is surjective, then f is surjective. (b) If we replace ϱf by an equivalence relation ϱ ⊆ ϱf , then f : Gϱ → H is defined in the same way, but is injective only if ϱ = ϱf . Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 18  1 Directed and undirected graphs Proof. Define f as indicated. We shall show that f is welldefined. Suppose that xϱf = xϱ f in Gϱf ; then xϱf x , and thus f (xϱf ) = f (x) = f (x ) = f (xϱ f ). It is clear that f makes the diagram commutative and is the uniquely determined mapping with these properties. Indeed, if a mapping f has the same properties, then f (xϱf ) = f πϱf (x) = f (x) = f πϱf (x) = f (xϱf ) for all xϱf ∈ Gϱf . It is also clear that the two additional properties are valid. In particular, the inclusion ϱ ⊆ ϱf ensures that f is welldefined also in this case. Theorem 1.6.10 (The homomorphism theorem for graphs). For every halfstrong graph homomorphism f : G → H, there exists exactly one injective strong graph homomorphism f : Gϱf → H, with f (xϱf ) = f (x) for x ∈ G, such that we have the following commutative diagram, i. e., f = f ∘ πϱf : Moreover, the following statements hold: (a) If f is surjective, then f is surjective. (b) If we replace ϱf by a graph congruence ϱ ⊆ ϱf , then f : Gϱ → H is defined in the same way, but is injective and strong only if ϱ = ϱf . (c) If (a) and (b) are fulfilled, then Gϱf ≅ H. Proof. Define f as indicated, just as we did for sets in Proposition 1.6.9. Then f is welldefined, is unique and makes the diagram commutative. We only have to show that πϱf and f are graph homomorphisms. For πϱf this comes from Proposition 1.6.8. Take (xϱf , yϱf ) ∈ E(Gϱf ) and consider (f (xϱf ), f (yϱf )) = (f (x), f (y)). As f is halfstrong, there exists a preimage (x , y ) ∈ E(G) of (xϱf , yϱf ) ∈ E(Gϱf ), which implies (f (x), f (y)) ∈ E(H). The two additional properties are the same as for sets, so nothing further needs to be proved. Remark 1.6.11. In the language of category theory, the essence of the homomorphism theorem is that every homomorphism has an epimono factorization in the given category. Note that in the graph categories considered, epimorphisms (epis) are surjective and monomorphism (monos) are injective. The monomorphism is called an embedding of the factor graph into the image graph. The embedding is strong if f is at least halfstrong. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 1.7 The endomorphism type of a graph  19 Corollary 1.6.12. Surjective endomorphisms and injective endomorphisms of a finite graph (set) are already automorphisms. Example 1.6.13. We consider again the homomorphism f from Example 1.5.11. Here, the congruence classes are {1}, {2, 4}, and {3, 5}, so πϱf maps every vertex to its congru ence class, and f is the embedding which takes 1ϱf to 3, 2ϱf to 4 and 3ϱf to 5. The result of this procedure can be visualized as follows: Application 1.6.14. As an application, we observe that the homomorphism theorem can be used to determine all homomorphisms from G to H as follows. We first determine all congruences on G, giving all possible natural surjections π. Then, for each congruence relation ϱ which is given by its congruence classes, i. e., for every πϱ , we determine all possible embeddings of Gπϱ into H. Each of these embeddings corresponds to some f , all of which are different but induce the same congruence. In Example 1.6.13, we have G = H and obtain all embeddings as follows. The class {1} can be mapped onto any vertex of G, and after that the classes {2, 4} and {3, 5} forming an edge in Gπϱ can be mapped onto every edge of G which does not contain the image of {1} in the actual embedding. In particular, if we map {1} onto 1 we have six possible embeddings, and they all give quasistrong endomorphisms. If we map {1} onto 3 or 4, we have four possible embeddings in each case, two of which give quasistrong, which are not strong, and the other two give not even halfstrong endomorphisms. If we map {1} onto 2 or 5, we have two possible embeddings, which in each case give not halfstrong endomorphisms. So, overall, this congruence relation gives ten quasistrong and eight not halfstrong endomorphisms. The same method for groups is formulated in Project 9.1.8. 1.7 The endomorphism type of a graph For a more systematic treatment of different endomorphisms, we define the endomorphism spectrum and the endomorphism type of a graph. Definition 1.7.1. For the graph X, consider the following sequence from Remark 1.5.2 (brackets around G are omitted for simplicity): End G ⊇ HEnd G ⊇ LEnd G ⊇ QEnd G ⊇ SEnd G ⊇ Aut G. With this sequence, we associate the sequence of respective cardinalities, Endospec G = (End G, HEnd G, LEnd G, QEnd G, SEnd G, Aut G), Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 20  1 Directed and undirected graphs and we call this 6tuple the endospectrum or endomorphism spectrum of G. Next, associate with the above sequence a 5tuple (s1 , s2 , s3 , s4 , s5 ) with si ∈ {0, 1} for i = 1, . . . , 5, where si = 1 stands for ≠ and si = 0 stands for =, such that s1 = 1 means that End G ≠ HEnd G, s2 = 0 means that HEnd G = LEnd G, etc. We use decadic coding and call the integer ∑5i=1 si 2i−1 the endotype or endomorphism type of G and denote it by endotype G. If End G = Aut G, we call the graph G unretractive or EA unretractive; if End G = 1, we call the graph rigid; and if Aut G = 1, we call the graph asymmetric. More generally, if XG = X G for X, X ∈ {End, HEnd, LEnd, QEnd, Aut}, we call the graph XX unretractive. In principle, there are 32 possibilities, i. e., endotype 0 up to endotype 31. We will now prove that graphs of endotypes 1 and 17 do not exist. Proposition 1.7.2. Let G be a finite graph such that End G ≠ HEnd G. Then HEnd G ≠ SEnd G. Proof. Take f ∈ End G \ HEnd G. Then there exists (f (x), f (x )) ∈ E(G) but for all x, x with f (x) = f (x) and f (x ) = f (x ) one has (x, x ) ∉ E(G). From finiteness of End G, we get an idempotent power f i of f , i. e., (f i )2 = f i , and thus f i ∈ HEnd G; see Remark 1.5.10. In particular, since (f i (x), f i (x )) ∈ E(G), we have that f i (x) and f i (x ) are fixed under f i , and thus they are adjacent preimages. Moreover, f i ∉ SEnd G since not all preimages are adjacent, in particular (x, x ) ∉ E(G). Before analyzing the endotypes of graphs in more detail, we consider all endotypes with regard to whether or not Aut G = 1. Proposition 1.7.3. Aut G = 1 implies SEnd G = 1. Proof. Take f ∈ SEnd G \ Aut G. Then there exist x, x ∈ V(G), x ≠ x , with f (x) = f (x ) and N(x) = N(x ) by Proposition 1.5.5. Then the mapping which permutes exactly x and x is a nontrivial automorphism of G. The preceding result shows that for endotypes 16 up to 31 we always have Aut G ≠ 1, since SEnd G ≠ Aut G in these cases. So endotypes 0 to 15 get an additional a if one has asymmetry, i. e., if AutG = 1. We can say that endotype 0 describes unretractive graphs and endotype 0a describes rigid graphs. Endotypes 0 up to 15 describe SA unretractive graphs, and endotypes 0a, 2a, . . . , 15a describe asymmetric graphs. Endotype 16 describes ES unretractive graphs which are not unretractive. Endotype 31 describes graphs for which all six sets are different. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 1.7 The endomorphism type of a graph  21 Theorem 1.7.4. There exist simple graphs without loops of endotype 0, 0a, 2, 2a, 3, 3a, . . . , 15, 15a, 16, 18, 19, . . . , 31. Proof. See M. Böttcher and U. Knauer [11, 12] The following result is an approach to the question of to what extent trees are determined by their endospectrum. It also shows that the endospectrum in general does not determine graphs up to isomorphism. We will use some new notation. We call K1,n a star. Take two stars K1,n , K1,m with n ≥ 3, m ≥ 2 or vice versa and identify one edge of one star with one edge of the other star. The result is called a double star. A definition in terms of the lexicographic product can be found in the table of Theorem 1.7.5. Theorem 1.7.5. Let G be a tree, with G ≠ K2 . The following table characterizes G with respect to endotypes, which are given by their decadic coding in the first column and explicitly in the second column. Classes of endomorphisms are abbreviated by their first letters, and νG ≠ Δ indicates the existence of two different vertices in G which have exactly the same neighbors; cf. Definitions 9.5.1 and 10.2.2. For the notation in the last column, see the generalized lexicographic product in Section 4.4. Note that Pn has n edges and n + 1 vertices. N0 Endotype νG diam Examples or complete descriptions 6 10 16 22 E = H ≠ L ≠ Q = S = A E = H ≠ L = Q ≠ S = A E = H = L = Q = S ≠ A E = H ≠ L ≠ Q = S ≠ A =Δ =Δ ≠ Δ ≠ Δ ≥4 =3 =2 ≥4 26 E = H ≠ L = Q ≠ S ≠ A ≠ Δ =3 P4 is the smallest P3 is the only one Exactly the stars, i. e., K1,n for n ≥ 2 P4 with one endvertex doubled, e. g., P4 [K 2 , K1 , K1 , K1 , K1 ], which is the smallest Exactly the “double stars,” i. e., P3 [K n , K1 , K1 , K m ] with n ≥ 2 or m ≥ 2 Asymmetric trees G, i. e., G such that Aut G = 1, are possible only with endotype 6; in other words, they have endotype 6a. The smallest is the path of length 5, with one pending vertex at the third vertex, i. e., a vertex of degree 1. A proof follows after Proposition 1.7.14. Lemma 1.7.6. Let G be a graph such that N(x) ⫋ N(x ) for some x, x ∈ G with (x, x ) ∉ E(G). Then HEnd G ≠ LEnd G. Proof. Define f (x) = f (x ) = x and f (y) = y for all y ≠ x ∈ G. Then obviously f ∈ HEnd G. But f ∉ LEnd G, because for x ∈ N(x ) \ N(x) one has (f (x ), f (x)) = (x , x ) ∈ E(G), f −1 (x ) = {x }, f −1 (x ) = {x, x } but (x, x ) ∉ E(G), i. e., not every preimage of x is adjacent to some preimage of x . The following two lemmas are clear. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 22  1 Directed and undirected graphs Lemma 1.7.7. Suppose G is a tree with x, x ∈ G such that N(x) ⫋ N(x ). Then diam(G) ≥ 3. Lemma 1.7.8. Let G be a tree with diam(G) ≥ 3. Take x, x , x ∈ G with {x } = N(x) ⫋ N(x ) ⊆ {x, x }. Then, by defining f (x) = x and f (y) = y for y ≠ x, we get f ∈ HEnd G \ LEnd G. Lemma 1.7.9. Let G be a double star. Then QEnd G ≠ SEnd G. Proof. Take {x0 , x0 , x1 , x1 }, a longest simple path in G. Define f (N(x0 )) = {x1 } and f (N(x1 )) = {x0 }. Then f ∈ QEnd G, since x1 ∈ f −1 (x1 ) is adjacent to every vertex in N(x1 ) = f −1 (x0 ) and x0 ∈ f −1 (x0 ) is adjacent to every vertex in N(x0 ) = f −1 (x1 ). But f ∉ SEnd G as (x0 , x1 ) ∉ E(G). Proposition 1.7.10. Let G be a tree with diam(G) ≥ 4. Then QEnd G = SEnd G. Proof. Take f ∈ QEnd G. Then there exists (x, x ) ∈ E(G) such that (f (x), f (x )) ∈ E(G), and we may assume that x and x are central with respect to (f (x), f (x )). Then U := f −1 (f (x)) ⊆ N(x ) and U := f −1 (f (x )) ⊆ N(x). As diam(G) ≥ 4, there exists y ∈ N(U ) such that (y, x ) ∈ E(G) for some x ∈ U . Then (f (y), f (x )) = (f (y), f (x )) ∈ E(G), and since f ∈ QEnd G we get that y, say, is adjacent to all vertices in U , and hence to x in particular. But then U  = 1, because otherwise there would be a cycle {y, x , x, x , y) in G, which is impossible since G is a tree. Moreover, every vertex in U has degree 1 with the common neighbor x . Together with Proposition 1.5.5, this implies that f ∈ SEnd G. Proposition 1.7.11. If G is a tree with diam(G) ≥ 4, then LEnd G ≠ QEnd G. Proof. As diam(G) ≥ 4, the tree contains P4 = {x0 , x1 , x2 , x3 , x4 }. Define f : G → G as follows: all vertices with even distance from x2 are mapped onto x2 ; all other vertices are mapped onto x1 . Then f ∈ LEnd G, since every preimage of x2 is adjacent to some preimage of x1 and vice versa. But f ∉ QEnd G because no vertex exists in the preimage of x1 which is adjacent to x0 and to x4 , as G has no cycles. Lemma 1.7.12. For stars G = K1,n , one has End G = SEnd G. Proof. We may assume that n > 1. If f (G) > 2 for an endomorphism f , the central vertex of the star is fixed and, therefore, f is strong. If f (G) = 2, i. e., f (G) = K2 , then f is also strong. Proposition 1.7.13. Let G ≠ K2 be a tree with diam(G) ≤ 3. Then LEnd G = QEnd G. Proof. If G ≠ K2 is a tree with diam(G) ≤ 3, then G is a star or a double star. In the first case, the statement is contained in Lemma 1.7.12. So let G be a double star, i. e., suppose that there exist x0 , x1 ∈ G with V(G) = N(x0 ) ⋃ N(x1 ) and (x0 , x1 ) ∈ E(G). Take f ∈ LEnd G. Then it is impossible to have f (y) = x1 and f (y ) ≠ x1 for y, y ∈ N(x0 ) \ {x1 }. So f identifies only vertices inside N(x0 ) \ {x1 } or inside N(x1 ) \ {x0 }, possibly followed by an automorphism of the resulting graph, and we have f ∈ SEnd G. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 1.7 The endomorphism type of a graph  23 Proposition 1.7.14. For any graph G, one has SEnd G = Aut G if and only if RG = Δ, i. e., N(x) ≠ N(x ) for all x ≠ x ∈ G. Proof. If the vertices x ≠ x have the same neighbors, then f (x) = x is a nonbijective strong endomorphism, provided all other vertices are fixed. Proof of Theorem 1.7.5. It is clear that the third column of the table covers all possible trees. The first column of equalities E = H is obvious for all trees. In the second column, the inequalities H ≠ L are furnished by Lemmas 1.7.8 and 1.7.6. The equality H = L for type 16 is taken care of by Lemma 1.7.12. The inequalities L ≠ Q are provided by Proposition 1.7.11, and the equalities L = Q are given by Proposition 1.7.13. The equalities Q = S are taken care of by Proposition 1.7.10 and for type 16 again by Lemma 1.7.12. The inequalities are given by Lemma 1.7.9, noting that P3 is also a double star. The relations between S and A come from Proposition 1.7.14. Now consider the “examples” and “complete descriptions” in the last column of Theorem 1.7.5. The statements about endotypes 6, 10, and 22 follow, by inspection, from what was said about νG and diam. The statement about endotype 16 follows from Lemma 1.7.12 together with the fact that νG ≠ Δ and diam(G) = 2. The statement about endotype 26 comes from he statement about endotype 10, if we double at least one end vertex, since then νG ≠ Δ. The last assertion about asymmetric trees is also implied by 4.13 in R. Novakovski and I. Rival [67]. Indeed, Aut G = 1 is possible only if SEnd G = Aut G (see Proposition 1.7.3), i. e., only for endotypes smaller than 16; so in our situation only endotype 6 remains. The statement concerning the smallest examples follows by inspection. In the following table, we use the (disjoint) union of graphs in a naive way. A formal definition (as coproduct) will follow in Chapter 3. Endotype Graph 0 K2 2 4 Graph 16 K n , K1,n , n ≥ 2 K1 ⋃ K2 18 K n ⋃ K2 , n ≥ 2 ⋃n≥2 K2 19 K n ⋃(⋃n≥2 Kn ), K m ⋃ K1,n , n ≥ 2, m ≥ 1 6 22 7 10 Endotype 23 P3 26 11 27 15 31 double stars Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 24  1 Directed and undirected graphs Theorem 1.7.15. Bipartite graphs are exactly of the following endotypes, where the graphs or their common structures are given where possible. Proof. See U. Knauer [53]. Note that adding an isolated vertex to a connected graph which is not of endotype 0 or 16 adds 1 to the value of the endotype. This gives examples of graphs of endotypes 7, 11, 23, and 27 when starting with suitable trees from Theorem 1.7.5. The procedure yields graphs with endotype 2 or 18 when starting with graphs of endotype 0 or 16. Question. For which of the trees in Theorem 1.7.5 do the sets which are not monoids in general form monoids? The question makes sense for LEnd and endotypes 6, 10, 22, and 26. It seems possible that trees are determined by their endomorphism spectrum up to isomorphism. Obviously, this is not the case for the endotype. Would this be a worthwhile question to investigate? Some more information about this can be found in U. Knauer [52]. 1.8 On the genus of a graph Final to this introductory chapter we introduce some of the wellknown topological descriptions of graphs. A graph is said to be (2cell) embedded in a surface M if it is “drawn” in M in such a way that edges intersect only at their common vertices and, moreover, the surface decomposes into open discs after removal of vertices and edges of the graph. These discs form the faces or regions of the embedded graph. A graph is said to be planar if it can be embedded in the plane or equivalently, on the sphere. We say that this embedding is a plane graph. By the genus of a graph G, we mean the minimum genus among all surfaces in which G can be embedded. So if G is planar, then the genus of G is zero. A graph is said to be outer planar if it has an embedding in the plane such that one face is incident to every vertex. It is clear that we have the following. Lemma 1.8.1. The genus of a subgraph or of a contraction of G is not greater than the genus of G. First, we recall the following wellknown results on the genus of graphs. Theorem 1.8.2 (Kuratowski, Wagner). For a finite graph G, the following are equivalent: (i) G is planar, (ii) G does not contain a subgraph that is a subdivision of K5 or K3,3 (Kuratowski), (iii) G does not contain K5 or K3,3 as a minor (Wagner). Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 1.8 On the genus of a graph  25 So basically these two graphs are the prototypes of nonplanar graphs. However, note that the graph in Figure 1.4 shows that both statements in Theorem 1.8.2 are qualitatively different. A similar result, that is much easier to prove holds for outer planar graphs. Theorem 1.8.3 (Chartrand, Harary). For a finite graph G, the following are equivalent: (i) G is outer planar, (ii) G does not contain a subgraph that is a subdivision of K4 or K2,3 , (iii) G does not contain K4 or K2,3 as a minor. For the next result, we have to recall that a surface is called orientable if it has a “consistently oriented triangulation.” This is the case for the sphere, the cylinder, and the torus, but not for the projective plane, the Möbius strip or the Klein bottle. In other words, a surface is nonorientable if it contains a Möbius strip. Figure 1.6: The above mentioned surfaces represented as polygons where appropriate arcs have to be by identified. Theorem 1.8.4 (Euler (1758), Poincaré (1895)). A finite graph that has n vertices and m edges and is 2cell embedded on an orientable surface M of genus g with f faces satisfies the Euler–Poincaré formula; i. e., n − m + f = 2 − 2g. This is specialized as follows. Theorem 1.8.5 (Euler’s formula). Every simple connected plane graph G with vertex set V, edge set E and face set F fulfills V − E + F = 2. In particular, G has at most 3V − 6 edges, i. e., E ≤ 3V − 6 and at most 2V − 4 edges if the embedding has no triangular faces, i. e., E ≤ 2V − 4. Note that this formula can be proved quite easily by induction on the number of edges E of G. Remark 1.8.6 (Geometric dual). The geometric dual G∗ of a plane graph G is the plane graph which has the faces of the original graph G as vertices; so it has a new vertex set, and two vertices in G∗ are adjacent if and only if the two faces in G have a common edge. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 26  1 Directed and undirected graphs This procedure can be generalizes to graphs embedded on a surface of genus greater than zero. Note that already in the plane different embeddings may be possible and, therefore, different geometric duals will exist. See Figure 1.7 for an illustration of dual graphs. Figure 1.7: Embeddings of the cube in the plane and on the torus and the respective dual graphs. The planar dual of the cube is the octahedron. Note that the geometric dual of a simple graph may have loops and multiple edges. Remark 1.8.7 (Platonic solids). In the following, the Platonic solids octahedron, dodecahedron, and icosahedron will appear, which together with the threedimensional cube Q3 and the tetrahedron (as graph isomorphic to K4 ) make up the five platonic graphs. From the values of d and d∗ , it is clear that the tetrahedron is selfdual, Q3 and the octahedron as well as the dodecahedron and the icosahedron are dual. These are the only plane graphs, which are, as we say, completely regular; this means that they are dregular (all vertices have degree d) and their geometric duals are d∗ regular (which is equivalent to saying that the regions of the plane representation are all bounded by d∗ edges). This can be proved with the Euler formula; see Theorem 1.8.4. For convenience, we will first give the combinatorial description of these five platonic graphs. Here again, F denotes the number of faces, d is the degree, d∗ is the number of edges around one region, which is equal to the degree of the geometric dual graph, always in a plane representation. d d∗ V  3 3 4 4 3 6 3 3 5 4 5 3 E F  6 4 Tetrahedron 12 8 Octahedron 8 12 20 30 12 30 6 12 20 Cube Dodecahedron Icosahedron Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 1.9 Comments: homomorphisms produce models  27 Remark 1.8.8 (Completely regular graphs on surfaces). Completely regular graphs can also be studied for surfaces other than the plane or sphere, e. g., for the torus and also for nonorientable surfaces of higher genus like the Möbius strip, the projective plane, the Klein bottle and so on. The interesting thing is that this topological question can be formulated algebraically, and this is a possible clue to the characterization of completely regular graphs on these surfaces. The starting point in all cases would be the Euler–Poincaré formula; this shows which graphs could be completely regular on the surface under consideration, but it does not give embeddings. The problem is completely solved for the torus. More information can be found [White 2001], and may be, in [Liu 1995]. Many interesting results can be found at www.omeyer.gmxhome.de/on_completely_regular.pdf. 1.9 Comments: homomorphisms produce models Ordinary homomorphisms are widely used. Halfstrong homomorphisms were called “full” in P. Hell [37], and in G. Sabidussi [80]; and they were called “partially adjacent” by S. Antohe and E. Olaru [1]. Surjective locally strong homomorphisms appeared in the book by A. Pultr and V. Trnkova [Pultr/Trnkova 1980]. As far as we know, the term “quasistrong” has not been used yet. Strong homomorphisms were first introduced by K. Culik in [15], under the name homomorphism. Metric homomorphisms can be found in the aforementioned paper by P. Hell. Egamorphisms are also called weak homomorphisms, e. g., in [Imrich/Klavžar 2000]. We would like to point out a more general phenomenon. Homomorphisms generate an image of a given object. This is the basis of the main principle of model building: we can view homomorphisms as the modeling tool and the homomorphic image as the model. When we use isomorphisms, all the information is retained. Since a model is usually thought of as a simplification, an isomorphic image is not really the kind of model one usually needs. So, in modeling, we want to suppress certain information about the original object, because in order to analyze the system it is helpful to first simplify the structure. To investigate different questions, we may wish to suppress different parts of the structure. Specializing this idea to graphs, strong homomorphisms reduce the number of points but maintain the structure in the sense that they reflect edges. Quasistrong, locally strong, and halfstrong homomorphisms reflect edges to a lesser and lesser extent in each step down to ordinary homomorphisms, which do not reflect edges at all. Now let us also look back on the homomorphism theorem. One important aspect is that it produces an epimono factorization for every homomorphism. This is exploited in the following way. We start with one endomorphism f of G, which by the induced congruence ϱf defines the epipart of the epimono factorization, the natural surjection G → G/ϱf . If we now consider all possible embeddings of this factor graph into Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 28  1 Directed and undirected graphs G, we obtain all possible endomorphisms with the induced congruence ϱf . This principle can be used to find all endomorphisms of an object G. This is done, e. g., when we prove that the set LEnd Pn for a path of length n is a monoid if and only if n = 3 or n + 1 is prime; see Section 9.3. Recall that the homomorphism theorem gives especially nice approaches to group and ring homomorphisms. In these two cases (categories), induced congruences are uniquely described by subobjects, namely normal subgroups in groups, also called normal divisors, and ideals in rings. These objects are much easier to handle than congruence relations; thus the investigation of homomorphisms in these categories is – to some extent – easier. For example, every endomorphism of a group A is determined by the factor group A/N, where N is a normal subgroup of A, and all possible embeddings of A/N into A. Nothing similar can be done for semigroups or in any of the graph categories (which will be introduced later). Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:25 AM 2 Graphs and matrices Matrices are very useful for describing and analyzing graphs. In this chapter, we shall present most of the common matrices for graphs and apply them to investigate various aspects of graph structures, such as isomorphic graphs, number of paths, or connectedness, and even endomorphisms and eigenvalues. All of this analysis is based on the socalled adjacency matrix. We also define another important matrix, the socalled incidence matrix, which we will use later when discussing cycle and cocycle spaces. 2.1 Adjacency matrix The definition of the adjacency matrix is the same for directed and undirected graphs, which may have loops and multiple edges. Definition 2.1.1. Let G = (V, E, p) where V = {x1 , . . . , xn } is a graph. The n × n matrix A(G) = (aij )i,j=1,...,n defined by aij := {e ∈ E  p(e) = (xi , xj )} is called the adjacency matrix of G. Example 2.1.2 (Adjacency matrices). We show the “divisor graph” of 6 and some multiple graph, along with their adjacency matrices. 0 0 A(G) = ( 0 0 1 0 0 0 1 0 0 0 0 A(G) = ( 1 0 2 0 1 0 0) 1 1 1 ) 1 0 1 2 3 6 Remark 2.1.3. There exists a bijective correspondence between the set of all graphs with finitely many edges and n vertices and the set of all n × n matrices over ℕ0 . It is clear that if the matrix A(G) is symmetric, then the graph G is symmetric (i. e., undirected) and vice versa. If G is simple, i. e., if it does not have multiple edges, then we can define A(G) by 1 aij := { 0 if (xi , xj ) ∈ E, otherwise. https://doi.org/10.1515/9783110617368002 Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:56 AM 30  2 Graphs and matrices Proposition 2.1.4. For all xi ∈ V with A(G) = (aij )i,j∈V=n , we have n indeg(xi ) = ∑ aji , column sum of column i; j=1 n outdeg(xi ) = ∑ aij , row sum of row i. j=1 In the symmetric case, one has n n j=1 j=1 deg(xi ) = ∑ aij = ∑ aji . Example 2.1.5 (Adjacency matrix and vertex degrees). This example illustrates that the row sums of A(G) are the outdegrees of the vertices and the column sums are the indegrees. v1 v2 v3 v4 v5 row sum v1 v2 v3 v4 v5 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 3 1 1 0 column sum 2 0 2 1 0 Isomorphic graphs and the adjacency matrix The next theorem gives a simple formal description of isomorphic graphs. It does not contribute in an essential way to a solution of the socalled isomorphism problem, which describes the problem of testing two graphs for being isomorphic. This turns out to be a difficult problem if one wants to construct, e. g., all (nonisomorphic) graphs of a given order. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:56 AM 2.1 Adjacency matrix  31 Theorem 2.1.6. Let G = (V, E) and G = (V , E ) be two simple graphs with n = V. The homomorphism f : G = (V, E) → G is an isomorphism if and only if there exists a matrix P such that A(G ) = P A(G) P −1 , where P is an n×n row permutation matrix which comes from the identity matrix In upon performing row permutations corresponding to f . Proof. For “⇒,” suppose G ≅ G , i. e., that G comes from G by permutation of the vertices. Then, in A(G), rows and columns are permuted correspondingly. Thus A(G ) = P A(G) P −1 , where P is the corresponding row permutation matrix. Left multiplication by P then permutes the rows and right multiplication by P −1 permutes the columns. For “⇐,” suppose A(G ) = P A(G) P −1 where P is a permutation matrix. Then there exists a mapping f : V → V with (xi , xj ) ∈ E, i. e., aij = 1 ⇔ af (i),f (j) = 1, i. e., (xf (i) , xf (j) ) ∈ E . Example 2.1.7 (Isomorphisms and adjacency matrices). It is apparent that the graphs G and G are isomorphic. The matrix P describes the permutation of vertex numbers which leads from A(G) to A(G ), i. e., A(G ) = P A(G) P −1 . 0 P = (0 1 1 0 0 0 1) , 0 P −1 = t P, 0 A(G) = (0 1 1 0 1 0 1) , 0 0 A(G ) = ( 1 1 1 0 0 0 1 ). 0 Components and the adjacency matrix Simple matrix techniques enable restructuring of the adjacency matrix of a graph according to its geometric structure. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:56 AM 32  2 Graphs and matrices Theorem 2.1.8. The graph G has s (weak) components G1 , . . . , Gs if and only if there exists a permutation matrix P with A(G1 ) 0 A(G2 ) P A(G) P −1 = ( .. 0 . ) A(Gs ) (block diagonal form). Proof. Weak connectedness defines an equivalence relation on V, so we get a decomposition of V into V1 , . . . , Vs . These vertex sets induce subgraphs G1 , . . . , Gs . Renumber G so that we first get all vertices in G1 , then all vertices in G2 , and so on. Note that there are no edges between different components. Theorem 2.1.9. The directed graph G has the strong components G1 , . . . , Gs if and only if there exists a permutation matrix P with A(Gi1 ) A(Gi2 ) P A(G) P −1 = ( 0 ∗ .. . ) A(Gis ) (Frobenius form, block triangular form). Proof. If we have the strong components, select Gi1 so that no arrows end in Gi1 . Then select Gi2 so that except for arrows starting from Gi1 , no arrows end in Gi2 . Note that there may be no arrows ending in Gi2 . Next, select Gi3 so that except for arrows starting from Gi1 or from Gi2 , no arrows end in Gi3 . Continue in this fashion. Observe that the numbering inside the diagonal blocks is arbitrary. The vertices of G have to be renumbered correspondingly. Example 2.1.10 (Frobenius form). 0 0 (1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0) 1 0 Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:56 AM 2.2 Incidence matrix  33 Adjacency list The adjacency list is a tool that is often used when graphs have to be represented in a computer, especially if the adjacency matrix has many zeros. Definition 2.1.11. The adjacency list A(x) of the vertex x ∈ G in the directed case consists of all successors of x, i. e., the elements of out(x) in arbitrary order. In the undirected case, it consists of all neighbors of x in arbitrary order. The adjacency list of the graph G is A(x1 ); A(x2 ); . . . for xi ∈ G. Example 2.1.12. The adjacency list of the graph from Example 2.1.10 is A(1) = 2, 4; A(2) = 3; A(3) = 1; A(4) = 5; A(5) = 4. If the graph G has multiple edges, then the outsets in its adjacency list may contain certain elements several times; in this case, we get socalled multisets. 2.2 Incidence matrix The incidence matrix relates vertices with edges, so multiple edges are possible but loops have to be excluded completely. It will turn out to be useful later when we consider cycle and cocycle spaces. Its close relation to linear algebra becomes clear in Theorem 2.2.3. We give its definition now, although most of this section relates to the adjacency matrix. Definition 2.2.1. Take G = (V, E, p), with V = {x1 , . . . , xn } and E = {e1 , . . . , em }. The n × m matrix B(G) over {−1, 0, 1} where 1 { { bij := {−1 { { 0 if xi = o(ej ) if xi = t(ej ) otherwise or, in the undirected case, bij := { 1 0 if xi ∈ ej otherwise is called the (vertex–edge) incidence matrix of G. Example 2.2.2 (Incidence matrix). Here, we present the incidence matrix of the divisor graph of 6; see Example 2.1.2. The matrix is the inner part of the table. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:56 AM 34  2 Graphs and matrices 1 2 3 6 a 0 1 0 −1 b 1 0 0 −1 c 0 0 1 −1 d 1 −1 0 0 e 1 0 −1 0 Theorem 2.2.3. Let G be a graph with n vertices and s (weak) components, and without loops. Then B(G) has rank n − s over ℤ2 in the undirected case, over ℝ otherwise. If s = 1 any n − 1 rows of B(G) are linearly independent. Proof. We number the vertices according to Theorem 2.1.8 (block diagonal form), and get B(G) also in block diagonal form. Its rank is the sum of the ranks of the blocks. So we consider s = 1. Addition of the row vectors gives the zero vector; therefore, the rows are linearly dependent, i. e., we have rank(B(G)) ≤ n − 1. If we delete one row, i. e., one vertex, then the sum of the remaining row vectors is obviously not zero. This holds also for any subset of rows. 2.3 Distances in graphs We now consider reachability and distances in graphs. For each graph, these can again be represented by matrices. Definition 2.3.1. Take G = (V, E) with V = {x1 , . . . , xn }. The n × n matrix R(G) with 1 rij := { 0 if there exists a nontrivial xi , xj path otherwise is called the reachability matrix of G. The reachability matrix also shows the strong components of a graph. Note that there may be a problem with the diagonal. In the definition, we have rii = 1 if and only if xi lies on a cycle. It is also possible to set all diagonal elements to 0 or 1. This choice can be made when the graph models a problem that allows us to decide whether a vertex can be reached from itself if it lies on a cycle. Definition 2.3.2. Take G = (V, E) and use the notation from Definition 1.1.5. The matrix D(G) with ∞ { { dij := { 0 { {d(xi , xj ) if F(xi , xj ) = 0 and i ≠ j if i = j otherwise is called the distance matrix of G. The (i, j)th element of the distance matrix is the distance from vertex xi to vertex xj , and is infinity if no path exists. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:56 AM 2.3 Distances in graphs  35 The adjacency matrix and paths A simple but surprising observation is that the powers of the adjacency matrix count the number of paths from one vertex to another. We start with an example. Example 2.3.3 (Powers of the adjacency matrix). 0 1 2 A(G) = ( 1 1 1 0 0 0 0 0 0 0 2 1 2 1 1 ) =( 0 0 0 0 0 1 1 1 0 0 0 0 1 1 ) = A(H) 1 1 Theorem 2.3.4. Take G = (V, E, p) and let a(r) be an entry of (A(G))r . Then a(r) is the ij ij number of xi , xj paths of length r in G. Proof. The result follows from the formula for the second power, n a(2) ij = ∑ aik akj , k=1 together with induction. This is the formula for the entries in the product of matrices. Remark 2.3.5. Note that forming the second power of an adjacency matrix can be generalized to taking the product of two adjacency matrices of the same size. The result can be interpreted as a graph containing as its edges the corresponding paths of length two. A similar method works for products of more than two matrices. In all cases, the resulting graph depends on the numbering. If, conversely, we start from a given graph G and construct the graph G2 of paths of length two, and then perform the corresponding steps with A(G), we automatically get the matrix product A(G)2 without having to know its definition from linear algebra. The adjacency matrix, the distance matrix, and circuits The following remark and two theorems are obvious. Remark 2.3.6. If V = n, then the length of a simple path in G is at most n. If the length equals n, then the path is a circuit. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:56 AM 36  2 Graphs and matrices Theorem 2.3.7. Let G be a graph with n vertices. The elements of the distance matrix D(G) can be obtained from the powers of A(G) as follows: (a) dii = 0 for all i; (b) dij is the smallest r ∈ ℕ with a(r) > 0 and r < n, if such an r exists; ij (c) dij = ∞ otherwise. For the elements of the reachability matrix R(G), we have: (a) rii = 0 for all i; (b) rij = 1 if and only if there exists r < n with a(r) > 0; ij (c) rij = 0 otherwise. Theorem 2.3.8. The graph G contains no circuits if and only if a(r) = 0 in (A(G))r for ii r ≤ n and for all i. 2.4 Endomorphisms and commuting graphs We briefly discuss two aspects of the adjacency matrix which have not gained much attention so far. Definition 2.4.1. Let f be a transformation of the finite set {1, . . . , n}, i. e., a mapping of the set into itself. Define the transformation matrix T(f ) = (tij )i,j∈{1,...,n} of f by setting its ith row ti to be ∑f (j)=i ej , where ej is the jth row of the identity matrix In and 0 is the row of zeros with n elements. This means that the ith row of T consists of the sum of rows ej such that j is mapped onto i by f . For the following, start by verifying some small examples. Exerceorem 2.4.2. (1) The transformation f is an endomorphism of the graph G with vertex set {x1 , . . . , xn } and adjacency matrix A(G) if and only if the (i, j)th entry of T(f )A(G)t T(f ) being nonzero implies that the (i, j)th entry of A(G) is nonzero. (2) The transformation f is an endomorphism of the graph G with vertex set {x1 , . . . , xn } and incidence matrix B(G) if and only if the jth column of T(f )B(G) having nonzero entries implies that there exists a column of B(G) which has the same nonzero entries in the same places. Definition 2.4.3. We say that G and H (with the same number of vertices) are commuting graphs if there exist labelings of the graphs such that their adjacency matrices commute, i. e., A(G)A(H) = A(H)A(G). Theorem 2.4.4. The graph G commutes with Kn if and only if G is a regular graph; it commutes with Kn,n if G is a regular subgraph of Kn,n . Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:56 AM 2.5 The characteristic polynomial and eigenvalues  37 Proof. See A. Heinze [36]. In addition, in this paper a construction of new commuting graphs starting with two pairs of commuting graphs is given. Question. Can you find a counterexample for the open “only if” part of the theorem? Construct some positive examples and some negative ones. 2.5 The characteristic polynomial and eigenvalues The possibility of representing graphs by their adjacency matrices naturally leads to the idea of applying the theory of eigenvalues to graphs. As the eigenvalues of a matrix are invariant with respect to permutation of columns and rows, we can expect that they are suitable for describing properties of graphs which are invariant under renaming of the vertices, i. e., invariant under automorphisms. Note that “eigenvalue” is a partial translation of the German word “Eigenwert.” In this section, we investigate how the eigenvalues of the adjacency matrix reflect the geometric and combinatorial properties of a graph. The definitions are valid for both directed and undirected graphs, but our results are focused mainly on undirected graphs and, correspondingly, symmetric matrices. Here, the theory is relatively simple and many interesting results have been obtained. For directed graphs and nonsymmetric matrices, things become much more complicated. The interested reader can consult monographs on this topic, such as [Cvetković et al. 1979]. We will return to this topic in Chapter 5 and in Chapter 8. Now let F be a field and G an undirected graph with V(G) = n. The following definition of the characteristic polynomial is for both directed and undirected graphs. Note that the coefficients can be determined by the entries of the matrix A(G) by using the determinant. This principle from linear algebra is adapted for graphs in Theorem 2.5.8 and thereafter. Definition 2.5.1. Let A(G) be the adjacency matrix of G. The polynomial of degree n in the indeterminate t over the field F given by chapo(G) = chapo(G; t) := det(tIn − A(G)) = t n + an−1 t n−1 + ⋅ ⋅ ⋅ + a1 t + a0 , is called the characteristic polynomial of the graph G. Here, det denotes the determinant and In denotes the nrow identity matrix. The zeros λ ∈ F of chapo(G) are called the eigenvalues of the graph G. We denote by m(λ) the multiplicity of λ. Remark 2.5.2. An element λ ∈ F is an eigenvalue of the graph G if and only if there exists a vector v ∈ F n , v ≠ 0, with A(G)v = λv, i. e., v is an eigenvector of A(G). We say v is an eigenvector of the graph G for λ. The characteristic polynomial chapo(G) is independent of the numbering of the vertices of G. The characteristic polynomial of a matrix is invariant even under arbitrary basis transformations. Brought to you by  Stockholm University Library Authenticated Download Date  10/13/19 4:56 AM 38  2 Graphs and matrices We now define the spectrum of a graph to be the sequence of its eigenvalues together with their multiplicities. It is quite surprising that for graphs that represent chemical CHmolecules there exists a correspondence between the spectrum of the graph and the chemical spectrum of the molecule; see, e. g., [Cvetković et al. 1979]. Definition 2.5.3. Let λi , i = 1, . . . , n, be the zeros of chapo(G) in natural order. We set λ(G) := λ1 < ⋅ ⋅ ⋅ < λp =: Λ(G). The spectrum of a graph G is the set of eigenvalues of A(G) together with their multiplicities: λ m(λ) Spec(G) = ( ⋅⋅⋅ ⋅⋅⋅ λi m(λi ) ⋅⋅⋅ ⋅⋅⋅ Λ ). m(Λ) The largest eigenvalue Λ is called the spectral radius of G. The next theorem follows immediately from Theorem 2.1.8 and the properties of the characteristic polynomial. Theorem 2.5.4. If G has the components G1 , . . . , Gr , then chapo(G) = chapo(G1 ) ⋅ ⋅ ⋅ chapo(Gr ). The set of all eigenvectors of an eigenvalue λ of a graph G together with the zerovector is called the eigenspace of λ, denoted by Eig(G, λi ). The following two theorems are not true for directed graphs, i. e., for nonsymmetric matrices. For the proofs, we need several results from linear algebra. Theorem 2.5.5. Over F = ℝ, all zeros of the characteristic polynomial chapo(G) of the undirected graph G are irrational or integer. Moreover, A(G) is diagonalizable, i. e., dim(Eig(G, λi )) = m(λi ), and has an orthonormal basis of eigenvectors of A(G). Proof. As G is undirected, A(G) is symmetric (cf. Remark 2.1.3). Symmetric matrices have only real eigenvalues (since they are selfadjoint with respect to the standard scalar product over ℝ; i. e., ⟨ v, Av ⟩ = ⟨ Av, v ⟩ for all v, w ∈ ℝn .) So A(G) is a real symmetric matrix, and this is equivalent to the existence of an orthonormal basis of eigenvectors of A(G). Finally, we prove that λi ∈ ℚ implies λi ∈ ℤ. Suppose that chapo(