img

Notice détaillée

Axioms for generalized graphs, illustrated by a Cantor-Bernstein proposition

Article Ecrit par: Engelfriet, J. ; Gelsema, T. ;

Résumé: The notion of a graph type T is introduced by a collection of axioms. A graph of type T (or T-graph) is defined as a set of edges, of which the structure is specified by T. From this, general notions of subgraph and isomorphism of T-graphs are derived. A Cantor-Bernstein (CB) result for T-graphs is presented as an illustration of a general proof for different types of graphs. By definition, a relation R on T-graphs satisfies the CB property if A R B and B R A imply that A and B are isomorphic. In general, the relation 'isomorphic to a subgraph' does not satisfy the CB property. However, requiring the subgraph to be disconnected from the remainder of the graph, a relation that satisfies the CB property is obtained. A similar result is shown for T-graphs with multiple edges.


Langue: Anglais