A lower bound for tree-width of Cartesian product graphs

摘要

In this paper, we give a lower bound for tree-width of Cartesian product graphs. To be more precise, we show that the bramble number of Cartesian product of graphs G_1 and G_2 is at least Hadwiger number of G_1 times PI number of G_2. We also demonstrate applications of the lower bound.%本論文では，2つのグラフG_1とG_2のデカルト積として表わされるグラフG_1□G_2のtree－widthに対するある下界を与える．より具体的には，G_1のHadwiger数とG_2のPI数の積がG_1□G_2のブランブル数の下界となることを示す．また木下界を用いた応用例も示す．