A short constructive proof of A. R. Rao's characterization of potentially Kr+1-graphic sequences
A short constructive proof of A. R. Rao's characterization of potentially Kr+1-graphic sequences
复制标题
DOI：
10.1016/j.dam.2011.10.015
复制
发表时间：
2012-02
期刊：
影响因子：
--
通讯作者：
Jianhua Yin
中科院分区：
文献类型：
--
作者：
Jianhua Yin
设Kr+1是r+1个顶点的完全图。Rao证明了一个非负整数序列（d1，d2，.，dn）有一个包含Kr +1的子图的实现当且仅当∑i= 1 ndi是偶数，且对所有s和t，0≤s≤r+1且0≤t≤n−r−1，∑i= 1 sdi +∑ i= 1 tdr +1+i≤（s+t）（s+t−1）+∑ i=s+1 r +1 min {s + t，di−r+s}+∑i=r+t+2nmin{s+t，di}。在本文中，我们给出了一个简短的建设性证明，这个特征，可以实现为一个算法来构建一个实现包含Kr+1。
Let Kr+1be the complete graph on r+1 vertices. Rao proved that a non-increasing sequence (d1,d2,…,dn) of nonnegative integers with dr+1≥r has a realization containing Kr+1as a subgraph if and only if ∑i=1ndiis even and ∑i=1sdi+∑i=1tdr+1+i≤(s+t)(s+t−1)+∑i=s+1r+1min{s+t,di−r+s}+∑i=r+t+2nmin{s+t,di} for all s and t with 0≤s≤r+1 and 0≤t≤n−r−1. In this paper, we give a short constructive proof of this characterization that can be implemented as an algorithm to construct a realization containing Kr+1.