We relate the isoperimetric inequalities with many width parameters of graphs: treewidth, pathwidth and the carving width. Using these relations, we deduce 1. A lower bound for the treewidth in terms of girth and average degree 2. The exact values of the pathwidth and carving width of the d-dimensional hypercube, H_d 3. That treewidth (H_d) = Θ (2d/d~(1/2)). Moreover we study these parameters in the case of a generalization of hypercubes, namely the Hamming graphs.
展开▼
