CONVEXITY IN GRAPHS: MATHEMATICAL PRELIMINARIES TO A THEORY OF GRAPH GRAMMARS,
Abstract
A natural concept of convexity for directed graphs is introduced, and properties of the lattice of convex subgraphs of a graph are studied. The extent to which this lattice determines the graph is established, and conditions for a lattice to be a convex subgraph lattice are investigated. The concept of a lower semi-homomorphism is defined for lattices; it is shown that such mappings preserve basic properties of convex subgraph lattices, and that on such lattices, they are uniquely determined by their kernels. Graph homomorphisms which preserve convexity are also studied, with emphasis on their relationship to lower semi-homomorphisms of the convex subgraph lattice. Homomorphisms which 'contract' subgraphs (which are analogous to the rewriting rules of context-sensitive phrase structure grammars) are briefly considered. Finally, a concept of local convexity for directed graphs is introduced. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1968
- Accession Number
- AD0673420
Entities
People
- John L. Pfaltz
Organizations
- University of Maryland