Graph property

Graph property

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.

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. [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 [http://books.google.com/books?id=aE_-qdthsWcC&pg=PA217&lpg=PA217&dq=%22induced+hereditary+property%22&source=web&ots=Q_sGAk5c73&sig=7pQOu-zaI8tSABMncyewDU9RyJM#PPA213,M1 p. 213] ]

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.

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

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 [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 [http://books.google.com/books?id=aE_-qdthsWcC&pg=PA217&lpg=PA217&dq=%22induced+hereditary+property%22&source=web&ots=Q_sGAk5c73&sig=7pQOu-zaI8tSABMncyewDU9RyJM#PPA213,M1 p. 214] ] For example, being an acyclic graph is an additive property.

ee also

*Topological index

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • Graph enumeration — is a subject of graph theory that deals with the problems of the following type: find how many non isomorphic graphs have a given property.See Pólya enumeration theorem for examples.References* cite book author = Frank Harary and Edgar M. Palmer… …   Wikipedia

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Graph continuous — In mathematics, and in particular the study of game theory, a function is graph continuous if it exhibits the following properties. The concept was originally defined by Partha Dasgupta and Eric Maskin in 1986 and is a version of continuity that… …   Wikipedia

  • Property B — In mathematics, Property B is a certain set theoretic property. Formally, given a finite set X , a collection C of subsets of X , all of size n , has Property B iff we can partition X into two disjoint subsets Y and Z such that every set in C… …   Wikipedia

  • Hereditary property — In mathematics, a hereditary property is a property of an object, that inherits to all its subobjects, where the term subobject depends on the context. These properties are particularly considered in topology and graph theory. Contents 1 In… …   Wikipedia

  • Control flow graph — Simplified control flowgraphs[1] A control flow graph (CFG) in computer science is a representation, using graph notation, of all paths that might be traversed through a program during its execution …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Connectivity (graph theory) — In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) which need to be removed to disconnect the remaining nodes from each other[1]. It is… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”