





















Many extremal problems for graphs have threshold graphs as their extremal examples. For instance the current authors proved that for fixed $k\ge 1$, among all graphs on $n$ vertices with $m$ edges, some threshold graph has the fewest matchings of size $k$; indeed either the lex graph or the colex graph is such an extremal example. In this paper we consider the problem of maximizing the number of matchings in the class of threshold graphs. We prove that the minimizers are what we call \emph{almost alternating threshold graphs}. We also discuss a problem with a similar flavor: which threshold graph has the fewest independent sets. Here we are inspired by the result that among all graphs on $n$ vertices and $m$ edges the lex graph has the most independent sets.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。