Graph Sensitivity of Cartesian Products with Matched Bridges
En palabras de los autores
For a graph , let denote the minimum of the maximum degree of an induced subgraph with vertices, where is the independence number, and write . Huang's theorem gives for the -dimensional hypercube . We extend this lower bound to Cartesian products of bipartite graphs with perfect matchings and prove that equality holds when the factors are connected and each has a matched bridge. In particular, we prove that whenever each is a tree with a perfect matching. We determine the sensitivity of every Cartesian product of paths, settling the even-path case left open by Zeng and Hou [J. Graph Theory 107 (2024), 169--180]. For these tree products, with , we also prove that whenever . When , this equality holds for all , provided that at least one factor is not . Matching cuts give an additional exact range for products of even-order paths. Finally, we prove that for every with , whereas and .
Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 17 pages