Alpha graphs with different pendent paths
Alpha graphs with different pendent paths
复制标题
具有不同悬垂路径的 Alpha 图
DOI：
10.5614/ejgta.2020.8.2.8
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Christian Barrientos
中科院分区：
文献类型：
--
作者：
Christian Barrientos
优美标号是求完全图和完全二部图循环分解的有效工具。最强的优美标号α-标号是图标号研究领域的中心，一个图的α-标号的存在意味着该图存在几个明显不相关的其他标号。此外，具有α-标号的图可以组合成新的图，这些新的图也允许这种类型的标号。联合收割机的标准方法是将基图的每个顶点与另一个图的顶点标识。这些方法的共同点是，所有涉及的图（可能除了基）都具有相同的大小。在本文中，我们做了一些不同的工作，我们证明了一棵树的α-标号的存在性，该树是通过将不同长度的路附加到基路的顶点上而得到的，使得悬垂路的长度形成一个差为1的等差序列，其中基路的连续顶点被标识为长度是序列的连续元素的路。这些α-树以几种方式组合以生成新的α-树族。我们还证明了这些树可以用来创建具有α-标号的单圈图。此外，我们还证明了悬垂路可以被等价的α-树代替，从而产生新的α-树，从而得到一个相当鲁棒的α-树类.
Graceful labelings are an effective tool to find cyclic decompositions of complete graphs and complete bipartite graphs. The strongest kind of graceful labeling, the α-labeling, is in the center of the research field of graph labelings, the existence of an α-labeling of a graph implies the existence of several, apparently non-related, other labelings for that graph. Furthermore, graphs with α-labelings can be combined to form new graphs that also admit this type of labeling. The standard way to combine these graphs is to identify every vertex of a base graph with a vertex of another graph. These methods have in common that all the graphs involved, except perhaps the base, have the same size. In this work, we do something different, we prove the existence of an α-labeling of a tree obtained by attaching paths of different lengths to the vertices of a base path, in such a way that the lengths of the pendent paths form an arithmetic sequence with difference one, where consecutive vertices of the base path are identified with paths which lengths are consecutive elements of the sequence. These α-trees are combined in several ways to generate new families of α-trees. We also prove that these trees can be used to create unicyclic graphs with an α-labeling. In addition, we show that the pendent paths can be substituted by equivalent α-trees to produce new α-trees, obtaining in this manner a quite robust category of α-trees.