Strong product of 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.^[1]

Definition and example

The strong product $G ⊠ H$ of graphs $G$ and $H$ is a graph such that^[2] the vertex set of $G ⊠ H$ is the Cartesian product $V (G) \times V (H)$ ; and distinct vertices $(u, u')$ and $(v, v')$ are adjacent in $G ⊠ H$ if and only if:

u = v

and

u'

is adjacent to

v'

, or

u' = v'

and

u

is adjacent to

v

, or

u

is adjacent to

v

and

u'

is adjacent to

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.^[3]

Properties and applications

Every planar graph is a subgraph of a strong product of a path and a graph of treewidth at most six.^[4]^[5] This result has been used to prove that planar graphs have bounded queue number,^[4] small universal graphs and concise adjacency labeling schemes,^[6]^[7]^[8]^[9] and bounded nonrepetitive chromatic number^[10] and centered chromatic number.^[11] This product structure can be found in linear time.^[12]^[13] Beyond planar graphs, extensions of these results have been proven for graphs of bounded genus,^[4]^[14] graphs with a forbidden minor that is an apex graph,^[4] bounded-degree graphs with any forbidden minor,^[15] and k-planar graphs.^[16]

The clique number of the strong product of any two graphs equals the product of the clique numbers of the two graphs.^[17] 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.^[18]

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 $k$ . If $G$ is a $k$ -leaf power of a tree $T$ , then $T$ can be found as a subgraph of a strong product of $G$ with a $k$ -vertex cycle. This embedding has been used in recognition algorithms for leaf powers.^[19]

The strong product of a 7-vertex cycle graph and a 4-vertex complete graph, $C_{7}\boxtimes K_{4}$ , 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 $C_{5}\boxtimes K_{4}$ . 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.^[20]

References

^ See page 2 of Lovász, László (1979), "On the Shannon Capacity of a Graph", IEEE Transactions on Information Theory, IT-25 (1): 1–7, doi:10.1109/TIT.1979.1055985.
^ Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), Graphs and their Cartesian Product, A. K. Peters, ISBN 978-1-56881-429-2.
^ Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005), "Two-anticoloring of planar and related graphs" (PDF), 2005 International Conference on Analysis of Algorithms, Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, pp. 335–341, MR 2193130.
^ ^a ^b ^c ^d Dujmović, Vida; Joret, Gwenaël; Micek, Piotr; Morin, Pat; Ueckerdt, Torsten; Wood, David R. (2020), "Planar graphs have bounded queue-number", Journal of the ACM, 67 (4): Art. 22, 38, arXiv:1904.04791, doi:10.1145/3385731, MR 4148600
^ Ueckerdt, Torsten; Wood, David R.; Yi, Wendy (2022), "An improved planar graph product structure theorem", Electronic Journal of Combinatorics, 29 (2), Paper No. 2.51, arXiv:2108.00198, doi:10.37236/10614, MR 4441087, S2CID 236772054
^ Dujmović, Vida; Esperet, Louis; Gavoille, Cyril; Joret, Gwenaël; Micek, Piotr; Morin, Pat (2021), "Adjacency labelling for planar graphs (and beyond)", Journal of the ACM, 68 (6): Art. 42, 33, arXiv:2003.04280, doi:10.1145/3477542, MR 4402353
^ Gawrychowski, Pawel; Janczewski, Wojciech (2022), "Simpler adjacency labeling for planar graphs with B-trees", in Bringmann, Karl; Chan, Timothy (eds.), 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022, Society for Industrial and Applied Mathematics, pp. 24–36, doi:10.1137/1.9781611977066.3, S2CID 245738461
^ Esperet, Louis; Joret, Gwenaël; Morin, Pat (2020), Sparse universal graphs for planarity, arXiv:2010.05779
^ Huynh, Tony; Mohar, Bojan; Šámal, Robert; Thomassen, Carsten; Wood, David R. (2021), Universality in minor-closed graph classes, arXiv:2109.00327
^ Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Walczak, Bartosz; Wood, David R. (2020), "Planar graphs have bounded nonrepetitive chromatic number", Advances in Combinatorics: Paper No. 5, 11, MR 4125346
^ Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2021), "Improved bounds for centered colorings", Advances in Combinatorics, Paper No. 8, arXiv:1907.04586, doi:10.19086/aic.27351, MR 4309118, S2CID 195874032
^ Morin, Pat (2021), "A fast algorithm for the product structure of planar graphs", Algorithmica, 83 (5): 1544–1558, arXiv:2004.02530, doi:10.1007/s00453-020-00793-5, MR 4242109, S2CID 254028754
^ Bose, Prosenjit; Morin, Pat; Odak, Saeed (2022), An optimal algorithm for the product structure of planar graphs, arXiv:2202.08870
^ Distel, Marc; Hickingbotham, Robert; Huynh, Tony; Wood, David R. (2022), "Improved product structure for graphs on surfaces", Discrete Mathematics & Theoretical Computer Science, 24 (2): Paper No. 6, arXiv:2112.10025, doi:10.46298/dmtcs.8877, MR 4504777, S2CID 245335306
^ Dujmović, Vida; Esperet, Louis; Morin, Pat; Walczak, Bartosz; Wood, David R. (2022), "Clustered 3-colouring graphs of bounded degree", Combinatorics, Probability and Computing, 31 (1): 123–135, arXiv:2002.11721, doi:10.1017/s0963548321000213, MR 4356460, S2CID 211532824
^ Dujmović, Vida; Morin, Pat; Wood, David R. (2019), Graph product structure for non-minor-closed classes, arXiv:1907.05168
^ Kozawa, Kyohei; Otachi, Yota; Yamazaki, Koichi (2014), "Lower bounds for treewidth of product graphs", Discrete Applied Mathematics, 162: 251–258, doi:10.1016/j.dam.2013.08.005, MR 3128527
^ Bonnet, Édouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width II: small classes", Combinatorial Theory, 2 (2): P10:1–P10:42, arXiv:2006.09877, doi:10.5070/C62257876, MR 4449818
^ Eppstein, David; Havvaei, Elham (2020), "Parameterized leaf power recognition via embedding into graph products", Algorithmica, 82 (8): 2337–2359, arXiv:1810.02452, doi:10.1007/s00453-020-00720-8, MR 4132894, S2CID 254032445
^ Gethner, Ellen (2018), "To the Moon and beyond", in Gera, Ralucca; Haynes, Teresa W.; Hedetniemi, Stephen T. (eds.), Graph Theory: Favorite Conjectures and Open Problems, II, Problem Books in Mathematics, Springer International Publishing, pp. 115–133, doi:10.1007/978-3-319-97686-0_11, MR 3930641

[1] See page 2 of Lovász, László (1979), "On the Shannon Capacity of a Graph", IEEE Transactions on Information Theory, IT-25 (1): 1–7, doi:10.1109/TIT.1979.1055985.

[2] Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), Graphs and their Cartesian Product, A. K. Peters, ISBN 978-1-56881-429-2.

[3] Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005), "Two-anticoloring of planar and related graphs" (PDF), 2005 International Conference on Analysis of Algorithms, Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, pp. 335–341, MR 2193130.

[djmmuw-4] Dujmović, Vida; Joret, Gwenaël; Micek, Piotr; Morin, Pat; Ueckerdt, Torsten; Wood, David R. (2020), "Planar graphs have bounded queue-number", Journal of the ACM, 67 (4): Art. 22, 38, arXiv:1904.04791, doi:10.1145/3385731, MR 4148600

[5] Ueckerdt, Torsten; Wood, David R.; Yi, Wendy (2022), "An improved planar graph product structure theorem", Electronic Journal of Combinatorics, 29 (2), Paper No. 2.51, arXiv:2108.00198, doi:10.37236/10614, MR 4441087, S2CID 236772054

[6] Dujmović, Vida; Esperet, Louis; Gavoille, Cyril; Joret, Gwenaël; Micek, Piotr; Morin, Pat (2021), "Adjacency labelling for planar graphs (and beyond)", Journal of the ACM, 68 (6): Art. 42, 33, arXiv:2003.04280, doi:10.1145/3477542, MR 4402353

[7] Gawrychowski, Pawel; Janczewski, Wojciech (2022), "Simpler adjacency labeling for planar graphs with B-trees", in Bringmann, Karl; Chan, Timothy (eds.), 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022, Society for Industrial and Applied Mathematics, pp. 24–36, doi:10.1137/1.9781611977066.3, S2CID 245738461

[8] Esperet, Louis; Joret, Gwenaël; Morin, Pat (2020), Sparse universal graphs for planarity, arXiv:2010.05779

[9] Huynh, Tony; Mohar, Bojan; Šámal, Robert; Thomassen, Carsten; Wood, David R. (2021), Universality in minor-closed graph classes, arXiv:2109.00327

[10] Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Walczak, Bartosz; Wood, David R. (2020), "Planar graphs have bounded nonrepetitive chromatic number", Advances in Combinatorics: Paper No. 5, 11, MR 4125346

[11] Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2021), "Improved bounds for centered colorings", Advances in Combinatorics, Paper No. 8, arXiv:1907.04586, doi:10.19086/aic.27351, MR 4309118, S2CID 195874032

[12] Morin, Pat (2021), "A fast algorithm for the product structure of planar graphs", Algorithmica, 83 (5): 1544–1558, arXiv:2004.02530, doi:10.1007/s00453-020-00793-5, MR 4242109, S2CID 254028754

[13] Bose, Prosenjit; Morin, Pat; Odak, Saeed (2022), An optimal algorithm for the product structure of planar graphs, arXiv:2202.08870

[14] Distel, Marc; Hickingbotham, Robert; Huynh, Tony; Wood, David R. (2022), "Improved product structure for graphs on surfaces", Discrete Mathematics & Theoretical Computer Science, 24 (2): Paper No. 6, arXiv:2112.10025, doi:10.46298/dmtcs.8877, MR 4504777, S2CID 245335306

[15] Dujmović, Vida; Esperet, Louis; Morin, Pat; Walczak, Bartosz; Wood, David R. (2022), "Clustered 3-colouring graphs of bounded degree", Combinatorics, Probability and Computing, 31 (1): 123–135, arXiv:2002.11721, doi:10.1017/s0963548321000213, MR 4356460, S2CID 211532824

[16] Dujmović, Vida; Morin, Pat; Wood, David R. (2019), Graph product structure for non-minor-closed classes, arXiv:1907.05168

[17] Kozawa, Kyohei; Otachi, Yota; Yamazaki, Koichi (2014), "Lower bounds for treewidth of product graphs", Discrete Applied Mathematics, 162: 251–258, doi:10.1016/j.dam.2013.08.005, MR 3128527

[18] Bonnet, Édouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width II: small classes", Combinatorial Theory, 2 (2): P10:1–P10:42, arXiv:2006.09877, doi:10.5070/C62257876, MR 4449818

[19] Eppstein, David; Havvaei, Elham (2020), "Parameterized leaf power recognition via embedding into graph products", Algorithmica, 82 (8): 2337–2359, arXiv:1810.02452, doi:10.1007/s00453-020-00720-8, MR 4132894, S2CID 254032445

[20] Gethner, Ellen (2018), "To the Moon and beyond", in Gera, Ralucca; Haynes, Teresa W.; Hedetniemi, Stephen T. (eds.), Graph Theory: Favorite Conjectures and Open Problems, II, Problem Books in Mathematics, Springer International Publishing, pp. 115–133, doi:10.1007/978-3-319-97686-0_11, MR 3930641

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]