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 man who knows governments most completely is he who troubles himself least about a definition which shall give their essence. Enjoying an intimate acquaintance with all their particularities in turn, he would naturally regard an abstract conception in which these were unified as a thing more misleading than enlightening.”
—William James (1842–1910)
“Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
—The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)
“... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
—Adrienne Rich (b. 1929)