Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-25T06:10:37.507Z Has data issue: false hasContentIssue false
  • English
  • Français

A Classification of Reflexive Graphs: The use of “Holes”

Published online by Cambridge University Press:  20 November 2018

El Moustafa Jawhari ,
Maurice Pouzet  and
Ivan Rival
El Moustafa Jawhari
Affiliation:
Université Claude-Bernard, Villeurbanne, France
Maurice Pouzet
Affiliation:
University of Ottawa, Ottawa, Ontario
Ivan Rival
Affiliation:
University of Ottawa, Ottawa, Ontario
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.

The purpose of this article is to develop aspects of a classification theory for reflexive graphs. A first important step was already taken in [2]; throughout we follow, at least the spirit, of the classification theory for ordered sets initiated in [1].

For a graph G let V(G) denote its vertex set and E(G) ⊆ V(G) × V(G) its edge set. A graph K is a subgraph of G if V(K) ⊆ V(G) and for a, b ∊ V(K), (a, b) ∊ E(K) just if (a, b) ∊ E(G). The subgraph K of G is a retract of G, and we write K ◅ G, if there is an edge-preserving map g of V(G) to V(K) satisfying g(v) = v for each v ∊ V(K); g is called a retraction. A reflexive graph is an undirected graph with a loop at every vertex. The reason for a loop at a vertex is that an edge-preserving map can send the two vertices of an adjacent pair to it. The concept is illustrated in Figure 1. From here on, though, we shall for convenience suppress the illustration of the loops in the figures of reflexive graphs.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 38 , Issue 6 , 01 December 1986 , pp. 1299 - 1328
Copyright
Copyright © Canadian Mathematical Society 1986

References

1. Duffus, D. and Rival, I., A structure theory for ordered sets, Discrete Math. 35 (1981), 53–118.Google Scholar
2. Nowakowski, R. J. and Rival, I., A fixed edge theorem for graphs with loops, J. Graph Theory 3 (1979), 339–350.Google Scholar
3. Nowakowski, R. J. and Rival, I., The smallest graph variety containing all paths, Discrete Math. 43 (1983), 223–234.Google Scholar