论文标题
关于三方图和n-Partite图的存在
On the existence of tripartite graphs and n-partite graphs
论文作者
论文摘要
图的度序列是其顶点程度的序列。如果$π$是图$ g $的度序列，则$ g $是实现$π$，$ g $实现$π$。确定一个正整数序列何时可以将一个简单图的度序列实现，这引起了很多关注。 Erdös和Gallai的早期结果之一，表征了图的度序列。 Hakimi和Havel加强了结果。 Cai等人得出了另一个概括。 Hoogeveen和Sierksma列出了七个标准，并提供了统一的证明。此外，大风和雷克尔通过使用网络流独立建立了表征。我们将大风和Ryser的结果从两部分图形扩展到三方图形，甚至将$ n $ - 分段图扩展到。作为推论，我们给出了必要的条件和足够的条件（σ_1，σ_2，σ_3）$，可以通过三方图实现，其中$σ_1$，$σ_2$和$σ_3$都是所有非内在整体序列的序列。我们还为$（σ_1，σ_2，σ_3）$提供了更强的必要条件，可以通过三方图实现。
The degree sequence of a graph is the sequence of the degrees of its vertices. If $π$ is a degree sequence of a graph $G$, then $G$ is a realization of $π$ and $G$ realizes $π$. Determining when a sequence of positive integers is realizable as a degree sequence of a simple graph has received much attention. One of the early results, by Erdös and Gallai, characterized degree sequences of graphs. The result was strengthened by Hakimi and Havel. Another generalization is derived by Cai et al. Hoogeveen and Sierksma listed seven criteria and gave a uniform proof. In addition, Gale and Ryser independently established a characterization by using network flows. We extend Gale and Ryser's results from bipartite graphs to tripartite graphs and even $n$-partite graphs. As corollaries, we give a necessary condition and a sufficient condition for the triple $(σ_1, σ_2, σ_3)$ to be realizable by a tripartite graph, where $σ_1$, $σ_2$ and $σ_3$ are all non-increasing sequences of nonnegative integers. We also give a stronger necessary condition for $(σ_1, σ_2, σ_3)$ to be realizable by a tripartite graph.
