Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-26T00:52:57.832Z Has data issue: false hasContentIssue false
  • English
  • Français

Groups and Monoids of Regular Graphs (And of Graphs with Bounded Degrees)

Published online by Cambridge University Press:  20 November 2018

Pavol Hell  and
Jaroslav Nešetřil
Pavol Hell
Affiliation:
Université de Montréal, Montréal, Québec
Jaroslav Nešetřil
Affiliation:
Charles University, Prague, Czechoslovakia
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A graph X is a set V(X) (the vertices of X) with a system E(X) of 2-element subsets of V(X) (the edges of X). Let X, Y be graphs and f : V(X) → V(Y) a mapping; then/ is called a homomorphism of X into F if [f(x),f(y)] ∈ E(Y) whenever [x,y] ∈ E(X). Endomorphisms, isomorphisms and automorphisms are defined in the usual manner.

Much work has been done on the subject of representing groups as groups of automorphisms of graphs (i.e., given a group G, to find a graph X such that the group of automorphisms of X is isomorphic to G). Recently, this was related to category theory, the main question being as to whether every monoid (i.e., semigroup with 1) can be represented as the monoid of endomorphisms of some graph in a given category of graphs.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 25 , Issue 2 , April 1973 , pp. 239 - 251
Copyright
Copyright © Canadian Mathematical Society 1973

References

1. Frucht, R., Graphs of degree three with a given abstract group, Can. J. Math. 1 (1949), 365–378.Google Scholar
2. Hedrlin, Z. and Lambek, J., How comprehensive is the category of semigroups? J. Algebra 11 (1969), 195–212.Google Scholar
3. Hedrlin, Z. and Mendelsohn, E., The category of graphs with a given subgraph - with applications to topology and algebra, Can. J. Math. 21 (1969), 1506–1517.Google Scholar
4. Hedrlin, Z. and Pultr, A., Symmetric relations ﹛undirected graphs) with given semigroups, Monatsh.Math. 69 (1965), 318–322.Google Scholar
5. Hedrlin, Z. and Pultr, A., On rigid undirected graphs, Can. J. Math. 18 (1966), 1237–1242.Google Scholar
6. Hell, P. and Nešetřil, J., Graphs and k-societies, Can. Math. Bull. 13 (1970), 375–381.Google Scholar
7. Hell, P., Full embeddings into some categories of graphs, Algebra Universalis 2 (1972), 129–141.Google Scholar
7. Hell, P., Full embeddings into some categories of graphs (submitted to Algebra Universalis).Google Scholar
8. Kurosh, A. G., The theory of groups (Chelsea, New York, 1960).Google Scholar
9. Mendelsohn, E., Šip-products and graphs with given semigroups(to appear).Google Scholar
10. Sabidussi, G., Graphs with given group and given graph-theoretical properties, Can. J. Math. 9 (1957), 515–525.Google Scholar
11. Vopnka, P., Hedrlin, Z. and Pultr, A., A rigid relation exists on any set, Comment. Math. Univ. Carolinae 6 (1965), 149–155.Google Scholar