Silhouette edge

2012-10-23T01:09:01Z

63.226.32.16: /* Similar Technique */

[[File:6n-graf.svg|thumb|250px|An example graph, with the properties of being [[planar graph|planar]] and being [[connectivity (graph theory)|connected]], and with order 6, size 7, [[Distance (graph theory)|diameter]] 3, [[girth (graph theory)|girth]] 3, [[connectivity (graph theory)|vertex connectivity]] 1, and [[degree sequence]] <3, 3, 3, 2, 2, 1>]]
In [[graph theory]], a '''graph property''' or '''graph invariant''' is a property of [[graph (mathematics)|graphs]] that depends only on the abstract structure, not on graph representations such as particular [[graph labeling|labellings]] or [[graph drawing|drawings]] of the graph.

==Definitions==
While graph drawing and graph representation are valid topics in graph theory, in order to focus only on the abstract structure of graphs, a '''graph property''' is defined to be a property preserved under all possible [[graph isomorphism|isomorphism]]s of a graph. In other words, it is a property of the graph itself, not of a specific drawing or representation of the graph.

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".

More formally, a graph property is a class of graphs, i.e. a function{{dubious|date=February 2014}} from graphs to {T,F}, and a graph invariant is a function from graphs to some other set,<ref>R. Diestel, ''Graph Theory'', 3rd edition, Heidelberg:Springer-Verlag, 2005. [http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/]</ref> such as to the natural numbers (for scalar invariants),<ref>[http://arxiv.org/abs/0902.3616v1 S. Kreutzer, Algorithmic Meta-Theorems, 2008]</ref> or to (possibly ordered) sequences of natural numbers (for properties like the [[degree sequence]]), or to a polynomial ring,<ref>I. Averbouch, B. Godlin, and J.A. Makowsky, An extension of the bivariate chromatic polynomial, 2008. [http://www.cs.technion.ac.il/~admlogic/TR/2008/agm08-preprint.pdf]</ref> such that isomorphic graphs have the same value.

A graph property is often called [[hereditary property|hereditary]] if it also holds for (is "inherited" by) its [[induced subgraph]]s.<ref>{{Citation | last = Alon|first = Noga|author-link = Noga Alon|last2 = Shapira| first2 = Asaf|title = Every monotone graph property is testable|journal = SIAM Journal on Computing|volume = 38|issue = 2|year = 2008|pages = 505–522|doi = 10.1137/050633445|url = http://www.math.tau.ac.il/~nogaa/PDFS/monotone1.pdf}}</ref> A property is called '''additive''' if it is closed under [[graph union|disjoint union]].<ref>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 0-8218-0963-6 [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]</ref> The property of being [[planar graph|planar]] is both hereditary and additive, for example, since a subgraph of a planar graph must be planar, and a disjoint union of two planar graphs must also be planar. The property of being [[connectivity (graph theory)|connected]] is neither, since a subgraph of a connected graph need not be connected, and a disjoint union of two connected graphs cannot be connected.

A graph property is sometimes called '''monotone increasing''' (or respectively '''monotone decreasing''') if it is kept under the addition (respectively, the deletion) of edges. For example, the property of being [[connectivity (graph theory)|connected]] is monotone increasing, whereas the property of being 3-colorable is monotone decreasing.<ref>{{citation
| last = Friedgut | first = Ehud
| doi = 10.1002/rsa.20042
| issue = 1-2
| journal = Random Structures & Algorithms
| mr = 2116574
| pages = 37–51
| title = Hunting for sharp thresholds
| volume = 26
| year = 2005}}.</ref>

==Graph invariants and graph isomorphism==

Easily computable graph invariants are instrumental for fast recognition of [[graph isomorphism]], or rather non-isomorphism, since for any invariant at all, two graphs with different values cannot (by definition) be isomorphic. Two graphs with the same invariants may or may not be isomorphic, however.

A graph invariant ''I''(''G'') is called '''complete''' if the identity of the invariants ''I''(''G'') and ''I''(''H'') implies the isomorphism of the graphs ''G'' and ''H''. Finding such an invariant would imply an easy solution to the challenging [[graph isomorphism problem]]. However, even polynomial-valued invariants such as the [[chromatic polynomial]] are not usually complete. The [[claw (graph theory)|claw graph]] and the [[path graph]] on 4 vertices both have the same chromatic polynomial, for example.

==Some examples of graph properties==

* [[Connected space|connected]]
* [[Cyclic graph|cyclic]]
* [[Acyclic graph|acyclic]]
* [[2-colorable]]
* [[3-colorable]]
* [[n-colorable]]
* [[bipartite graph|bipartite]] - same as 2-coloring
* [[Planar graph|planar]]

== Some graph invariants ==
=== Scalars ===
* [[order (graph theory)|order]] - the number of vertices
* [[size (graph theory)|size]] - the number of edges
* [[Distance (graph theory)|diameter]] - the longest of the shortest path lengths between pairs of vertices
* [[girth (graph theory)|girth]] - the length of the shortest cycle contained in the graph
* [[clustering coefficient]]
* [[betweenness centrality]]
* [[Connectivity (graph theory)|vertex connectivity]] - the smallest number of vertices whose removal disconnects the graph
* [[edge connectivity]] - the smallest number of edges whose removal disconnects the graph
* [[independence number]] - the largest size of an independent set of vertices
* [[clique number]] - the largest order of a complete subgraph
* [[algebraic connectivity]]
* [[vertex chromatic number]] - the minimum number of colors needed to color all vertices so that [[Adjacent (graph theory)|adjacent]] vertices have a different color
* [[edge chromatic number]] - the minimum number of colors needed to color all edges so that adjacent edges have a different color
* [[vertex covering number]] - the minimal number of vertices needed to cover all edges
* [[edge covering number]] - the minimal number of edges needed to cover all vertices
* [[Cheeger constant (graph theory)|isoperimetric number]]
* [[arboricity]]
* [[graph genus]]
* [[Book embedding|pagenumber]]
* [[Hosoya index]]
* [[Wiener index]]
* [[Estrada index]]
* [[Colin de Verdière graph invariant]]
* [[boxicity]]
* [[Strength of a graph (graph theory)|strength]]

=== Sequences and polynomials ===
* [[degree sequence]]
* [[graph spectrum]]
* [[characteristic polynomial]] of the [[adjacency matrix]]
* [[chromatic polynomial]] – the number of <math>k</math>-colorings viewed as a function of <math>k</math>
* [[Tutte polynomial]] – a bivariate function that encodes much of the graph’s connectivity

==See also==

*[[Topological index]]
*[[Graph canonization]]

== References ==
{{Reflist}}

{{DEFAULTSORT:Graph Property}}
[[Category:Graph invariants|*]]
[[Category:Graph theory]]

formulasearchengine - User contributions [en]

Silhouette edge