zbMATH — the first resource for mathematics

A spectral lower bound for the treewidth of a graph and its consequences. (English) Zbl 1161.68647
Summary: We give a lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. We use this lower bound to show that the treewidth of a \(d\)-dimensional hypercube is at least \(\lfloor 3\cdot 2d/(2(d+4))\rfloor - 1\). The currently known upper bound is \(0(2^d/\sqrt d)\). We generalize this result to Hamming graphs. We also observe that every graph \(G\) on \(n\) vertices, with maximum degree \(\Delta\) contains an induced cycle (chordless cycle) of length at least \(1+\log_{\Delta}(\mu n/8)\) (provided \(G\) is not acyclic),has a clique minor \(K_h\) for some \(h=\Omega ((n\mu ^{2}/(\Delta +2\mu )^{2})^{1/3})\), where \(\mu \) is the second smallest eigenvalue of the Laplacian matrix of \(G\).

68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Alon, N., Eigen values and expanders, Combinatorica, 6, 83-96, (1986) · Zbl 0661.05053
[2] Alon, N.; Millman, V.D., λ1, isoperimetric inequalities for graphs and super concentrators, J. combin. theory, ser. B, 38, 73-88, (1985) · Zbl 0549.05051
[3] Alon, N.; Seymour, P.D.; Thomas, R., A separator theorem for graphs with an excluded minor and its applications, (), 293-299
[4] Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability—a survey, Bit, 25, 2-23, (1985) · Zbl 0573.68018
[5] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems on graphs embedded in k-trees, Discrete appl. math., 23, 11-24, (1989) · Zbl 0666.68067
[6] Biggs, N., Algebraic graph theory, (1993), Cambridge University Press Cambridge
[7] Bodlaender, H.L., A tourist guide through treewidth, Acta cybernet., 11, 1-21, (1993) · Zbl 0804.68101
[8] Bodlaender, H.L., A linear time algorithm for finding tree decompositions of small treewidth, SIAM J. comput., 25, 1305-1317, (1996) · Zbl 0864.68074
[9] Bodlaender, H.L.; Hagerup, T., Parallel algorithms with optimal speedup for bounded treewidth, SIAM J. comput., 27, 1725-1746, (1998) · Zbl 0907.68089
[10] Bodlaender, H.L.; Thilikos, D.M., Treewidth for graphs with small chordality, Discrete appl. math., 79, 45-61, (1997) · Zbl 0895.68113
[11] Bondy, J.A., Basic graph theory: paths and circuits, () · Zbl 0849.05044
[12] Brouwer, A.E.; Cohen, A.M.; Neumaier, A., Distance-regular graphs, (1989), Springer Berlin · Zbl 0747.05073
[13] Chlebikova, J., On the tree-width of a graph, Acta math. univ. comen., 61, 225-236, (1992) · Zbl 0821.05014
[14] Fiedler, M., The algebraic connectivity of graphs, Czech. math. J., 23, 298-305, (1973) · Zbl 0265.05119
[15] Jájá, J., An introduction to parallel algorithms, (1992), Addison-Wesley Reading, MA · Zbl 0781.68009
[16] Leighton, T., Introduction to parallel algorithms and architectures: arrays; trees; hypercubes, (1992), Academic Press Morgan Kaufmann, CA · Zbl 0743.68007
[17] Mohar, B., Eigen values, diameter, and Mean distance in graphs, Graphs combin., 7, 53-64, (1991) · Zbl 0771.05063
[18] Robertson, N.; Seymour, P.D., Graph minors. I. excluding a forest, J. combin. theory, ser. B, 35, 39-61, (1983) · Zbl 0521.05062
[19] Robertson, N.; Seymour, P.D., Graph minors. II: algorithmic aspects of tree-width, J. algorithms, 7, 309-322, (1986) · Zbl 0611.05017
[20] Spielman, D.A.; Teng, S.-H., Spectral partitioning works: planar graphs and finite element meshes, () · Zbl 1122.05062
[21] Thomassen, C., Embeddings and minors, () · Zbl 0851.05043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.