Strong product of graphs
{{short description|Binary operation in graph theory}}
File:King's graph.svg, a strong product of two path graphs]]
In graph theory, the strong product is a way of combining two graphs to make a larger graph. Two vertices are adjacent in the strong product when they come from pairs of vertices in the factor graphs that are either adjacent or identical. The strong product is one of several different graph product operations that have been studied in graph theory. The strong product of any two graphs can be constructed as the union of two other products of the same two graphs, the Cartesian product of graphs and the tensor product of graphs.
An example of a strong product is the king's graph, the graph of moves of a chess king on a chessboard, which can be constructed as a strong product of path graphs. Decompositions of planar graphs and related graph classes into strong products have been used as a central tool to prove many other results about these graphs.
Care should be exercised when encountering the term strong product in the literature, since it has also been used to denote the tensor product of graphs.See page 2 of {{citation | first = László | last = Lovász | authorlink = László Lovász | title = On the Shannon Capacity of a Graph | journal = IEEE Transactions on Information Theory | volume = IT-25 | issue = 1 | pages = 1–7 | year = 1979 | doi = 10.1109/TIT.1979.1055985}}.
Definition and example
The strong product {{math|G ⊠ H}} of graphs {{mvar|G}} and {{mvar|H}} is a graph such that{{citation
|author1=Imrich, Wilfried |author2=Klavžar, Sandi |author3=Rall, Douglas F. | title = Graphs and their Cartesian Product
| publisher = A. K. Peters
| year = 2008
| isbn = 978-1-56881-429-2}}.
the vertex set of {{math|G ⊠ H}} is the Cartesian product {{math|V(G) × V(H)}}; and
distinct vertices {{math|(u,u' )}} and {{math|(v,v' )}} are adjacent in {{math|G ⊠ H}} if and only if:
: {{math|1=u = v}} and {{mvar|u'}} is adjacent to {{mvar|v'}}, or
: {{math|1=u' = v' }} and {{mvar|u}} is adjacent to {{mvar|v}}, or
: {{mvar|u}} is adjacent to {{mvar|v}} and {{mvar|u'}} is adjacent to {{mvar|v'}}.
It is the union of the Cartesian product and the tensor product.
For example, the king's graph, a graph whose vertices are squares of a chessboard and whose edges represent possible moves of a chess king, is a strong product of two path graphs. Its horizontal edges come from the Cartesian product, and its diagonal edges come from the tensor product of the same two paths. Together, these two kinds of edges make up the entire strong product.{{citation
| last1 = Berend | first1 = Daniel
| last2 = Korach | first2 = Ephraim
| last3 = Zucker | first3 = Shira
| contribution = Two-anticoloring of planar and related graphs
| contribution-url = http://www.emis.de/journals/DMTCS/pdfpapers/dmAD0130.pdf
| location = Nancy
| mr = 2193130
| pages = 335–341
| publisher = Association for Discrete Mathematics & Theoretical Computer Science
| series = Discrete Mathematics & Theoretical Computer Science Proceedings
| title = 2005 International Conference on Analysis of Algorithms
| year = 2005}}.
Properties and applications
Every planar graph is a subgraph of a strong product of a path and a graph of treewidth at most six.{{citation
| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović
| last2 = Joret | first2 = Gwenaël
| last3 = Micek | first3 = Piotr
| last4 = Morin | first4 = Pat | author4-link = Pat Morin
| last5 = Ueckerdt | first5 = Torsten
| last6 = Wood | first6 = David R. | author6-link = David Wood (mathematician)
| doi = 10.1145/3385731
| issue = 4
| journal = Journal of the ACM
| mr = 4148600
| page = Art. 22, 38
| title = Planar graphs have bounded queue-number
| volume = 67
| year = 2020| arxiv = 1904.04791 }}{{citation
| last1 = Ueckerdt | first1 = Torsten
| last2 = Wood | first2 = David R. | author2-link = David Wood (mathematician)
| last3 = Yi | first3 = Wendy
| doi = 10.37236/10614
| issue = 2
| journal = Electronic Journal of Combinatorics
| mr = 4441087
| at = Paper No. 2.51
| title = An improved planar graph product structure theorem
| volume = 29
| year = 2022| s2cid = 236772054
| doi-access = free
| arxiv = 2108.00198
}} This result has been used to prove that planar graphs have bounded queue number, small universal graphs and concise adjacency labeling schemes,{{citation
| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović
| last2 = Esperet | first2 = Louis
| last3 = Gavoille | first3 = Cyril
| last4 = Joret | first4 = Gwenaël
| last5 = Micek | first5 = Piotr
| last6 = Morin | first6 = Pat | author6-link = Pat Morin
| doi = 10.1145/3477542
| issue = 6
| journal = Journal of the ACM
| mr = 4402353
| page = Art. 42, 33
| title = Adjacency labelling for planar graphs (and beyond)
| volume = 68
| year = 2021| arxiv = 2003.04280 }}{{citation
| last1 = Gawrychowski | first1 = Pawel
| last2 = Janczewski | first2 = Wojciech
| editor1-last = Bringmann | editor1-first = Karl
| editor2-last = Chan | editor2-first = Timothy
| contribution = Simpler adjacency labeling for planar graphs with B-trees
| doi = 10.1137/1.9781611977066.3
| pages = 24–36
| publisher = Society for Industrial and Applied Mathematics
| title = 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022
| year = 2022| s2cid = 245738461
| last1 = Esperet | first1 = Louis
| last2 = Joret | first2 = Gwenaël
| last3 = Morin | first3 = Pat | author3-link = Pat Morin
| arxiv = 2010.05779
| title = Sparse universal graphs for planarity
| year = 2020}}{{citation
| last1 = Huynh | first1 = Tony
| last2 = Mohar | first2 = Bojan | author2-link = Bojan Mohar
| last3 = Šámal | first3 = Robert
| last4 = Thomassen | first4 = Carsten | author4-link = Carsten Thomassen (mathematician)
| last5 = Wood | first5 = David R. | author5-link = David Wood (mathematician)
| arxiv = 2109.00327
| title = Universality in minor-closed graph classes
| year = 2021}} and bounded nonrepetitive chromatic number{{citation
| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović
| last2 = Esperet | first2 = Louis
| last3 = Joret | first3 = Gwenaël
| last4 = Walczak | first4 = Bartosz
| last5 = Wood | first5 = David R. | author5-link = David Wood (mathematician)
| journal = Advances in Combinatorics
| mr = 4125346
| page = Paper No. 5, 11
| title = Planar graphs have bounded nonrepetitive chromatic number
| year = 2020}} and centered chromatic number.{{citation
| last1 = Dębski | first1 = Michał
| last2 = Felsner | first2 = Stefan
| last3 = Micek | first3 = Piotr
| last4 = Schröder | first4 = Felix
| doi = 10.19086/aic.27351
| journal = Advances in Combinatorics
| mr = 4309118
| at= Paper No. 8
| title = Improved bounds for centered colorings
| year = 2021| arxiv = 1907.04586
| s2cid = 195874032
}} This product structure can be found in linear time.{{citation
| last = Morin | first = Pat | author-link = Pat Morin
| doi = 10.1007/s00453-020-00793-5
| issue = 5
| journal = Algorithmica
| mr = 4242109
| pages = 1544–1558
| title = A fast algorithm for the product structure of planar graphs
| volume = 83
| year = 2021| arxiv = 2004.02530 | s2cid = 254028754 }}{{citation
| last1 = Bose | first1 = Prosenjit | author1-link = Jit Bose
| last2 = Morin | first2 = Pat | author2-link = Pat Morin
| last3 = Odak | first3 = Saeed
| arxiv = 2202.08870
| title = An optimal algorithm for the product structure of planar graphs
| year = 2022}} Beyond planar graphs, extensions of these results have been proven for graphs of bounded genus,{{citation
| last1 = Distel | first1 = Marc
| last2 = Hickingbotham | first2 = Robert
| last3 = Huynh | first3 = Tony
| last4 = Wood | first4 = David R. | author4-link = David Wood (mathematician)
| arxiv = 2112.10025
| doi = 10.46298/dmtcs.8877
| issue = 2
| journal = Discrete Mathematics & Theoretical Computer Science
| mr = 4504777
| page = Paper No. 6
| title = Improved product structure for graphs on surfaces
| volume = 24
| year = 2022| s2cid = 245335306
}} graphs with a forbidden minor that is an apex graph, bounded-degree graphs with any forbidden minor,{{citation
| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović
| last2 = Esperet | first2 = Louis
| last3 = Morin | first3 = Pat | author3-link = Pat Morin
| last4 = Walczak | first4 = Bartosz
| last5 = Wood | first5 = David R. | author5-link = David Wood (mathematician)
| doi = 10.1017/s0963548321000213
| issue = 1
| journal = Combinatorics, Probability and Computing
| mr = 4356460
| pages = 123–135
| title = Clustered 3-colouring graphs of bounded degree
| volume = 31
| year = 2022| arxiv = 2002.11721 | s2cid = 211532824 }} and k-planar graphs.{{citation
| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović
| last2 = Morin | first2 = Pat | author2-link = Pat Morin
| last3 = Wood | first3 = David R. | author3-link = David Wood (mathematician)
| arxiv = 1907.05168
| title = Graph product structure for non-minor-closed classes
| year = 2019}}
The clique number of the strong product of any two graphs equals the product of the clique numbers of the two graphs.{{citation
| last1 = Kozawa | first1 = Kyohei
| last2 = Otachi | first2 = Yota
| last3 = Yamazaki | first3 = Koichi
| doi = 10.1016/j.dam.2013.08.005
| journal = Discrete Applied Mathematics
| mr = 3128527
| pages = 251–258
| title = Lower bounds for treewidth of product graphs
| volume = 162
| year = 2014| doi-access = free
}} If two graphs both have bounded twin-width, and in addition one of them has bounded degree, then their strong product also has bounded twin-width.{{citation
| last1 = Bonnet | first1 = Édouard
| last2 = Geniet | first2 = Colin
| last3 = Kim | first3 = Eun Jung
| last4 = Thomassé | first4 = Stéphan
| last5 = Watrigant | first5 = Rémi
| arxiv = 2006.09877
| doi = 10.5070/C62257876
| issue = 2
| journal = Combinatorial Theory
| mr = 4449818
| page = P10:1–P10:42
| title = Twin-width II: small classes
| volume = 2
| year = 2022}}
A leaf power is a graph formed from the leaves of a tree by making two leaves adjacent when their distance in the tree is below some threshold . If is a -leaf power of a tree , then can be found as a subgraph of a strong product of with a -vertex cycle. This embedding has been used in recognition algorithms for leaf powers.{{citation
| last1 = Eppstein | first1 = David | author1-link = David Eppstein
| last2 = Havvaei | first2 = Elham
| doi = 10.1007/s00453-020-00720-8
| issue = 8
| journal = Algorithmica
| mr = 4132894
| pages = 2337–2359
| title = Parameterized leaf power recognition via embedding into graph products
| volume = 82
| year = 2020| s2cid = 254032445 | url = https://drops.dagstuhl.de/opus/volltexte/2019/10217/ | arxiv = 1810.02452
}}
The strong product of a 7-vertex cycle graph and a 4-vertex complete graph, , has been suggested as a possibility for a 10-chromatic biplanar graph that would improve the known bounds on the Earth–Moon problem; another suggested example is the graph obtained by removing any vertex from . In both cases, the number of vertices in these graphs is more than 9 times the size of their largest independent set, implying that their chromatic number is at least 10. However, it is not known whether these graphs are biplanar.{{citation
| last = Gethner | first = Ellen | author-link = Ellen Gethner
| editor1-last = Gera | editor1-first = Ralucca | editor1-link = Ralucca Gera
| editor2-last = Haynes | editor2-first = Teresa W. | editor2-link = Teresa W. Haynes
| editor3-last = Hedetniemi | editor3-first = Stephen T.
| contribution = To the Moon and beyond
| doi = 10.1007/978-3-319-97686-0_11
| mr = 3930641
| pages = 115–133
| publisher = Springer International Publishing
| series = Problem Books in Mathematics
| title = Graph Theory: Favorite Conjectures and Open Problems, II
| year = 2018}}
References
{{Reflist}}