文摘

亲切的标签图 是一个双射 这样的优势 1如果分配标签 或 ,对于一些 和标签0否则,满足边的数量用0和边的数量标记标示1最多相差1。图,承认权力亲切标签被称为权力亲切图。在这篇文章中,我们得到一些权力特征的亲切的图表以及探索电力亲切标签np完全问题。这项工作也排除了任何禁止的子图表征电力亲切标签的可能性。

1。介绍

我们开始用一个简单的、有限的和无向图 。顺序、大小和数量的图形的周长是顶点,边的数量,和最短周期的长度包含在图,分别。一个图是triangle-free如果没有三个顶点形成一个循环。一个图 - - - - - -cycle-free如果没有顶点形成一个循环。所有标准术语、符号和术语没有定义,我们指的是克拉克和霍尔顿(1]。我们将给一个简短的总结有用的定义目前调查。

定义1。图表标签是一个整数分配给顶点或边或受到某些条件(s)。如果域的映射是顶点的集合(边缘),那么标签被称为顶点标签(标签)的优势。
书目引用以及一个广泛的调查各种图的标号,我们指的是盖伦2]。
标记图应用在许多不同的领域如编码理论、通信网络,确定最佳的电路布局。研究不同图的标号的各种各样的应用程序已经被Yegnanarayanan探索和•韦迪雅那桑3]。
2022年,Barasara和塔迦尔(4]介绍了权力的亲切标签图,定义如下:

定义2。对于一个图 ,亲切的标签被定义为一个双射的力量 这样引起的边缘标记功能 是由以下几点: 满足条件的 ,在哪里和边的数量是用0和1标记,分别。承认权力亲切标签的图称为权力亲切图。
在同一篇论文中,我们研究电力亲切标签路径,循环,完成图,轮,蝌蚪,完成两偶图 ,完成两偶图 ,明星,bistar。在[5),我们已经讨论了执掌权力亲切标签,花朵,装备,风扇,和宝石图以及从明星获得较大的图表和bistar使用图形操作。在[6),我们得到的结果与权力的亲切标签图顶点的上下文切换操作。
有三种类型的问题,可以认为是在这个领域,如下:(1)情意是如何影响在各种图形操作(2)构建新的家庭权力的亲切图通过寻找合适的标签(3)给定一个图的理论属性 ,描述图的类属性权力的亲切并非所有的图形都是权力的亲切图表,有趣的是研究图的理论属性影响或影响权力亲切标签。
在本文中,我们专注于第三种类型的问题。节2,我们给出一些权力亲切的性格特征图。而在部分3的上下文中,我们研究np完全问题权力亲切标签。

2。一些权力亲切的性格特征图

在本节中,我们将讨论嵌入在权力的亲切标签和得到一些权力特征的亲切的图表。

定理3。任何图可以嵌入作为诱导子图的力量亲切图。

证明。让的图顶点,边缘。指定的标签 的顶点 。
让与标签的边缘和 。
我们考虑以下三种情况:案例1:如果 。权力的亲切的定义标签的图,是一个权力亲切图。案例2:如果 。新的图可以通过添加顶点的图 ,说 加入他们的顶点标签1。指定的标签 的顶点为 。因此,边缘会收到标签1。因此, 。案例3:如果 。新的图可以通过添加的道路顶点,说 的图并加入顶点顶点的标签 。指定的标签 的顶点为 。因此,边缘会收到标签0。因此, 。因此,在例2和例3中,构造超图满足条件的权力亲切图。
因此,任何图可以嵌入作为诱导子图的力量亲切图。

推论4。任何树可以嵌入作为诱导子图的力量亲切树。

证明。如果是一棵树,那么超图吗建于定理3是一个亲切的树。因此,结果。

推论5。任何非循环(单循环的)图可以嵌入一个无环的诱导子图(一个单循环的)力量的亲切图。

证明。如果是一个非循环图(一个单循环的),然后超图吗建于定理3是一个非循环(一个单循环的)力量的亲切图。因此,结果。

推论6。任何triangle-free ( - - - - - -周期免费)图可以嵌入triangle-free作为诱导子图(一个吗 - - - - - -周期免费)权力亲切图。

证明。如果是一个triangle-free ( - - - - - -周期免费)图,超图建于定理3是一个triangle-free ( - - - - - -周期免费)权力亲切图。因此,结果。

推论7。任何图在周长可以嵌入作为诱导子图的力量亲切图吗在周长 。

证明。如果是一个图形周长 ,然后超图建于定理3是一个权力亲切图形周长 。因此,结果。

推论8。任何平面(连接)图可以嵌入作为诱导子图的平面(连接)权力亲切图。

证明。如果是一个平面(一个连接图,超图建于定理3是一个平面(一个连接图。因此,结果。

定理9。给出一个正整数 ,有一个权力亲切图 ,已顶点。

证明。我们将在以下两种情况:证明结果案例1: 是奇数。构造一个包含路径 顶点 。标签路径的顶点和 ,分别。因此,边缘将收到标签1和其他边缘吗为 将收到标签0。取 顶点 和标签 ,分别。现在,加入这些顶点到顶点 。然后,所以得到的图表顶点,边缘。此外,我们定义了会引起标签模式 与标签边缘0和1。因此,满足条件 。因此,合成图是一个权力亲切图。案例2: 是偶数。构造一个包含路径 顶点 。标签路径的顶点和 ,分别。因此,边缘将收到标签1和其他边缘吗为 将收到标签0。取 顶点 和标签 ,分别。现在,加入这些顶点到顶点 。然后,所以得到的图表顶点,边缘。此外,我们定义了会引起标签模式 0和边缘与标签 边缘与标签1。因此,满足条件 。因此,合成图是一个权力亲切图。因此,给定一个正整数 ,有一个权力亲切图 ,已顶点。

为 ,一个图表与10个顶点及其权力亲切标签如图1。

定理10。如果甚至是一个权力的亲切图大小,那么也是一种权力亲切图吗 。

证明。让是权力的大小亲切图 。然后, 。让有任何优势 。如果标签0呢有 。如果标签1呢有 。因此,满足条件 。因此,是一个权力亲切图。
因此,如果甚至是一个权力的亲切图大小,那么也是一种权力亲切图吗 。

定理11。如果是一个权力亲切图奇怪的大小,那么也是一种权力亲切一些图吗 。

证明。让 是权力的大小亲切图 。然后,要么 或 。如果 ,然后删除边这是标记为0,如果 ,然后删除边标记为1的 。在这两种情况下,有 。因此,满足条件 。因此,是一个权力亲切图。
因此,如果是一个权力亲切图奇怪的大小,那么也是一种权力亲切一些图吗 。

定理12。让是一个亲切图的大小和力量 ,然后添加一个任意两个不相邻的顶点之间的边也是一种权力亲切图。

证明。让是权力的大小亲切图 。然后, 。构造新的图通过添加一条边任意两个不相邻顶点之间 。将收到标签边缘0或1。如果收到标签0,那么有 。如果收到标签1,那么有 。在这两种情况下,满足条件 。因此,是一个权力亲切图。
因此,对是一个亲切图的大小和力量 ,然后添加一个任意两个不相邻的顶点之间的边也是一种权力亲切图。

定理13。让是任何权力的亲切图秩序和是一个两偶图分为两部分 与 和 。这个图通过识别的顶点在标签1和的顶点有标签作为最大的质数这样 在 。然后,是一个权力亲切图。

证明。让是任何权力的亲切图秩序 。让和顶点有标签1和的最大素数 ,分别在图 。
让 的分为两部分这样 和 。然后,分配标签 的顶点 ,分别。
然后,确定顶点和的与和 ,分别。让图得到 。案例1:为 。的标签 ,为每一个 ,不包含的力量吗 。因此,所有的边缘事件和将收到标签1和所有的边缘事件和将收到标签0。的边缘同样有助于和在 。因此,是一个权力亲切图。案例2:为 。让是最大的质数,这样 。假设有标签 。然后,交换的标签和 。然后,根据案例1,是一个权力亲切图。因此,是一个权力亲切图。

周期和图和他们的权力亲切标签如图2。

定理14。让与尺寸图 。如果有一个顶点这样 ,然后是一个权力亲切图。

证明。让图的大小和的顶点这样 。
我们考虑两种情况如下:案例1:当是偶数。分配标签1到顶点和标签剩余的顶点,他们不产生边缘标签1(除了结束的边缘有一个顶点 )。然后, 和 。因此,满足条件 。案例2:当是奇数。子用例1:当 。分配标签1到顶点和标签剩余的顶点,他们不产生边缘标签1(除了结束的边缘有一个顶点 )。然后, 和 。因此,满足条件 。子用例2:当 。分配标签1到顶点和标签剩余的顶点,他们不产生边缘标签1(除了结束的边缘有一个顶点 )。然后, 和 。因此,满足条件 。因此,根据情况1和情况2,图是一个权力亲切图。

3所示。一些np完全问题的权力亲切图表

大部分的决策问题分为四种类型:P, NP,非完全多项式和赋权。虽然可以验证解决方案很快一个np完全问题,但是不存在有效的算法达到快速的解决方案。许多图形理论等问题找到支配集,分配适当的顶点着色,并找出最长的路径图是np完备性。更多细节可以在[7]。

Acharya et al。8)派生的,每一个图表可以嵌入作为诱导子图的优美的图,因此显示不可能获得任何禁止优美图的子图描述。在同一行,Acharya et al。9,10),Sethuraman et al。11),种子和Ajitha12),Ichishima et al。13],饶和Sahoo [14],Vaidya和Barasara [15,16],Vaidya和Vihol [17],Anandavally et al。18]讨论了嵌入和np完全问题的背景下,各种图表标签计划。

在本节中,我们研究一些np完全问题的权力亲切标签。

定理15。决定是否色号的问题 ,在哪里 ,甚至是np完全的权力亲切图。

证明。让图的色数 。让电力亲切超图的构造定理3,其中包含G作为诱导子图。然后, 。自从决定是否色号的问题 ,在哪里 ,由(非完全多项式7]。由此可见,决定是否色号 ,在哪里 ,非完全多项式甚至是对权力的亲切图表。因此,结果。

定理16。决定是否集团数量的问题 是np完全即使限制权力的亲切图。

证明。以来的问题决定是否派的一个图表 由(非完全多项式7), 超图的建于定理3就是力量的亲切。因此,结果。

定理17。的问题决定是否支配数量(总支配数)图小于或等于什么是np完全即使限制权力的亲切图。

证明。自从决定是否控制数量的问题(总支配数)图小于或等于什么非完全多项式,报道(7]。的超图建于定理3就是力量的亲切,其统治数量大于或等于统治的 。因此,结果。

4所示。结论

在这篇文章中,我们已经得到任何nonpower亲切图可以嵌入在一个权力亲切图和获得权力的亲切图的一些特征。我们还讨论了一些np完全问题亲切标签,这排除了禁用子图表征对权力的可能性亲切标签。获得相似的结果为其他图表标签计划是一个开放的研究领域。

数据可用性

没有数据被用来支持本研究的发现。

信息披露

目前工作所进行的研究工作的一部分次要的研究项目。HNGU UGC / 5658/2023,日期:1月4日,2023年古吉拉特邦Hemchandracharya北大学的帕坦(古吉拉特邦),印度。

的利益冲突

作者宣称没有利益冲突有关的出版。