Handbook of Product Graphs, Second Edition examines the dichotomy between the structure of products and their subgraphs. It also features the design of efficient algorithms that recognize products and their subgraphs and explores the relationship between graph parameters of the product and factors. Extensively revised and expanded, the handbook presents full proofs of many important results as well as up-to-date research and conjectures. Results and Algorithms New to the Second Edition: Cancellation results A quadratic recognition algorithm for partial cubes Results on the strong isometric dimension Computing the Wiener index via canonical isometric embedding Connectivity results A fractional version of Hedetniemis conjecture Results on the independence number of Cartesian powers of vertex-transitive graphs Verification of Vizings conjecture for chordal graphs Results on minimum cycle bases Numerous selected recent results, such as complete minors and nowhere-zero flows The second edition of this classic handbook provides a thorough introduction to the subject and an extensive survey of the field. The first three parts of the book cover graph products in detail. The authors discuss algebraic properties, such as factorization and cancellation, and explore interesting and important classes of subgraphs. The fourth part presents algorithms for the recognition of products and related classes of graphs. The final two parts focus on graph invariants and infinite, directed, and product-like graphs. Sample implementations of selected algorithms and other information are available on the books website, which can be reached via the authors home pages.
Dayan D, Solovey K, Pavone M and Halperin D (2023). Near-Optimal Multi-Robot Motion Planning with Finite Sampling, IEEE Transactions on Robotics , 39 :5 , (3422-3436), Online publication date: 1-Oct-2023 .
Dayan D, Solovey K, Pavone M and Halperin D Near-Optimal Multi-Robot Motion Planning with Finite Sampling 2021 IEEE International Conference on Robotics and Automation (ICRA), (9190-9196)
Imrich W and Peterin I (2018). Cartesian products of directed graphs with loops, Discrete Mathematics , 341 :5 , (1336-1343), Online publication date: 1-May-2018 .
Geetha J and Somasundaram K (2018). Total Colorings of Product Graphs, Graphs and Combinatorics , 34 :2 , (339-347), Online publication date: 1-Mar-2018 .
Kuziak D, Puertas M, Rodrguez-Velzquez J and Yero I (2018). Strong resolving graphs, Discrete Applied Mathematics , 236 :C , (270-287), Online publication date: 19-Feb-2018 .
repnjak M and Tratnik N (2017). The Szeged index and the Wiener index of partial cubes with applications to chemical graphs, Applied Mathematics and Computation , 309 :C , (324-333), Online publication date: 15-Sep-2017 .
Kubota S (2017). Unification of Graph Products and Compatibility with Switching, Graphs and Combinatorics , 33 :5 , (1347-1355), Online publication date: 1-Sep-2017 .
Al-Bar J, Al-Kenani A, Muthana N and Praeger C (2017). Finite edge-transitive oriented graphs of valency four with cyclic normal quotients, Journal of Algebraic Combinatorics: An International Journal , 46 :1 , (109-133), Online publication date: 1-Aug-2017 .
Hartinger T and Milani M (2017). 1-perfectly orientable graphs and graph products, Discrete Mathematics , 340 :7 , (1727-1737), Online publication date: 1-Jul-2017 .
Mathew K and Östergård P (2017). New lower bounds for the Shannon capacity of odd cycles, Designs, Codes and Cryptography , 84 :1-2 , (13-22), Online publication date: 1-Jul-2017 .
Rall D and Wash K (2017). On Minimum Identifying Codes in Some Cartesian Product Graphs, Graphs and Combinatorics , 33 :4 , (1037-1053), Online publication date: 1-Jul-2017 .
Akhtar Y and Maity S (2017). Covering Arrays on Product Graphs, Graphs and Combinatorics , 33 :4 , (635-652), Online publication date: 1-Jul-2017 .
Hu S and Shayevitz O (2017). The $\rho $ -Capacity of a Graph, IEEE Transactions on Information Theory , 63 :4 , (2241-2253), Online publication date: 1-Apr-2017 .
Duarte M, Penso L, Rautenbach D and Santos Souza U (2017). Complexity properties of complementary prisms, Journal of Combinatorial Optimization , 33 :2 , (365-372), Online publication date: 1-Feb-2017 .
Hinz A, Klavźar S and Zemljič S (2017). A survey and classification of Sierpiński-type graphs, Discrete Applied Mathematics , 217 :P3 , (565-600), Online publication date: 30-Jan-2017 .
Tepanyan H and Petrosyan P (2017). Interval edge-colorings of composition of graphs, Discrete Applied Mathematics , 217 :P2 , (368-374), Online publication date: 30-Jan-2017 .
Estrada-Moreno A, Yero I and Rodríguez-Velázquez J (2016). Relationships Between the 2-Metric Dimension and the 2-Adjacency Dimension in the Lexicographic Product of Graphs, Graphs and Combinatorics , 32 :6 , (2367-2392), Online publication date: 1-Nov-2016 .
Pĕgřímek D and Gregor P (2016). Hamiltonian Laceability of Hypercubes Without Isometric Subgraphs, Graphs and Combinatorics , 32 :6 , (2591-2624), Online publication date: 1-Nov-2016 .
Brown J and Mol L (2016). On the roots of the node reliability polynomial, Networks , 68 :3 , (238-246), Online publication date: 1-Oct-2016 .
Ramírez-Cruz Y, Estrada-Moreno A and Rodríguez-Velázquez J (2016). The Simultaneous Metric Dimension of Families Composed by Lexicographic Product Graphs, Graphs and Combinatorics , 32 :5 , (2093-2120), Online publication date: 1-Sep-2016 .
Dod M (2016). Graph products of the trivariate total domination polynomial and related polynomials, Discrete Applied Mathematics , 209 :C , (92-101), Online publication date: 20-Aug-2016 .
Clark R, Punzo G, Baumanis K and Macdonald M Consensus speed maximisation in engineered swarms with autocratic leaders Proceedings of the International Conference on Artificial Intelligence and Robotics and the International Conference on Automation, Control and Robotics Engineering, (1-5)
Anholcer M, Cichacz S and Peterin I (2016). Spectra of graphs and closed distance magic labelings, Discrete Mathematics , 339 :7 , (1915-1923), Online publication date: 6-Jul-2016 .
Estrada-Moreno A, Yero I and Rodríguez-Velázquez J (2016). The k -metric dimension of the lexicographic product of graphs, Discrete Mathematics , 339 :7 , (1924-1934), Online publication date: 6-Jul-2016 .
Barragán-Ramírez G and Rodríguez-Velázquez J (2016). The Local Metric Dimension of Strong Product Graphs, Graphs and Combinatorics , 32 :4 , (1263-1278), Online publication date: 1-Jul-2016 .
Hammack R, Imrich W and Klavžar S (2016). Edge-transitive products, Journal of Algebraic Combinatorics: An International Journal , 43 :4 , (837-850), Online publication date: 1-Jun-2016 .
Reeves T, Farr R, Blundell J, Gallagher A and Fink T (2016). Eigenvalues of neutral networks, Discrete Mathematics , 339 :4 , (1283-1290), Online publication date: 6-Apr-2016 .
González Yero I (2016). Strong resolving partitions for strong product graphs and Cartesian product graphs, Discrete Applied Mathematics , 202 :C , (70-78), Online publication date: 31-Mar-2016 .
Varghese S and Vijayakumar A On the Power Domination Number of Graph Products Proceedings of the Second International Conference on Algorithms and Discrete Applied Mathematics - Volume 9602, (357-367)
(2016). Fast factorization of Cartesian products of (directed) hypergraphs, Theoretical Computer Science , 615 :C , (1-11), Online publication date: 15-Feb-2016 .
Crespelle C and Thierry E (2015). Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time, Discrete Mathematics , 338 :12 , (2393-2407), Online publication date: 6-Dec-2015 .
Meierling D, Protti F, Rautenbach D and de Almeida A (2015). Cycles in complementary prisms, Discrete Applied Mathematics , 193 :C , (180-186), Online publication date: 1-Oct-2015 .
Saha L and Panigrahi P (2015). A lower bound for radio k -chromatic number, Discrete Applied Mathematics , 192 :C , (87-100), Online publication date: 10-Sep-2015 .
Koch I and Peterin I (2015). The b-chromatic index of direct product of graphs, Discrete Applied Mathematics , 190 :C , (109-117), Online publication date: 20-Aug-2015 .
Donno A (2015). Generalized Wreath Products of Graphs and Groups, Graphs and Combinatorics , 31 :4 , (915-926), Online publication date: 1-Jul-2015 .
(2015). A new application of the ⊗ h -product to α -labelings, Discrete Mathematics , 338 :6 , (839-843), Online publication date: 6-Jun-2015 .
Klavzar S and Rho Y (2015). On the Wiener index of generalized Fibonacci cubes and Lucas cubes, Discrete Applied Mathematics , 187 :C , (155-160), Online publication date: 31-May-2015 .
Vesel A (2015). Linear Recognition and Embedding of Fibonacci Cubes, Algorithmica , 71 :4 , (1021-1034), Online publication date: 1-Apr-2015 .
Marc T (2015). Vertex-transitive median graphs of non-exponential growth, Discrete Mathematics , 338 :3 , (191-198), Online publication date: 6-Mar-2015 .
Jha P and Smith J (2015). Cycle Kronecker products that are representable as optimal circulants, Discrete Applied Mathematics , 181 :C , (130-138), Online publication date: 30-Jan-2015 .
Erveš R and Žerovnik J (2015). Improved upper bounds for vertex and edge fault diameters of Cartesian graph bundles, Discrete Applied Mathematics , 181 :C , (90-97), Online publication date: 30-Jan-2015 .
Schröppel C and Wackerfuß J (2015). Meshing highly regular structures, Journal of Nanomaterials , 16 :1 , (441-441), Online publication date: 1-Jan-2015 .
Jha P (2014). Tight-optimal circulants vis--vis twisted tori, Discrete Applied Mathematics , 175 :C , (24-34), Online publication date: 1-Oct-2014 .
Jha P (2014). Tight-optimal circulants vis-à-vis twisted tori, Discrete Applied Mathematics , 175 , (24-34), Online publication date: 1-Oct-2014 .
Gaüzère B, Bougleux S, Riesen K and Brun L Approximate Graph Edit Distance Guided by Bipartite Matching of Bags of Walks Proceedings of the Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition - Volume 8621, (73-82)
Klavžar S and Nadjafi-Arani M (2014). Computing distance moments on graphs with transitive Djoković-Winkler relation, Discrete Applied Mathematics , 166 :C , (269-272), Online publication date: 31-Mar-2014 .
Jha P (2014). Dense bipartite circulants and their routing via rectangular twisted torus, Discrete Applied Mathematics , 166 :C , (141-158), Online publication date: 31-Mar-2014 .
Azarija J (2014). A short note on a short remark of Graham and Lovász, Discrete Mathematics , 315-316 , (65-68), Online publication date: 1-Feb-2014 .
Petrie C (2014). ( F , I ) -security in graphs, Discrete Applied Mathematics , 162 :C , (285-295), Online publication date: 10-Jan-2014 .
Petrie C (2014). (F,I)-security in graphs, Discrete Applied Mathematics , 162 , (285-295), Online publication date: 1-Jan-2014 .
ŠUmenjak T, Rall D and Tepeh A (2013). Rainbow domination in the lexicographic product of graphs, Discrete Applied Mathematics , 161 :13-14 , (2133-2141), Online publication date: 1-Sep-2013 .
Ducoffe G (2013). Hamiltonicity of large generalized de Bruijn cycles, Discrete Applied Mathematics , 161 :13-14 , (2200-2204), Online publication date: 1-Sep-2013 .
Hon W, Kloks T, Liu H, Poon S and Wang Y On independence domination Proceedings of the 19th international conference on Fundamentals of Computation Theory, (183-194)
Erveš R and Erovnik J (2013). Mixed fault diameter of Cartesian graph bundles, Discrete Applied Mathematics , 161 :12 , (1726-1733), Online publication date: 1-Aug-2013 .
Yero I, RodríGuez-VeláZquez J and Bermudo S (2013). Alliance free sets in Cartesian product graphs, Discrete Applied Mathematics , 161 :10-11 , (1618-1625), Online publication date: 1-Jul-2013 .
Wang W and Yan Z (2013). Connectivity of Kronecker products with complete multipartite graphs, Discrete Applied Mathematics , 161 :10-11 , (1655-1659), Online publication date: 1-Jul-2013 .
Mulder H and Novick B (2013). A tight axiomatization of the median procedure on median graphs, Discrete Applied Mathematics , 161 :6 , (838-846), Online publication date: 1-Apr-2013 .
Chalermsook P, Laekhanukit B and Nanongkai D Graph products revisited Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, (1557-1576)
