论文标题
拆分图和块表示
Split graphs and Block Representations
论文作者
论文摘要
在本文中，我们从它们的顶点度序列和主要晶格的序列的角度研究了图形和相关类别的相关类别。在2003年梅里斯（Merris）的工作之后，我们定义了块$ [α（π）|β（π）] $，其中$π$是图的度序列，而$α（π）$和$β（π）$是$π$产生的序列。我们使用块表示$ [α（π）|β（π）] $来表征以下每个类中的成员资格：不平衡的拆分图，平衡的拆分图，伪切片图和三种Nordhaus-Gaddum图（Collins和Trenk在2013年定义）。与梅里斯（Merris）的工作一样，我们在关系的主要化下形成了一个poset，其中元素是$ [α（π）|β（π）] $，代表具有固定数量边缘的拆分图。我们使用我们所谓的Amphoras以几种有趣的方式对此Poset进行了分区，并证明了由不同的图形家族引起的块的向上和向下闭合结果。最后，我们证明当添加最大和最小元素时，Poset成为晶格，并且我们证明了两个块的遇见和联接的属性。
In this paper, we study split graphs and related classes of graphs from the perspective of their sequence of vertex degrees and an associated lattice under majorization. Following the work of Merris in 2003, we define blocks $[α(π)|β(π)]$, where $π$ is the degree sequence of a graph, and $α(π)$ and $β(π)$ are sequences arising from $π$. We use the block representation $[α(π)|β(π)]$ to characterize membership in each of the following classes: unbalanced split graphs, balanced split graphs, pseudo-split graphs, and three kinds of Nordhaus-Gaddum graphs (defined by Collins and Trenk in 2013). As in Merris' work, we form a poset under the relation majorization in which the elements are the blocks $[α(π)|β(π)]$ representing split graphs with a fixed number of edges. We partition this poset in several interesting ways using what we call amphoras, and prove upward and downward closure results for blocks arising from different families of graphs. Finally, we show that the poset becomes a lattice when a maximum and minimum element are added, and we prove properties of the meet and join of two blocks.
