Let G be an arbitrary spanning subgraph of the complete graph Kr＋1 on r＋1 vertices and Kr＋1-E（G） be the graph obtained from Kr＋1 by deleting all edges of G.A non-increasing sequence π=（d1,d2,...,dn） of nonneg...Let G be an arbitrary spanning subgraph of the complete graph Kr＋1 on r＋1 vertices and Kr＋1-E（G） be the graph obtained from Kr＋1 by deleting all edges of G.A non-increasing sequence π=（d1,d2,...,dn） of nonnegative integers is said to be potentially Kr＋1-E（G）-graphic if there is a graph on n vertices that has π as its degree sequence and contains Kr＋1-E（G） as a subgraph.In this paper,a characterization of π that is potentially Kr＋1-E（G）-graphic is given,which is analogous to the Erdo s–Gallai characterization of graphic sequences using a system of inequalities.This is a solution to an open problem due to Lai and Hu.As a corollary,a characterization of π that is potentially Ks,tgraphic can also be obtained,where Ks,t is the complete bipartite graph with partite sets of size s and t.This is a solution to an open problem due to Li and Yin.展开更多
基金Supported by National Natural Science Foundation of China(Grant No.11161016)
文摘Let G be an arbitrary spanning subgraph of the complete graph Kr＋1 on r＋1 vertices and Kr＋1-E（G） be the graph obtained from Kr＋1 by deleting all edges of G.A non-increasing sequence π=（d1,d2,...,dn） of nonnegative integers is said to be potentially Kr＋1-E（G）-graphic if there is a graph on n vertices that has π as its degree sequence and contains Kr＋1-E（G） as a subgraph.In this paper,a characterization of π that is potentially Kr＋1-E（G）-graphic is given,which is analogous to the Erdo s–Gallai characterization of graphic sequences using a system of inequalities.This is a solution to an open problem due to Lai and Hu.As a corollary,a characterization of π that is potentially Ks,tgraphic can also be obtained,where Ks,t is the complete bipartite graph with partite sets of size s and t.This is a solution to an open problem due to Li and Yin.
