9
$\begingroup$

The sequence of sizes of single vertex cuts of a graph is called its degree sequence. Is there an agreed-upon name for the sequence of sizes of $k$-vertex cuts? What can be said about two graphs which have the same sequences for all $k? We obviously don't know that they are homomorphic, as that would suggest an easy $\operatorname{O}(2^n)$ algorithm for graph homomorphism (which we don't have), but maybe we know more than nothing?

  • 0
    @Louis: Oh I see. Thank you for the explanation.2012-01-24

0 Answers 0