Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 4 down vote favorite

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|improve this question
This is the definition of degree sequence I have learned in my graph theory course: en.wikipedia.org/wiki/Degree_%28graph_theory%29#Degree_sequence Are we talking about the same thing? – Paul Jan 24 '12 at 10:15
2  
@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

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.