次三次二部图的间隙-[2]-点标号的复杂性

∈联系我们联系我们可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）725-734www.elsevier.com/locate/entcs关于次三次二部图Gap-[2]-点标号的复杂性C. A. 我们是桑托斯2号，C.N. 坎波斯河C. S. Schouery4巴西坎皮纳斯大学计算机学院摘要简单图G =（V，E）的间隙-[k]-点标号是一对（π，cπ），其中π：V（G）1，2，…，k是G的 顶点 的标号分配，cπ：V（G）0，1，.，k是G的一个真顶点着色，使得对于任意vV（G），cπ（v）是由其相邻标号之间的最大差，即最大间隙引起的（d（v）= 1和d（v）= 0的情况分别处理）。2013年，A。Dehghan等人[3]，他们表明，决定一个二部图是否允许 一个缺口-[2]-顶点标记是NP-完全的，并质疑决定三次二部图是否允许这样的标记的计算复杂性。在这项工作中，我们推进了这一类的计算复杂性的研究，证明了这个问题仍然是NP-完全的，即使限制到次立方二部图。保留字：间隙标注、适当标注、图形标注。1介绍设G是一个简单图，其顶点集为V（G），边集为E（G）. 的元素是它的顶点和边。 顶点的度与邻域v∈V（G）分别记为d（v）和N（v），G的最大度记为Δ（G）.G的一个真染色是一个赋值c：V（G）→ C，其中C表示一组颜色，使得对于每个边uv∈E（G），c（u）c（v）。适当的顶点标号是一对（π，c π），其中π：V（G）→ {1，2，.，k}是一个图G的顶点的标号分配和cπ是图G的一个真染色，1本工作得到了CNPqUni versal425340/2016-3、FAPESPT e ma'tico2015/11937-9和CNPq 308689/2017-8的支持。2电子邮件：celso. ic.unicamp.br3电子邮件：campos@ic.unicamp.br4电子邮件：rafael@ic.unicamp.brhttps://doi.org/10.1016/j.entcs.2019.08.0631571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。726C.A. Weffort-Santos等人/理论计算机科学电子笔记346（2019）725的12S1S11S210SS9S4S8S5第13集 第0集S3S7S6（一）（b）第（1）款（c）第（1）款Fig. 1.在（a）中，给出了Petersen图的间隙[3]-点标号;在（b）中，给出了诱导3-着色的次立方二部图的间隙[2]-点标号;在（c）中，给出了不允许3-着色的Heawood图的间隙[2]-点标号。gap-[2]-vertex-labeling. 对于每个顶点，其右下角框内的数字对应于 到其指定的标签通过π通过一些数学函数在标记元素的集合上。在这项工作中，我们讨论了适当的顶点标号的标签间隙诱导大多数作者将真图标号的起源追溯到1967年，当时A. Rosa[7]引入了β-赋值。从那时起，许多不同的标签已被研究。每一个都改变了标签所分配的元素以及颜色是如何被诱导的。事实上，有几个有趣的调查的主题[4，6，10]。关于间隙标记，它们首先由M在2012年作为顶点可区别边标记引入。[8]作为集合和多集合标号的推广[1]。我们在本文中考虑的顶点标记变体定义如下。图G的间隙-[k]-点标号是指图G在集合{1，2，. k}，使得c π：V（G）→ {0，1，.，k}是图G的一个真染色，其中对每个顶点v∈V（G）：（i）c π（v）= 1，如果d（v）= 0;（ii）c π（v）= π（u），u∈N（v），如果d（v）= 1;（iii）c π（v）=max u∈N（v）{π（u）} − min u∈N（v）{π（u）}. 图1（a）和1（b）使用k= 3的双间隙-[k]-顶点标记和k= 2个标签。在后者中观察到，如果图中存在度为1的顶点，则间隙-[k]-顶点-标号可以诱导适当的（k+1）-着色Gap-[k]-顶点标号是由A. Dehghan et al.[3] in 2013.在他们的文章中，作者研究了与某些图族的gap-[k]-顶点标记相关的决策问题的计算复杂性，以及某些图允许这种标记的最小k他们还表明，决定一个给定的图是否允许间隙-[k]-顶点标记是NP-完全的，k≥3。对于k= 2的情形，Dehghan等人证明了这个问题对于3-列图和二分图仍然是NP-完全的，但是如果图是二分图和平面图，那么这个问题可以在多项式时间内解决。他们还证明了每一个r-正则二部图，当r≥4时，都有一个间隙-[2]-顶点标号，并质疑这是否对三次二部图也是如此。围绕二部图的二分法由A. 2016年的Dehghan[2]。作者证明了判定一个平面二部图G是否允许一个间隙-[k]-顶点-0 22111112 01 21 01 3022 12 2102011212 21 2220011122 2C.A. Weffort-Santos等人/理论计算机科学电子笔记346（2019）725727标号使得cπ是G的真2-着色也是NP-完全问题。最近，C.A. 我们研究了一些经典图族的gap-[k]-顶点标记;对这项工作特别感兴趣的是对于这些类，作者刻画了哪些图允许gap-[2]-顶点标号。这些结果意味着间隙-[2]-顶点标记决策问题可以在这些特定情况下在线性时间内解决虽然文献中给出三次）二分图，最初亲，Dehghan et al.[2013年3月日]未知。在这项工作中，我们提出的计算复杂性分析的二部图，表明该问题仍然是NP-完全时，限制到家庭的次立方二部图。我们的主要结果在定理1.1和推论1.2中给出，并在下一节中证明。为了简化符号，我们用G2VL表示判定图是否允许间隙-[2]-顶点-标号的问题定理1.1限制于次三次二部图，G ~ 2 V1是NP-完全的. Q推论1.2G2VL在仅限于亚细胞家族保持NP最小度为2的bic二部图Q2定理1.1的证明给定一个图G=（V，E），单色三角形（MT）问题是：如果存在一个将E划分为两个不相交的集合E1，E2，使得G1=（V，E1）和G2=（V，E2）都不含三角形.Burr在1976年证明了这个问题是NP完全的（尽管这个结果直到1979年才由Garey Johnson发表[5]）。它也可以表述为边着色问题，问题是G是否允许{red，blue}-边着色，使得G中的每个三角形，即G中同构于完全图K3的子图，至少有一个红边边和一个蓝色边。对于实例G， 单色T形，我们表示为T =（t1，t2，...，t p）G中所有p个三角形的（任意但固定的）排序。 另外，我们滥用符号说ti={ex，ey，ez}是G由E（G）的边ex，ey和ez诱导的我们证明定理1.1通过减少单色T三角形到G2VL，多项式时间 等价地，给定一个实例G，单色的TRI-角，我们构造了一个次立方二部图Gj，使得G允许无单色三角形的2-边着色当且仅当GJ允许一个间隙-[2]-顶点-标签。还原是在两个小工具的帮助下完成的：一个三角形小工具和一个否定小工具。第一个图记为GΔ，它是一个辅助简单二部图，有19个顶点，20条边，并描述为： F或三角形ti={ex，ey，ez}，GΔi有：一个顶点u表示G j中的ti∈G;两个相邻顶点vj和wj对于ti中的每条边ej;和一条路径P12，V（P12）={q0，.，q11}。我们还将u连接到每个vj，并添加边wx q0，wy q4和wz q8。图图2（a）说明了三角形的三角形小工具728C.A. Weffort-Santos等人/理论计算机科学电子笔记346（2019）725ΔXX¬XXXX0J12XXJuis3S4 S5 S6QiQ iQiQiQ iQ iQ iQ iQI QiQ iQiv在s0s13的12S11S10v输出w01234567（一）8910 11（b）第（1）款图二、在（a）中，三角形小工具GΔi对于三角形ti={e1，e4，e7};和在（b）中，否定小工具G-。t3={e1，e4，e7}。请注意，在图中，我们用上标i索引小工具的所有 这样做是为了约束三角形小工具GΔi的顶点到G的相应三角形ti。 我们注意到GΔ是二部的，因为它不包含任何奇圈. 此外，由于没有顶点的度大于3，GΔ是次立方的。否定小工具G<$i，j用于连接顶点vi和w，j，b延伸到三角形小工具GΔi和GΔj（不一定是不同的）。 它是一个辅助的简单二分图，通过从图1（c）所示的希伍德图中删除一条边e，并将两个新的顶点vin和w连接到e的端点而获得。 设H是 Heawood图，其中V（H）={s0，...，s13}和e=s0s9。在证明中，我们也将顶点s9称为vout。G的构造产生一个次立方二部图有16个顶点和22条边，如图2所示。第2段（b）分段。顶点vi和wj用vin和w从G<$i，j，分别定义。请注意，执行时，这个操作，vi而WJ在对应的三角形中，gadget的度数为3。我们现在准备展示约简，它将以图G为示于图第3（a）段。 对于每个ti∈T，ti={ex，ey，ez}，添加一个新的三角形小工具GΔ到GJ。 对于每一个1≤i≤p− 1，将边qi qi+1加到GJ。 此外，添加一个我循环C6，V（C6）={c0，...，c5}和边c0q1。11 0其次，设px表示边ex∈E（G）所属的三角形的个数;注意px≤p。 那么，每个ex在GJ中有px个不同的三角形gadgetGΔ，每个它有自己的一对顶点vx和wx。现在，设t，x表示第j个三角形，其中包含e，x在T中.例如，考虑图3（a）中图G的边e9，它属于p9= 2个三角形：t3和t4。那么，t9是T中包含e9的第一个三角形，即t3;类似地，t9是包含e9的第二个三角形，即t3t4.为了完成约简，我们将顶点viWi属于三角形tx分别为vx，l和wx，l。 例如，v5，3是GΔ中的顶点vil5i对应于T中包含边e5的第三个三角形，即t3。然后，使用否定小工具G <$x，（j，j +1）循环连接顶点vx，j和wx，j+1，遵循T中三角形t x的索引。这个过程-以及由此产生的图GJ-如图所3（b）. 我们提请读者注意边缘e5，它属于三个三角形t1，t2和t3 因此，顶点v5， 1，w5， 2与否定vi1vi4vi7wi1wi4wi7S2S7eS1S8C.A. Weffort-Santos等人/理论计算机科学电子笔记346（2019）725729XXL我811011020223332440e6e1e7e5e9e8e2e3e4gadgetG<$5，（1，2），verticesv5，2andw5，3，withG<$5，（2，3）andv5，3andw5，1，withG<$5，（3，1）.注意，如果边ex属于G中的单个三角形ti，则vi和wi是在同一个三角形gadgetGΔi中，并且与否定gadgetG<$x，（i，i）连接，如图像中的边e1，e2，e3，e6，e7，e8和e9所示。这完成了图GJ的构造，图G j是G2VL的次立方二分实例。我们注意到，减少是在多项式时间内完成的输入图G的大小，因为p=O（n3）。用于构造GJ的结构具有重要的性质，这对还原是必要的，因此，对我们的主要结果的证明也是必要的。我们在下面列出了这些性质，并请读者参阅我们的导师桑托斯建议2.1LetGΔi是一个三角形的小玩意儿。 如果GΔi设（π，c π）有一个带隙点标号，且c π（ui）= 1，则π（qi）= π（qi）= π（qi）.0 4 8是的。设GΔi是一个三角形的小工具，假设GΔi允许一个间隙-[2]-顶点-标号使得c π（ui）= 1. 由于小工具是二分的，每个顶点v在V（GΔ）\ {qi}中，d（v）≥2，π在v中诱导的颜色仅有0和1. N_w，每个顶点q_i∈V（GΔi），l_dd，都与顶点u在一个G Δ i的ny二分划。当xqi，l≤9时，cπ（q i） =cπ（ui）=1，L l示于图四 、设a∈ {1， 2}是赋给qi的标号。那 么 ，由于c π（q i）= 1且N（q i）={qi，qi}，我们得出{π（qi），π（qi）}={ 1， 2}，因此，π（qi）=b，b∈ {1，2}\{a}. 类似地，考虑顶点qi和，观察到cπ（qi）= 1，N（q i）={q i，q i}，我们得出π（q i）= a = π（q i）. 根据类似的推理，我们得出结论，对于顶点qi也是如此，结果如下。Q（一）u1u2¬u3u4v12v13v15v25v26v27v31v39v3 v45 9¬v48v44w1w1¬¬2 3w15 ¬5w2w2¬¬¬¬¬¬6w27 1w3w3w395w49w48w44¬年q0年q4年q8Q20Q24第二季第三季8 0年q34年q38年q40年q44年q48（b）第（1）款图3.第三章。（a）单色三角形的实例G：（b）通过约化得到的图G ′。图G<$i，j由符号<$以双线表示;菱形顶点为vout。730C.A. Weffort-Santos等人/理论计算机科学电子笔记346（2019）725IxviyvizIxwiywiz我0QiQi一2 4BQiQiQI一6 8 10BaBQQQQ11XXi、jJuiVWQ我我我1 35我我我7 9 11图四、GΔi的（部分）标记当cπ（ui）=1时。具有诱导颜色1的顶点填充在black中，并且颜色为0的顶点，白色。VertexQI是橙色的，这意味着cπ（q1 1）∈{1，2}。命题2.2LetGJ是一个次三次双粒子代数，其中G<$i，j∈GJ，d（vin）=d（wj）=3。如果GJ有一个间隙-[2]-顶点-标记（π，cπ）使得cπ（vin）=0，则π（vin）π（v out），其中v in= v i，v out∈ V（G<$）.Pr oof（S ket ch）设GJ，G<$i，j如本文所述. GJ有一个空位-[2]-顶点标号使得cπ（v_in）= 0.注意c π（v）∈ {0，1}，对于每个v∈V（G<$i，j）siincedG′（v）=3。此外，由于s0与vin相邻，因此我们可以得出cπ（s0）= 1。因此，对于gadget中的每个sl，cπ（sl）=（l+1）mod 2。这意味着π（si）=π（sj），对于每个i，j∈en。的想法是验证所有可能的标签分配到奇数索引顶点sl，诱导着色cπ。设{a，b}={1，2}。我们首先考虑将标签分配给s0的一些邻居，假设a=π（s1）/=π（s13），如图5所示;注意，这种标签导致cπ（s0）= 1，而不考虑分配给vin的标签。现在，假设π（s3）=b。由于s3，s13∈N（s4）且π（s3）=π（s13）=b，我们得出π（s5）=a. 则由于s1，s5∈N（s6），π（s7）=b. 类似地，我们有s7，s13∈N（s12），这意味着π（s11）=a。剩下的唯一需要标记的奇数索引顶点是s9=vout。然而，如果π（vout）=a，则π（vout）=π（s5）=π（s11），这导致cπ（s10）= 0，与假设相矛盾。这使得我们可以得出结论，我们的最后一个假设，即，π（s3）=b/=π（s1），是不正确的。通过尝试π（s3）=π（s1）并遵循相同的推理，我们得出了类似的矛盾，迫使我们回溯到我们的第一个假设，并得出结论：在GJ的任何这样的间隙-[2]-顶点标记中，π（s1）=π（s13）。最后，我们假设π（vin）=π（vout），并且在知道π（s1）=π（s13）的情况下，我们只需要验证顶点S3的两种可能的标签分配以及它们如何影响诱导着色。 由于两种标记都产生矛盾，结果如下。Q命题2.3设ex是G的一条属于px≥2个三角形的边，x是T中包含e x的第j个三角形。如果GJ允许有一个间隙-[2]-点标号（π，cπ），则对任意p个三角形小配件GΔx，j，GΔx，j+1，r∈C_（？）三角形t x，t x，π（v x，j）= π（v x，j+1）。j j+1证明（略）设G， GJ，（π，c π）和 ex如假设中所述。现在，考虑px三角形gadgets，GΔx，j，其中ich具有verticesvx，j对应于边ex∈t j。然后，每个顶点vx，j通过使用一个否定gadget连接到wx，j+1，顶点wx，j连接到vx，j−1。另外，还记得每个顶点wx，j是QQ不C.A. Weffort-Santos等人/理论计算机科学电子笔记346（2019）725731BB一vout¬vout¬vout一wx，j−1一一wx，jwx，j+1Qx，jQx，j+1L一一BLLSsSs？与顶点vout，v x，j和某个顶点q x，j相邻，l≠ 0（mod 4）;此外，每个q x，j都被命题2.1赋予相同的标签a ∈ {1，2}。假设存在顶点vx，j和vx，j+1，其中{π（vx，j），π（vx，j+1）}={a，b}。一种djust符号，使得π（vx，j） =b。ByProposition2.2，b=π（vx，j） =π（vin）π（vout），其中vout连接vx，j和wx，j+1。因此，N（wx，j+1）被赋予相同的标签a，这导致cπ（wx，j+1）= 0。这是一个矛盾，因为wx，j+1与vx，j+1相邻，而v x，j +1的诱导颜色根据假设为0。我们得出结论：在GJ的间隙-[2]-点标号中，对应于边ex∈E（G）的每个vx，jQ命题2.4设C6<$Gj为约化中构造的. 如果GJ承认了一个缺口-[2]-顶点-labeling（π，cπ），nπ（c3）=a，π（c1）=π（c5）=b，{a，b}={1，2}.证据设GJ如假设中所述，并假设GJ允许有一个间隙-[2]-顶点-标号（π，cπ）.我们用反证法证明了这个结果。设cπ（c3）= 1.这意味着π（c4）/=π（c2）。 根据循环的对称性，我们不失一般性地假设π（c2）= 1。 这意味着π（c0）= 2，因为cπ（c1）=1.类似地，考虑N（c5），我们得出π（c4）= 1，这是一个矛盾。因此，cπ（c3）= 0，这意味着顶点c0，c2和c4都有诱导色1。 设π（c3）=a，对a∈ {1， 2}，我们得到π（c1）=π（c5）=b，S3S4S5S6BaS2S7S1S8一S3S4S5S6BaS2S7BS1S8一S3S4S5S6BaS2S7BS1S8一v在 s0B1312S11S10v输出wv在 s0B1312S11S10v输出wv在s0 S13的12一第十一季第十v输出w（一）（b）第（1）款（c）第（1）款图五、 情况π（s1）π（s1 3）。在（a）、（b）和（c）中，vertexs3已被指定为标签b，其中h确定分别将标签分配给顶点S5、S7和S11。 在所有图中，以橙色突出显示的边缘和标签是那些强制标签的边缘和标签，这些标签以红色突出显示。此外，我们将黑色顶点表示为诱导颜色为1的顶点，将白色顶点表示为颜色为0的顶点txtxtxtxtx1vx，1...j−1vx，j−1Jvx，jj+1vx，j+1...pxvx，pxwx，1BBvout一Wp¬XXvout732C.A. Weffort-Santos等人/理论计算机科学电子笔记346（2019）725图第六章 两个顶点vx，j和vx，j+1分别用b和a表示。 当观察到v e rtexwx，j+1时，在该标记中，将具有诱导颜色0时，实现了该矛盾。C.A. Weffort-Santos等人/理论计算机科学电子笔记346（2019）725733JXX1111XXXL我LLb ∈ {1，2}\ {a}.这两种情况都在图中说明。第七章Q了c0c5c1B bc4c2C3（一）一C3（b）第（1）款图第七章 在（a）中，c3与诱导颜色1;和，在（b）中，颜色0。 Bla ck顶点具有诱导颜色1和白色顶点，颜色0。为了证明次三次多项式的单色T三角≤pG2VL，二部图，我们证明了以下索赔。2.5如果G允许边着色c：E（G）→ {red，blue}使得没有三角形是单色的，则G允许有一个间隙-[2]-顶点标号。证明（略）设G，GJ如前所述，并假设G有一个{红，蓝}边着色c，且不含单色三角形. 另外，设{A，B}为GJ使得顶点vi∈A.图2和图3A和B部分的顶点分别为白色和黑色。定义G的一个标号π：V（G）→ {1， 2}如下。首先，将标签1分配给每个在B部分中使用。 现在，考虑一下A部分的证明。F或每个顶点vi∈GΔi（对应于边ex∈E（G）），如果c（ex）= red，且π（vx）= 2，则指定π（v x）= 1，否则，请执行以下操作。 F或否定小工具G<$i，j，将label：（a，b，b，b，a，a，a）分配给顶点（第1条，第3条， . . . . . . ，s1 3），其中b=π（vi）anda∈{1，2} \{b}. F或顶点qi∈P12<$GΔ，设π（qi）= 1，如果l≠0（mod 4），π（qi）= 2，如果l≠2（mod 4）。最后，分配π（c1）=π（c5）= 2和π（c3）= 1。 像往常一样定义着色cπ为了证明（π，cπ）是GJ的一个间隙-[2]-点标号，本文证明了cπ是GJ的一个真点染色. 首先，由于部分中的每个顶点B有相同标号，GJ连通，每个顶点v∈A都有诱导色cπ（v）= 0.因此，它仍然要考虑B中顶点的诱导色。在P12→GΔi中，C6环的诱导着色是可能的和否定小工具G<$i，j来观察ve，颜色0和1在这些顶点中交替，结构（除了G Δ p中的顶点qp，其颜色为cπ（qp）∈{1，2}）。根据性质2.2和2.3，对于任意i∈GΔi的顶点，（至少）two邻居，即vx和vout∈V（G<$），标签为π（vx）π（v输出）。因此，我们认为，我我c π（w i）= 1。为了完成证明，请注意，由于G中的每个三角形都不是单色的，因此ti={ex，了c02C5C1C421 C2734C.A. Weffort-Santos等人/理论计算机科学电子笔记346（2019）725ey，ez}的边被着色，使得{c（ex），c（ey），c（ez）}={ red， blue}。 这意味着{π（vi），π（vi），π（vi）}={ 1， 2}在每个三-角度小工具GΔi∈GJ，其中ch又诱导cπ（ui）=1。我们得出结论，cπ是一个C.A. Weffort-Santos等人/理论计算机科学电子笔记346（2019）725735X11X不XyzXyzG的适当着色，结果如下。Q2.6如果GJ允许一个间隙-[2]-顶点-标号，则G允许一个边-着色c：E（G）→ {red，blue}使得没有三角形是单色的。证明（草图）设GJ，（π，cπ）如假设中所述，设{A，B}为aV（GJ）的双分拆，其中vi∈A.根据命题2.4，圈C6<$GJ具有唯一的gap-[2]-vertex-labeling定义了GJ中度至少为2的每个顶点的诱导色：A中的顶点诱导色为0，B\ {qp}中的顶点诱导色为1。Now，由于ui∈GΔib∈B，我们知道cπ（ui）=1。更进一步，因为N（u i）={v i，v i，v i}，我们有{π（v i），π（v i），π（v i）}={1，2}。然后，定义一个{红色，blue}-G的边着色如下。对于每条边ex，指定c（ex）= red，如果π（v x）= 1且c（e x）=蓝色，否则。 根据命题2.3，每个vi都接收到相同的标签，因此没有边ex被分配两种颜色。 因此，我们有{c（ex），c（ey），c（ez）}={ red， blue}在每个三角形ti={ex，ey，ez}中，并且每个ti至少有一条边着色为红色，另一条着色为蓝色。Q通过结合权利要求2.5和2.6，我们得出MT ≤pG2 VL（仅限于次三次图），从而完成定理1.1的证明。现在，考虑对前面描述的减少进行以下修改。移去顶点qp，qp和qp从GΔp，即路径P12中的最后三个顶点9 10 11在GJ的最后一个三角形小工具中。 把得到的图G称为JJ。注意，这个图是δ（GJJ）= 2的次立方图。 然而，这种修改不改变用于证明定理1.1的G j的任何性质。因此，下面的推论1.2成立。推论1.2G2VL在仅限于亚细胞家族保持NP最小度为2的bic二部图Q3结束语和未决问题gap-[k]-顶点标号问题在图标号领域中是相当新的。目前正在从计算复杂度和算法两个角度对它在前者中，当k≥3时，该问题已被证明对一般图是NP-完全的。后一种方法已经表明，对于某些图族（例如圈、树、冠、轮、单圈图和一些snark族），可以决定它们是否允许在线性时间内进行这样的标记。此外，有已知的结果，最佳间隙-[k]-顶点标记这些家庭，即标记使用最少数量k的标签，以便诱导一个适当的着色图。也有一些图类的发现，不允许任何间隙-[k]-顶点-标签，任何k∈N，如完全图的阶n≥4和一些权力的道路和循环。特别是，对于k= 2，二分图族已被证明是相当具有挑战性的。已知判定一个二部图是否允许有一个间隙-[2]-顶点-标号一般是NP-完全的，但对于以下情况可以在多项式时间内解决：736C.A. Weffort-Santos等人/理论计算机科学电子笔记346（2019）725一些子族，如平面二部图和r≥4的r-正则图。我们的主要结果表明，即使仅限于次立方二部图的家庭，这个问题仍然是NP-完全的。此外，如果这些图的最小度为2，则该问题仍然是NP-完全的.因此，度为1的顶点的存在（或缺乏）似乎并不便于决定亚立方二部图是否允许间隙[2]-顶点标号。这个结果与已知的gap-顶点-labelable图的结果相反，因为在许多情况下，度1顶点的存在有助于某些图的gap-[k]-顶点-labeling每一个二分冠允许一个间隙-[2]-顶点标记，而这不是每一个偶数长度的循环的情况。最后，我们提出以下问题。为什么一次顶点有（显然）没有影响的硬度G2VL？ 此外，虽然问题仍然是NP-完全的次立方二部图，可以结构三次图的性质可以用来决定是否以及何时这些图允许间隙- [2]-顶点标号？引用[1] Chartrand，G.，F. Okamoto，E. Salehi和P. Zhang，图的多集色数，Mathematica Bohemica134（2009），pp. 191-209.[2] Dehghan，A.，关于强平面不全相等3SAT，组合优化杂志32（2016），pp。721URLhttps://doi.org/10.1007/s10878-015-9894-6[3] Dehghan，A.，M. Sadeghi和A.Ahadi，适当标记问题的数学复杂性，理论计算机科学495（2013），pp.25[4] Gallian，J.一、图标记的动态调查，组合数学电子杂志（2018）。[5] Garey，M. R.和D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP- H. 弗里曼公司，美国纽约州纽约市，1979年。[6] 别这样，S。C. 和F. A. Mun taner-Batle，“优雅，和谐和神奇的T y p e La belings-关系和技术”，斯普林格数学简报。Springer International Publishing，2017.[7] Rosa，A.，关于图的顶点的某些赋值，图的理论（国际研讨会，罗马）（1967年），pp。349[8] Tahraoui，M. 一、E. Du chene和H. Kheddouci，Gap vertex-distinguishingedgecoloringsofgraphs，离散数学312（2012），pp. 3011[9] 我们是桑托斯C.一、“Proper gap-labellings: on the edge and vertex variants,” Master’s thesis, Universityof Campinas[10] 张，P.，“Color-Induced Graph Colorings，”Springer Briefs in Mathematics. Springer InternationalPublishing，2015.