论文标题
最多有8个节点的所有图是2个interval-pcgs
All Graphs with at most 8 nodes are 2-interval-PCGs
论文作者
论文摘要
图G是一个多间隔的PCG，如果存在一个边缘加权树T，具有非负实际值的边缘加权树t和非阴性实际半行的脱节间隔，以便G的每个节点与T叶的叶子唯一相关，并且G时G中的两个节点之间存在两个节点之间的边缘，则仅当其在T lee中的相应叶子之间的距离之间仅具有相应的距离。如果间隔的数量为k，则称该图为K interval-PCG；在符号中，g = k-interval-pcg（t，i1，……ik）。众所周知，2个间隙PCG不包含所有图形，并且此类外部最小的已知图具有135个节点。在这里，我们证明所有最多有8个节点的图都是2个interval-pcgs，因此朝着确定n的最小值迈出了一步，以使得存在一个不是2个interval-pcg的n节点图。
A graph G is a multi-interval PCG if there exist an edge weighted tree T with non-negative real values and disjoint intervals of the non-negative real half-line such that each node of G is uniquely associated to a leaf of T and there is an edge between two nodes in G if and only if the weighted distance between their corresponding leaves in T lies within any such intervals. If the number of intervals is k, then we call the graph a k-interval-PCG; in symbols, G = k-interval-PCG (T, I1, . . . , Ik). It is known that 2-interval-PCGs do not contain all graphs and the smallest known graph outside this class has 135 nodes. Here we prove that all graphs with at most 8 nodes are 2-interval-PCGs, so doing one step towards the determination of the smallest value of n such that there exists an n node graph that is not a 2-interval-PCG.
