𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On graphs with a given endomorphism monoid

✍ Scribed by Václav Koubek; Vojtěch Rödl; Benjamin Shemmer

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
241 KB
Volume
62
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Hedrlín and Pultr proved that for any monoid M there exists a graph G with endomorphism monoid isomorphic to M. In this paper we give a construction G(M) for a graph with prescribed endomorphism monoid M. Using this construction we derive bounds on the minimum number of vertices and edges required to produce a graph with a given endomorphism monoid for various classes of finite monoids. For example we show that for every monoid M, |M|=m there is a graph G with End(G)≃M and |E(G)|≤(1 + 0(1))m^2^. This is, up to a factor of 1/2, best possible since there are monoids requiring a graph with \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*} && \frac{m^{2}}{2}(1 -0(1)) \end{eqnarray*}\end{document} edges.

We state bounds for the class of all monoids as well as for certain subclasses—groups, k‐cancellative monoids, commutative 3‐nilpotent monoids, rectangular groups and completely simple monoids. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 241–262, 2009

📜 SIMILAR VOLUMES

On smallest regular graphs with a given
On smallest regular graphs with a given isopart
✍ John Frederick Fink 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 408 KB 👁 1 views

## Abstract For a nonempty graph, G, we define p(G) and r(G) to be respectively the minimum order and minimum degree of regularity among all connected regular graphs __H__ having a nontrivial decomposition into subgraphs isomorphic to G. By f(G), we denote the least integer t for which there is a c

On graphs containing a given graph as ce
On graphs containing a given graph as center
✍ Fred Buckley; Zevi Miller; Peter J. Slater 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 367 KB 👁 1 views

## Abstract We examine the problem of embedding a graph __H__ as the center of a supergraph __G__, and we consider what properties one can restrict __G__ to have. Letting __A(H)__ denote the smallest difference ∣__V(G)__∣ ‐ ∣__V(H)__∣ over graphs __G__ having center isomorphic to __H__ it is demons

On connectivity in graphs with given cli
On connectivity in graphs with given clique number
✍ Angelika Hellwig; Lutz Volkmann 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 82 KB 👁 1 views

## Abstract We consider finite, undirected, and simple graphs __G__ of order __n__(__G__) and minimum degree δ(__G__). The connectivity κ(__G__) for a connected graph __G__ is defined as the minimum cardinality over all vertex‐cuts. If κ(__G__) < δ(__G__), then Topp and Volkmann 7 showed in 1993 f

On local connectivity of graphs with giv
On local connectivity of graphs with given clique number
✍ Andreas Holtkamp; Lutz Volkmann 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB

## Abstract For a vertex __v__ of a graph __G__, we denote by __d__(__v__) the __degree__ of __v__. The __local connectivity__ κ(__u, v__) of two vertices __u__ and __v__ in a graph __G__ is the maximum number of internally disjoint __u__ –__v__ paths in __G__, and the __connectivity__ of __G__ is

Covering a graph with cycles passing thr
Covering a graph with cycles passing through given edges
✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 91 KB 👁 2 views

We propose a conjecture: for each integer k ≥ 2, there exists N (k) such that if G is a graph of order n ≥ N (k) and d(x) + d(y) ≥ n + 2k -2 for each pair of nonadjacent vertices x and y of G, then for any k independent edges e 1 , . . . , e k of G, there exist If this conjecture is true, the condi