Graph Sensitivity of Cartesian Products with Matched Bridges
Abstract
For a graph G, let ft(G) denote the minimum of the maximum degree of an induced subgraph with α(G)+t vertices, where α(G) is the independence number, and write f(G)=f1(G). Huang's theorem gives f(Qk)≥⌈√k⌉ for the k-dimensional hypercube Qk. We extend this lower bound to Cartesian products of k 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 f(T1Box⋯Box Tk)=⌈√k⌉ whenever each Ti 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 D=⌈√k⌉, we also prove that ft(T1Box⋯Box Tk)=D whenever 1≤ t≤ 2D−⌈log2D⌉−1. When t=2, this equality holds for all k≥ 2, provided that at least one factor is not K2. Matching cuts give an additional exact range for products of even-order paths. Finally, we prove that f2(Qk)=⌈√k⌉ for every k≥ 2 with knot∈ {4,9}, whereas f2(Q4)=3 and 3≤ f2(Q9)≤ 4.
Related
- On k-limited domination: complexity and Cartesian products
- Sn-equivariant L-classes of Cartesian powers of Witt spaces and the Hodge index conjecture for symmetric products
- The Pairing-Hamiltonian property in Cartesian products of graphs
- Coded Computing for Dynamic System via Cartesian Products
- Well-Covered Powers: Cartesian Products and Cayley Graphs
BibTeX
@misc{hong2026graph,
title = {{Graph Sensitivity of Cartesian Products with Matched Bridges}},
author = {Zhen-Mu Hong and Zi-Yi Wu and Zheng-Jiang Xia},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09483},
eprint = {2610.09483},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09483},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Graph Sensitivity of Cartesian Products with Matched Bridges
AU - Zhen-Mu Hong
AU - Zi-Yi Wu
AU - Zheng-Jiang Xia
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.09483
UR - https://arxiv.org/abs/2610.09483
AB - For a graph G, let f_t(G) denote the minimum of the maximum degree of an induced subgraph with α(G)+t vertices, where α(G) is the independence number, and write f(G)=f_1(G). Huang's theorem gives f(Q_k)≥⌈√k⌉ for the k-dimensional hypercube Q_k. We extend this lower bound to Cartesian products of k 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 f(T_1Box⋯Box T_k)=⌈√k⌉ whenever each T_i 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 D=⌈√k⌉, we also prove that f_t(T_1Box⋯Box T_k)=D whenever 1≤ t≤ 2^D−⌈log_2D⌉−1. When t=2, this equality holds for all k≥ 2, provided that at least one factor is not K_2. Matching cuts give an additional exact range for products of even-order paths. Finally, we prove that f_2(Q_k)=⌈√k⌉ for every k≥ 2 with knot∈ {4,9}, whereas f_2(Q_4)=3 and 3≤ f_2(Q_9)≤ 4.
ER -