Graph property
From Wikipedia, the free encyclopedia
In graph theory a graph property is any "inherently graph-theoretical" property of graphs (formal definitions follow), distinguished from properties of graphs described in terms of various graph representations: graph drawings, data structures for graphs, graph labelings, etc.
Contents |
[edit] Definitions
While graph drawing and graph representation are valid topics in graph theory, in order to focus on "inherently graph-theoretical" properties of graphs, a graph property is defined to be a property preserved under all possible isomorphisms of a graph.
Graphs with the same graph property naturally define a certain family of graphs: the ones that have the specified property. Therefore, to avoid the ambiguity of the English word "property" and a feeling of circular logic in the definition, a graph property is defined as a nonempty proper subset of the set of graphs closed under the graph isomorphism.[1]
Informally, the term "graph invariant" is used for properties expressed quantitatively, while "property" usually refers to descriptive characterizations of graphs. For example, the statement "graph does not have vertices of degree 1" is a "property" while "the number of vertices of degree 1 in a graph" is an "invariant".
Formally, a graph invariant is an indexed family of graph properties.
For example "the number of vertices" is an indexed family of graph properties "a graph has M edges, M = 0, 1, 2....". In this case the family of properties is indexed by the set of nonnegative integer numbers. A more complex example of graph invariant is the degree sequence of a graph: the family of properties is indexed by the set of all ordered sequences of nonnegative integers.
[edit] Graph invariants
- number of vertices
- number of edges
- vertex chromatic number - minimum number of colors needed to color all vertices so that adjacent vertices have a different color
- edge chromatic number - minimum number of colors needed to color all edges so that adjacent edges have a different color
- edge covering number - minimal number of edges needed to cover all vertices
- vertex covering number - minimal number of vertices needed to cover all edges
- degree sequence
- graph genus
[edit] Types of graph properties
- Hereditary property (also called monotone property): a property closed under the operation of taking subgraphs
- Additive graph property: a property closed under the graph union [2] For example, being an acyclic graph is an additive property.
[edit] See also
[edit] References
- ^ Peter Mihok (1999) "Reducible properties and uniquely partitionable graphs" in: Ronald L. Graham, "Contemporary Trends in Discrete Mathematics", DIMASC Series in Discrete Mathematics and Computer Science, vol. 49, ISBN 0821809636 p. 213
- ^ Peter Mihok (1999) "Reducible properties and uniquely partitionable graphs" in: Ronald L. Graham, "Contemporary Trends in Discrete Mathematics", DIMASC Series in Discrete Mathematics and Computer Science, vol. 49, ISBN 0821809636 p. 214
