# OpenMath Content Dictionary: graph2

Canonical URL:
http://www.dse.nl/~postma/graph1.ocd
CD Base:
http://www.openmath.org/cd
CD File:
graph2.ocd
CD as XML Encoded OpenMath:
graph2.omcd
Defines:
automorphism_group, is_automorphism, is_endomorphism, is_homomorphism, is_isomorphism, isomorphic
Date:
2004-06-27
Version:
0 (Revision 12)
Review Date:
2006-06-01
Status:
experimental

This CD defines symbols for handling directed and undirected graphs. Authored by Arjeh---to be merged with version of Erik Postma.

## automorphism_group

Description:

This symbol is a unary function whose argument is an undirected graph. When applied to an undirected graph G, it represents the automorphism group of G. The resulting automorphism group is represented as a permutation group on the vertices of the graph G.

Example:
The automorphism group of a path of length 2 (on three nodes) is the permutation group of order two interchanging the two end nodes.
$\mathrm{automorphism_group}\left(\mathrm{graph}\left(\left\{1,2,3\right\},\left\{\left\{1,2\right\},\left\{2,3\right\}\right\}\right)\right)=\mathrm{group}\left(\mathrm{right_compose},\mathrm{permutation}\left(\mathrm{cycle}\left(1,3\right)\right)\right)$
Signatures:
sts

 [Next: is_homomorphism] [Last: isomorphic] [Top]

## is_homomorphism

Description:

This symbol is a boolean function with three arguments. The first and arguments are graphs M, N, the third is a map f from the vertex set of M to the vertex set of N. When applied to M, N, and f, it denotes that f is a graph homomorphism from M to N.

Commented Mathematical property (CMP):
If is_homomorphism(M,N,f) then, for each pair of vertices x, y of M, we have if {x,y} is an edge of M, then {f(x), f(y)} is an edge of N.
Formal Mathematical property (FMP):
$\mathrm{is_homomorphism}\left(M,N,f\right)⇒\forall x,y.x\in \mathrm{vertexset}\left(M\right)\wedge y\in \mathrm{vertexset}\left(M\right)\wedge \left\{x,y\right\}\in \mathrm{edgeset}\left(M\right)⇒\left\{f\left(x\right),f\left(y\right)\right\}\in \mathrm{edgeset}\left(N\right)$
Signatures:
sts

 [Next: is_isomorphism] [Previous: automorphism_group] [Top]

## is_isomorphism

Description:

This symbol is a boolean function with three arguments. The first and arguments are graphs M, N, the third is a map f from the element set of M to the element set of N. When applied to M, N, and f, it denotes that f is a graph isomorphism from M to N. This means that f is a homomorphism from M to N, that f is bijective, and that its inverse is a homomorphism from N to M.

Example:
$\mathrm{is_isomorphism}\left(M,N,f\right)$
Signatures:
sts

 [Next: is_endomorphism] [Previous: is_homomorphism] [Top]

## is_endomorphism

Description:

This symbol is a boolean function with two arguments. The first argument is a graph M, the second is a map f from the element set of M to the element set of M. When applied to M and f, it denotes that f is a graph endomorphism from M to M.

Commented Mathematical property (CMP):
If is_endomorphism(M,f) then is_homomorphism(M,M,f)
Formal Mathematical property (FMP):
$\mathrm{is_endomorphism}\left(M,f\right)⇒\mathrm{is_homomorphism}\left(M,M,f\right)$
Example:
$\mathrm{is_endomorphism}\left(M,f\right)$
Signatures:
sts

 [Next: is_automorphism] [Previous: is_isomorphism] [Top]

## is_automorphism

Description:

This symbol is a boolean function with two arguments. The first is a graph M, the second is a map f from the element set of M to the element set of M. When applied to M and f, it denotes a graph automorphism f of M.

Commented Mathematical property (CMP):
If is_automorphism(M,f) then is_isomorphism(M,M,f)
Formal Mathematical property (FMP):
$\mathrm{is_automorphism}\left(M,f\right)⇒\mathrm{is_isomorphism}\left(M,M,f\right)$
Example:
$\mathrm{is_automorphism}\left(M,f\right)$
Signatures:
sts

 [Next: isomorphic] [Previous: is_endomorphism] [Top]

## isomorphic

Description:

This symbol is a Boolean function with n arguments, n at least 2, which are graphs. When applied to M_1, ..., M_n, it denotes the fact that there is an isomorphism from each M_i to each M_j.

Example:
$\mathrm{isomorphic}\left(M,N\right)$
Signatures:
sts

 [First: automorphism_group] [Previous: is_automorphism] [Top]