Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
This is the definition of degree sequence I have learned in my graph theory course: Are we talking about the same thing? – Paul Jan 24 '12 at 10:15
@Paul: Yes. The point of the question is that the degree sequence records the number of edges connecting each vertex to the rest of the graph, which the OP generalizes to the sequence of numbers of edges connecting each set of $k$ vertices to the rest of the graph, and then asks what happens if $G$ and $H$ have the same generalized degree sequences for all $k$. – Louis Jan 24 '12 at 13:18
@Louis: Oh I see. Thank you for the explanation. – Paul Jan 24 '12 at 13:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.