lexicographic product of graphs
{{Short description|Graph in graph theory}}
Image:Graph-lexicographic-product.svg
In graph theory, the lexicographic product or (graph) composition {{math|G ∙ H}} of graphs {{mvar|G}} and {{mvar|H}} is a graph such that
- the vertex set of {{math|G ∙ H}} is the cartesian product {{math|V(G) × V(H)}}; and
- any two vertices {{math|(u,v)}} and {{math|(x,y)}} are adjacent in {{math|G ∙ H}} if and only if either {{mvar|u}} is adjacent to {{mvar|x}} in {{mvar|G}} or {{math|1=u = x}} and {{mvar|v}} is adjacent to {{mvar|y}} in {{mvar|H}}.
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 {{harvs|first=Felix|last=Hausdorff|authorlink=Felix Hausdorff|year=1914|txt}}.{{sfnp|Hausdorff|1914}} As {{harvtxt|Feigenbaum|Schäffer|1986}} showed, the problem of recognizing whether a graph is a lexicographic product is equivalent in complexity to the graph isomorphism problem.{{sfnp|Feigenbaum|Schäffer|1986}}
Properties
The lexicographic product is in general noncommutative: {{math|G ∙ H ≠ H ∙ G}}. However it satisfies a distributive law with respect to disjoint union: {{math|1=(A + B) ∙ C = A ∙ C + B ∙ C}}.
In addition it satisfies an identity with respect to complementation: {{math|1=C(G ∙ H) = C(G) ∙ C(H)}}. In particular, the lexicographic product of two self-complementary graphs is self-complementary.
The independence number of a lexicographic product may be easily calculated from that of its factors:{{sfnp|Geller|Stahl|1975}}
:{{math|1=α(G ∙ H) = α(G)α(H)}}.
The clique number of a lexicographic product is as well multiplicative:
:{{math|1=ω(G ∙ H) = ω(G)ω(H)}}.
The chromatic number of a lexicographic product is equal to the b-fold chromatic number of G, for b equal to the chromatic number of H:
:{{math|1=χ(G ∙ H) = χb(G)}}, where {{math|1=b = χ(H)}}.
The lexicographic product of two graphs is a perfect graph if and only if both factors are perfect.{{sfnp|Ravindra|Parthasarathy|1977}}
Notes
{{reflist}}
References
- {{citation
| last1 = Feigenbaum | first1 = J. | last2 = Schäffer | first2 = A. A.
| year = 1986
| title = Recognizing composite graphs is equivalent to testing graph isomorphism
| journal = SIAM Journal on Computing
| volume = 15
| pages = 619–627
| mr = 0837609
| doi = 10.1137/0215045
| issue = 2}}.
- {{citation
| last1 = Geller | first1 = D. | last2 = Stahl | first2 = S.
| title = The chromatic number and other functions of the lexicographic product
| journal = Journal of Combinatorial Theory | series = Series B
| volume = 19
| year = 1975
| pages = 87–95
| mr = 0392645
| doi = 10.1016/0095-8956(75)90076-3| doi-access =
}}.
- {{citation
| last = Hausdorff | first = F.
| authorlink = Felix Hausdorff
| title = Grundzüge der Mengenlehre
| year = 1914
| location = Leipzig}}
- {{citation
| last1 = Imrich | first1 = Wilfried | last2 = Klavžar | first2 = Sandi
| title = Product Graphs: Structure and Recognition
| publisher = Wiley
| year = 2000
| isbn = 0-471-37039-8}}
- {{citation
| last1 = Ravindra | first1 = G.
| last2 = Parthasarathy | first2 = K. R.
| doi = 10.1016/0012-365X(77)90056-5
| issue = 2
| journal = Discrete Mathematics
| mr = 0491304
| pages = 177–186
| title = Perfect product graphs
| volume = 20
| year = 1977| hdl = 10338.dmlcz/102469
| hdl-access = free
}}.
External links
- {{mathworld | title = Graph Lexicographic Product | urlname = GraphLexicographicProduct}}