Definition
As defined, e.g., by Goldberg & Karzanov (1996), a skew-symmetric graph G is a directed graph, together with a function σ mapping vertices of G to other vertices of G, satisfying the following properties:
- For every vertex v, σ(v) ≠ v,
- For every vertex v, σ(σ(v)) = v,
- For every edge (u,v), (σ(v),σ(u)) must also be an edge.
One may use the third property to extend σ to an orientation-reversing function on the edges of G.
The transpose graph of G is the graph formed by reversing every edge of G, and σ defines a graph isomorphism from G to its transpose. However, in a skew-symmetric graph, it is additionally required that the isomorphism pair each vertex with a different vertex, rather than allowing a vertex to be mapped to itself by the isomorphism or to group more than two vertices in a cycle of isomorphism.
A path or cycle in a skew-symmetric graph is said to be regular if, for each vertex v of the path or cycle, the corresponding vertex σ(v) is not part of the path or cycle.
Read more about this topic: Skew-symmetric Graph
Famous quotes containing the word definition:
“The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
—Ralph Waldo Emerson (1803–1882)
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)
“Perhaps the best definition of progress would be the continuing efforts of men and women to narrow the gap between the convenience of the powers that be and the unwritten charter.”
—Nadine Gordimer (b. 1923)