Hereditary unigraphs and Erd?s-Gallai equalities

详细信息    查看全文

• 作者：Michael D. Barrus
• 关键词：Chair ; Erd?s&ndash ; Gallai inequalities ; Degree sequence ; Hereditary graph class ; Unigraph
• 刊名：Discrete Mathematics
• 出版年：2013
• 出版时间：6 November, 2013
• 年：2013
• 卷：313
• 期：21
• 页码：2469-2481
• 全文大小：470 K

文摘

We give characterizations of the structure and degree sequence of hereditary unigraphs, those graphs for which every induced subgraph is the unique realization of its degree sequence. The class of hereditary unigraphs properly contains the threshold and matrogenic graphs, and the characterizations presented here naturally generalize those known for these other classes of graphs.

The degree sequence characterization of hereditary unigraphs makes use of the list of values for which the th Erd?s-Gallai inequality holds with equality for a graphic sequence. Using the canonical decomposition of Tyshkevich, we show how this list describes structure common among all realizations of an arbitrary graphic sequence.