Graphs and their associated inverse semigroups |
| |
Authors: | Tien Chih Demitri Plessas |
| |
Institution: | 1. Montana State University-Billings, 1500 University Drive, Billings, MT 59101, USA;2. Northeastern State University, 611 N. Grand Ave, Tahlequah, OK 74464, USA |
| |
Abstract: | Directed graphs have long been used to gain an understanding of the structure of semigroups, and recently the structure of directed graph semigroups has been investigated resulting in a characterization theorem and an analog of Frucht’s Theorem. We investigate two inverse semigroups defined over undirected graphs constructed from the notions of subgraph and vertex set induced subgraph. We characterize the structure of the semilattice of idempotents and lattice of ideals of these inverse semigroups. We prove a characterization theorem that states that every graph has a unique associated inverse semigroup up to isomorphism allowing for an algebraic restatement of the Edge Reconstruction Conjecture. |
| |
Keywords: | Inverse semigroup Graph automorphism Graph symmetry Semigroup ideal Algebraic graph theory |
本文献已被 ScienceDirect 等数据库收录! |
|