Lexicographic product of graphs

Lexicographic product of graphs

In graph theory, the lexicographic product or graph composition "G" ∙ "H" of graphs "G" and "H" is a graph such that
* the vertex set of "G" ∙ "H" is the cartesian product "V(G)" imes "V(H)"; and
* any two vertices "(u,u')" and "(v,v')" are adjacent in "G" ∙ "H" if and only if either "u" is adjacent with "v", or "u" = "v" and "u' " is adjacent with "v' ".

If the edge relations of the two graphs are order relations, then the edge relation of their lexicographic product is the corresponding lexicographic order.

The lexicographic product was first studied by Felix Hausdorff (1914). As Feigenbaum and Schäffer (1986) showed, the problem of recognizing whether a graph is a lexicographic product is equivalent in complexity to the graph isomorphism problem.

Properties

The lexicographic product is in general noncommutative: "G" ∙ "H" ≠ "H" ∙ "G". However it satisfies a distributive law with respect to disjoint union: ("A" + "B") ∙ "C" = "A" ∙ "C" + "B" ∙ "C".In addition it satisfies an identity with respect to complementation: C("G" ∙ "H") = C("G") ∙ C("H").

The independence number of a lexicographic product may be easily calculated from that of its factors::α("G" ∙ "H") = α("G")α("H")(Geller and Stahl 1975).

The chromatic number of a lexigraphic product is as well multiplicative:

omega(Gcdot H) = omega(G)cdot omega(H)

Application

In 1972 Abbott gave a curios super-quadratic constructive lower bound for the Ramsey numbers: Suppose you have a "n"-vertex graph "G" with independence number and clique number smaller than "n10" (or any other power) The same relations hold for the graph "G" ∙ "G" or any larger powers of "G". This gives a infinite sequence of explicit Ramsey graphs provided that we have the graph to start from. By checking all the graphs on k^10 vertices (k large enough), one of them certainly will be "k"-Ramsey.

References

*cite journal
author = Feigenbaum, J.; Schäffer, A. A.
year = 1986
title = Recognizing composite graphs is equivalent to testing graph isomorphism
journal = SIAM J. Comput.
volume = 15
pages = 619–627
id = MathSciNet | id = 0837609
doi = 10.1137/0215045

*cite journal
author = Geller, D.; Stahl, S.
title = The chromatic number and other functions of the lexicographic product
journal = Journal of Combinatorial Theory, Series B
volume = 19
year = 1975
pages = 87–95
id = MathSciNet | id = 0392645
doi = 10.1016/0095-8956(75)90076-3

*cite book
author = Hausdorff, F.
authorlink = Felix Hausdorff
title = Grundzüge der Mengenlehre
year = 1914
location = Leipzig

*cite book
author = Imrich, Wilfried; Klavžar, Sandi
title = Product Graphs: Structure and Recognition
publisher = Wiley
year = 2000
id = ISBN 0-471-37039-8

*cite article
author = Abbott, H. L.
title = Lower bounds for some Ramsey numbers
journal = Discrete Math.
volume = 2
year = 1972

External links

*mathworld | title = Graph Lexicographic Product | urlname = GraphLexicographicProduct


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Lexicographic product — In mathematics, a lexicographical or lexicographic product may be formed of * graphs ndash; see lexicographic product of graphs. * orders ndash; see lexicographical order …   Wikipedia

  • Graph operations — Operations on graphs produce new graphs from old ones. They may be separated into the following major categories. Contents 1 Unary operations 1.1 Elementary operations 1.2 Advanced operations 2 …   Wikipedia

  • 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

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • Cyclic order — In mathematics, a cyclic order is a way to arrange a set of objects in a circle.[nb] Unlike most structures in order theory, a cyclic order cannot be modeled as a binary relation a < b . One does not say that east is more clockwise than west.… …   Wikipedia

  • Order theory — For a topical guide to this subject, see Outline of order theory. Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as… …   Wikipedia

Share the article and excerpts

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