Permutation graph

Permutation graph

In areas of mathematics influenced by graph theory, a permutation graph is the intersection graph of a family of line segments that connect two parallel lines in the Euclidean plane. Equivalently, given a permutation (σ1,σ2,σ3,...) of the numbers 1,2,3,..."n", a permutation graph has a vertex for each number 1,2,3,..."n" and an edge between any two numbers that are in reversed order in the permutation.

Definition and characterization

* A graph "G" is a permutation graph if and only if "G" is a circle graph that admits an "equator," i.e., an additional chord that intersects every other chord. [.

External links

* cite web
url = http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_23.html
title = permutation graph
work = [http://wwwteo.informatik.uni-rostock.de/isgci/index.html Information System on Graph Class Inclusions]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Graph automorphism — In graph theoretical mathematics, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge vertex connectivity.Formally, an automorphism of a graph G = ( V , E ) is a permutation sigma;… …   Wikipedia

  • Comparability graph — In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable… …   Wikipedia

  • List of permutation topics — This is a list of topics on mathematical permutations.*Alternating group *Alternating permutation *Bijection *Circular shift *Combination *Cycle index *Cycle notation *Cyclic order *Cyclic permutation *Derangement *Even and odd permutations… …   Wikipedia

  • Circle graph — For the chart, see Pie chart. A circle with five chords and the corresponding circle graph. In graph theory, a circle graph is the intersection graph of a set of chords of a circle. That is, it is an undirected graph whose vertices can be… …   Wikipedia

  • Split graph — In graph theory, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer in two papers in 1977, and independently introduced by Tyshkevich and… …   Wikipedia

  • Casio Graph 35+ — Graph 35+ Mémoire vive 64 Ko Dimensions de l écran 128 × 64 pixels Connectivité …   Wikipédia en Français

  • Uniquely colorable graph — In graph theory, a uniquely colorable graph is a k chromatic graph that has only one possible (proper) k coloring up to permutation of the colors. Example 1 . A minimal imperfect graph is a graph in which every subgraph is perfect. The deletion… …   Wikipedia

  • Bogen (Graph) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • K-regulärer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Kubischer Graph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

Share the article and excerpts

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