http://debianws.lexgopc.com/wiki143/index.php?action=history&feed=atom&title=Modular_product_of_graphsModular product of graphs - Revision history2026-05-15T17:13:30ZRevision history for this page on the wikiMediaWiki 1.43.1http://debianws.lexgopc.com/wiki143/index.php?title=Modular_product_of_graphs&diff=5552212&oldid=previmported>OlliverWithDoubleL: added short description, links, mvar2023-04-20T16:59:16Z<p>added short description, links, mvar</p>
<p><b>New page</b></p><div>{{short description|Binary operation in graph theory}}<br />
[[Image:modular_product.png|thumb|300px|The modular product of graphs.]]<br />
<br />
In [[graph theory]], the '''modular product''' of [[Graph (discrete mathematics)|graphs]] {{mvar|G}} and {{mvar|H}} is a graph formed by combining {{mvar|G}} and {{mvar|H}} that has applications to [[subgraph isomorphism]].<br />
It is one of several different kinds of [[graph product]]s that have been studied, generally using the same [[Vertex (graph theory)|vertex]] set (the [[Cartesian product]] of the [[Set (mathematics)|sets]] of vertices of the two graphs {{mvar|G}} and {{mvar|H}}) but with different rules for determining which edges to include.<br />
<br />
==Definition==<br />
The vertex set of the modular product of {{mvar|G}} and {{mvar|H}} is the [[cartesian product]] {{math|''V''(''G'') × ''V''(''H'')}}.<br />
Any two vertices {{math|(''u'', ''v'')}} and {{math|(''u' '', ''v' '')}} are adjacent in the modular product of {{mvar|G}} and {{mvar|H}} if<br />
and only if {{mvar|u}} is distinct from {{mvar|u'}}, {{mvar|v}} is distinct from {{mvar|v'}}, and either <br />
* {{mvar|u}} is adjacent with {{mvar|u'}} and {{mvar|v}} is adjacent with {{mvar|v'}}, '''or'''<br />
* {{mvar|u}} is not adjacent with {{mvar|u'}} and {{mvar|v}} is not adjacent with {{mvar|v'}}.<br />
<br />
==Application to subgraph isomorphism==<br />
Cliques in the modular product graph correspond to [[graph isomorphism|isomorphisms]] of [[induced subgraph]]s of {{mvar|G}} and {{mvar|H}}. Therefore, the modular product graph can be used to reduce problems of induced subgraph isomorphism to problems of finding [[clique (graph theory)|cliques]] in graphs. Specifically, the [[maximum common induced subgraph]] of both {{mvar|G}} and {{mvar|H}} corresponds to the [[maximum clique]] in their modular product. Although the problems of finding largest common induced subgraphs and of finding maximum cliques are both [[NP-complete]], this reduction allows [[clique problem|clique-finding algorithms]] to be applied to the common subgraph problem.<br />
<br />
==References==<br />
*{{citation<br />
| last1 = Barrow | first1 = H.<br />
| last2 = Burstall | first2 = R. | author2-link = Rod Burstall<br />
| doi = 10.1016/0020-0190(76)90049-1<br />
| issue = 4<br />
| journal = Information Processing Letters<br />
| pages = 83–84<br />
| title = Subgraph isomorphism, matching relational structures and maximal cliques<br />
| volume = 4<br />
| year = 1976}}.<br />
*{{citation<br />
| last = Levi | first = G.<br />
| doi = 10.1007/BF02575586<br />
| issue = 4<br />
| journal = Calcolo<br />
| pages = 341–352<br />
| title = A note on the derivation of maximal common subgraphs of two directed or undirected graphs<br />
| volume = 9<br />
| year = 1973}}.<br />
*{{citation<br />
| last = Vizing | first = V. G. | authorlink = Vadim G. Vizing<br />
| contribution = Reduction of the problem of isomorphism and isomorphic entrance to the task of finding the nondensity of a graph<br />
| page = 124<br />
| title = Proc. 3rd All-Union Conf. Problems of Theoretical Cybernetics<br />
| year = 1974}}.<br />
<br />
[[Category:Graph products]]</div>imported>OlliverWithDoubleL