Journal of Graph Algorithms and Applications Recognition of Unigraphs through Superposition of Graphs

Journal of Graph Algorithms and Applications Recognition of Unigraphs through Superposition of Graphs
复制标题

图算法与应用杂志 通过图的叠加进行单图识别

DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
R. Petreschi
R. Petreschi
中科院分区：
--
文献类型：
--
作者：
A. Borri;T. Calamoneri;R. Petreschi;S. Das;R. Uehara;A. Borri;T. Calamoneri;R. Petreschi

文献摘要

被引文献

相似文献

唯一图是由其自身的度序列唯一确定直至同构的图。本文引入了一种单图的结构描述：将点集划分为三个不相交的集合，将边集划分为两类。这个特征使我们能够设计一个新的线性时间识别算法，递归地修剪图的度序列。该算法检测两个特定的图，其叠加生成给定的unigraph。图1：单图的子类之间的包含关系。
Unigraphs are graphs uniquely determined by their own degree sequence up to isomorphism. In this paper a structural description for unigraphs is introduced: vertex set is partitioned into three disjoint sets while edge set is divided into two different classes. This characterization allows us to design a new linear time recognition algorithm that works re-cursively pruning the degree sequence of the graph. The algorithm detects two particular graphs whose superposition generates the given unigraph. Threshold Split Matrogenic Matroidal Matrogenic Unigraph Figure 1: Relationships of inclusion among the subclasses of unigraphs.