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
What do we know about general graph degree sequences?
9
$\begingroup$
graph-theory
-
0This is the definition of degree sequence I have learned in my graph theory course: http://en.wikipedia.org/wiki/Degree_%28graph_theory%29#Degree_sequence Are we talking about the same thing? – 2012-01-24
-
3@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$. – 2012-01-24
-
0@Louis: Oh I see. Thank you for the explanation. – 2012-01-24