| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6872496 | Discrete Applied Mathematics | 2014 | 8 Pages |
Abstract
Two lower bounds for the treewidth of product graphs are presented in terms of the bramble number. The first bound is that the bramble number of the Cartesian product of graphs G1 and G2 must be at least the product of the Hadwiger number of G1 and the PI number of G2, where the PI number is a new graph parameter introduced in this paper. The second bound is that the bramble number of the strong product of graphs G1 and G2 must be at least the product of the Hadwiger number of G1 and the bramble number of G2. We also demonstrate applications of the lower bounds.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Kyohei Kozawa, Yota Otachi, Koichi Yamazaki,