3
$\begingroup$

For a given simple graph $G$ with $n$ vertices $v_1,v_2,\dots v_n$, the corresponding degree sequence is $d_1,d_2,\cdots,d_n$. My qusetion is:

How to determine whether there exist subgraphs in $G$ such that it has the degree sequence of $d_1',d_2'\cdots,d_n'$ (where $d_i'\le d_i$)? If exist, how to get it?

(This is an extension of the question at here.)

| cite | improve this question | | | | |
$\endgroup$
5
$\begingroup$

Let $G$ have vertices $v_1,\dots,v_n$. Let $Z(G)$ denote the convex hull in $\mathbb{R}^n$ of all ordered degree sequences $(\deg(v_1),\dots ,\deg(v_n))$ of subgraphs of $G$. One way of stating the well-known Erdős-Gallai characterization of degree sequences of spanning subgraphs of the complete graph $K_n$ is that every integer point in $Z(G)$ with even coordinate sum is a degree sequence of a spanning subgraph of $K_n$. We can then ask for what other graphs $G$ is this statement true. A complete characterization is due to Fulkerson, Hoffman, and McAndrew, Some properties of graphs with multiple edges, Canad. J. Math. 17 (1965), 166-177, namely, no induced subgraph of $G$ consists of two vertex-disjoint odd cycles (with no other edges). Equivalently, every induced subgraph of $G$ has at most one nonbipartite component.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.