




















We present new short proofs of known spanning tree enumeration formulae for threshold and Ferrers graphs by showing that the Laplacian matrices of such graphs admit triangular rank-one perturbations. We then characterize the set of graphs whose Laplacian matrices admit triangular rank-one perturbations as the class of special 2-threshold graphs, introduced by Hung, Kloks, and Villaamil. Our work introduces (1) a new characterization of special 2-threshold graphs that generalizes the characterization of threshold graphs in terms of isolated and dominating vertices, and (2) a spanning tree enumeration formula for special 2-threshold graphs that reduces to the aforementioned formulae for threshold and Ferrers graphs. We consider both unweighted and weighted spanning tree enumeration.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。