On the existence of N-connected graphs with prescribed degrees (n ≧ 2)
On the existence of N-connected graphs with prescribed degrees (n ≧ 2)
复制标题
DOI：
10.1002/net.3230030303
复制
发表时间：
1973
期刊：
影响因子：
2.1
通讯作者：
Danielle Wang;D. Kleitman
中科院分区：
文献类型：
--
作者：
Danielle Wang;D. Kleitman
在本文中，我们提供了一个简单的算法来构造一个n-（顶点）连通图，该图没有多条边或多个度序列满足以下条件的环。我们证明这些是必要的和充分的存在这样的图。我们的算法包括分阶段构建图。一个显式的构造给出了如果所有的度都是n或n+1。否则，我们选择一个最大或最小度的顶点，并将其与其余具有最大度的顶点的集合连接，为图的其余部分留下剩余度序列，然后可以通过迭代来构建。如果连通后的剩余度都至少为n，则连通上面最小度的顶点。否则，我们连接最大程度的顶点。关于度序列的条件是它必须是可实现的，所有的度必须至少是n，并且可以避免触及n-1个最大度顶点的边的数量足以在其他顶点之间形成树。
In this paper we provide a simple algorithm for constructing an n- (vertex) connected graph with no multiple edges or loops having degree sequence satisfying the conditions indicated below. We prove these to be necessary and sufficient for the existence of such a graph. Our algorithm consists of constructing the graph in stages. An explicit construction is given if all degrees are n or n+1. Otherwise we choose a vertex with either the largest or smallest degree and connect it with a set of the remaining vertices having largest degrees, leaving a residual degree sequence for the rest of the graph which later can then be constructed by iteration. We connect the vertex of smallest degree above if the residual degrees after its connection are all at least n. Otherwise we connect the vertex of largest degree. The conditions on the degree sequence are that it must be realizable by a graph, all degrees must be at least n, and the number of edges which can avoid touching the n-1 largest degree vertices are sufficient to form a tree among the other vertices.