≥可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）355-367www.elsevier.com/locate/entcs极小最大距离问题Fernanda Couto2巴西里约热内卢新伊瓜苏联邦农村大学费利佩岛库尼亚3号里约热内卢联邦大学计算机系统工程项目巴西里约热内卢摘要图G的一棵树t-树是G的一个生成子树T，其中G的任意两个相邻顶点之间的距离至多为t。 使G有树t-k的最小的t称为树伸展指数.本文研究了树木伸展指数的确定问题，上界，例如，基于围长值和最小直径生成树问题，分别;并提出一些类，其中t是一个紧值。1995年，MSST的计算复杂度被确定为NP-困难，4，对于t= 2，多项式时间可解。然而，如果t= 3仍然是一个悬而未决的问题。在这项工作中，我们证明了很少有P4的考虑（k，l）-图，这是那些图其顶点集可划分为k个独立集和l个团，我们对PvsNP-对于这样的决策版本的完全二分法。虽然我们证明了（2， 1）-图的MSST是NP-难的，并且事先知道确定弦图的拉伸指数也是NP-难的，但是我们给出了（2， 1）-弦图的树拉伸指数我们还解决了MSST的功率循环图是一个有趣的类，从两个不同的角度来看：它们是（0，l）-图族，我们证明了当l是关于图的大小的线性函数时，确定这类图的拉伸指数是NP-困难的;同时，它们的拉伸指数远离由围长给出的自然下界，并且关于直径生成树上界是紧的关键词：拉伸指数，少P4的图，（k，l）-图，（2，1）-弦图，PvsNP-c二分法.1本研究部分由CAPES、CNPq和FAPERJ2电子邮件：fernandavdc@ufrrj.br3电子邮件：lfignacio@cos.ufrj.brhttps://doi.org/10.1016/j.entcs.2019.08.0321571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。356F. 库托，L.F.I.Cunha/Electronic Notes in Theoretical Computer Science 346（2019）3551引言寻找具有顶点距离约束的生成树的问题图G的一棵树t-1是G的一棵生成子树T，其中每对顶点之间的距离至多是它们在G中的距离的t倍，或者等价地，它是G的一棵生成子树T，其中两个相邻顶点之间的距离至多是t（参见图1）。[7]）。如果一个图有树t-可容许图，则称它为树t-可容许图（或简称为t-可容许图）. 树t-T的参数t称为树拉伸因子，记为σ（T），图G是t-容许的最小t是图G的树拉伸指数，记为σT（ G ） 。注 意确 定 G 的 树 拉 伸 指 数 的 问 题 ， 称 为 最 小 拉 伸 生 成 树 问 题（MSST），是一个有趣的极小-极大问题，它不仅在图中被研究，而且在其他几个组合问题中也被研究，以这种方式，边界，算法和计算复杂性研究得到了广泛的发展[1，11]。从现在开始，当我们提到MSST时，我们正在处理这样一个问题的决策版本此外，由于不连通图没有生成树，树是唯一的1-容许图，我们只考虑连通图和与树不同的图考虑周长g（G），可以获得拉伸指数的下限，即，图G的最小圈的长度如果G是t-容许的，则t≥g（G）−1，对于某些类，例如完全图、圈图、轮图或完全r-部图，当r≥2时，t是紧值然而，建立下界并不是一个简单的任务，即使处理仅限于图类的MSST毕竟，关于它的绝大多数结果都涉及图的可容许性（cf. [7]）。另一方面，最小直径生成树产生拉伸指数的上界。在这个多项式时间可解问题中，解参数，比如DT（G），对应于G的最小直径生成树的直径[13]。定理1.1[7，13]给定G的围长g（G），我们有g（G）−1≤σT（G）≤D T（G）.当我们想确定一个图是否是t-可容许的时，一个有趣的方面就出现了就计算复杂度而言，这个任务仍然是我们旨在解决的最大突破，因为判定σT（G）≥4是NP-完全的，而2-容许图是多项式时间可识别的[7]，并且判定3-容许图是仍然是一个悬而未决的问题。也有一些类，这个问题被解决为NP-完全的，作为二分和弦与有界直径图[5，6]，或类的拉伸指数被证明是有界的特定值，作为分裂和上图（参见。 [16]）。仍然在计算复杂性方法中，定理1.2中所述的树2-可容许图的特征[7]处理连通图的三连通分量，定义为不包含两个顶点，移除这两个顶点会断开图形。虽然已知n阶完全图（n≥2）是（n-1）-连通的，也就是说，F. 库托，L.F.I.Cunha/Electronic Notes in Theoretical Computer Science 346（2019）355357.........n-2个顶点不断开图[3]，作者认为边和三角形是三连通分支。一个不可分图是一个没有切割顶点，即，一个顶点，它的移动会使图断开。一个有n+ 1个顶点的星是完全二部图K1，n. 一颗V心星是一颗在v.定理1.2[7]不可分图G有树2-n当且仅当G包含生成树T使得对于G的每个三连通分支H，T ∈H是H的生成星。最近，我们刻画了上图，即P4-free图的拉伸指数[8].因此，一个自然的问题是确定这样一个参数的图与几个P4在这项工作中，我们提出了精确的值为P4-稀疏和P4-整齐图（第二。2）。一个图是（k，l），如果它的顶点集可以划分为k个独立集和l个团[4]。我们感兴趣的是对这样一个类的MSST复杂性进行分类表1总结了到目前为止关于确定（k，l）-图的拉伸指数的技术状态表1关于（k，l）-图的拉伸指数的确定，本文首先讨论了P与NP-c.表2本文讨论了（k，l）-图的拉伸指数的确定问题. f（n）是n阶图上的线性函数。灰色单元表示本文的结果。注意，决策问题只针对k和l的几个值进行处理。尽管如此，确定一个图是否是t-可容许的问题被认为是（0，2）和（1，1）-图，这是3-可容许的（参见。[16]）。表2给出了我们对MSST（k，l）-图的贡献 虽然我们把它们中的大多数都设置为NP完全问题（第二节）。3.1），我们提出了子类，其中MSST是多项式时间可解的（第3.1节）。3.2），作为（2， 1）-弦（即使知道弦图，MSST是NP-完全的[6]）。 我们还确定了p-幂圈图（一个（0，l）-图族）的拉伸指数，推广了[8]中的结果。 考虑p-幂圈图的另一个相关性是：它们的拉伸指数同时远离围长给出的下界，并且相对于定理1.1的直径生成树上界是紧的。图2具有少量P4的图的拉伸指数给定一个图G=（V，E），dG（x，y）表示G中x和y之间的距离，dG（v）表示v在G中的度. 悬垂顶点是度数为1的顶点。 我们说 生成树T的非边是G\T的边。我们说一个子图H是如果NH（v）≠0，则s ∈ H，在这种情况下，v ∈H。更进一步，一个vertexvLK012... KL0123...f（n）...0–P？.0–PP？...NP-c...1–P[8]？.1–P[8]？？...NP-c...2NP-c[5]？？.2NP-c[5]NP-cNP-cNP-cNP-cNP-c...3？？？.3NP-cNP-cNP-cNP-cNP-cNP-c...................................... . .358F. 库托，L.F.I.Cunha/Electronic Notes in Theoretical Computer Science 346（2019）355是H-泛的，如果V（H）<$N（v）。p-路径是由p条边形成的路径。一个弦图是Ck-free的，对任意k≥4.一个上图是一个 P4-free图，即没有3-路的图。如果N[v]=N[w]，（分别）N（v）=N（w））。参见[3]中的其他图论术语。最近[8]，我们通过观察其余树的结构性质，确定了余图的树拉伸指数。在此基础上，现在我们考虑共图的超类。我们特别感兴趣的图很少的P4一个图是P4-稀疏的，如果对于每一个5个顶点的集合，最多有一个诱导P4。一个图G是P4-整齐的，如果对G的每个诱导P4P，G中，至多有一个顶点v∈V（G）\V（P）使得V（P）<${v}在两个P4具有少量P4的图操作，如联合和加入。 给定图G i=（V i，E i），i = 1，.，p我们正式定义联合和联合操作，分别如下：G1-0 ···10Gp=（V1···Vp，E1···Ep）;G11 ···1Gp=（V1···Vp，E1···Ep{xy|x∈Vi， y∈Vj，ij，1 ≤i，j≤p}）。拉伸索引与连接操作现在，我们处理任何两个图的连接操作。特别地，我们证明了 由 两 个图G=G1<$1G2的联所得到的图是3-容许图.引理2.1给定两个群G1和G2且G=G1<$1G2，则nσT（G）≤3.是的。 考虑v1是G 1的vertex。SinceNG（v1）=NG1（v1）<$V（G2），构造一个以v1为中心的星，其叶都是V（G2）的顶点.然后，任意选择一个叶，比如v2，使v2与V（G1）\ {v1}相邻.设T为结果图。我们称T是G的一棵3-叉树。首先，观察到G1的任何一对相邻顶点u，uJ（分别为w，WJ）是T的非边.在这种情况下，dT（u，u，J）= 2（分别dT（w，wJ）= 2），通过路径uv2uJ（或wv1wJ）。T的其他非边是横向的，即，它们的一端在G1，另一端在G2设uw为横截非边。 因此，DT（u，w）= 3，通过路径uv2v1w。Q引理2.1表明完全二部图Kp，q是3-容许的，因为它们是两个（1， 0）-图的并. 此外，请注意，在这种情况下，σT（Kp，q）= 3，由于T的非边都是横边，且不考虑生成树，连接二部图的两个不相邻顶点的最小路的长度至少为3.然而，也有两个图的拉伸指数为2的图，例如，任何图的一个通用的顶点的连接所获得的图。有趣的是，在[8]中，我们证明了对于余图，拉伸指数是2当且仅当它有一个泛顶点。拉伸指数与蜘蛛操作一个图G是一个蜘蛛，如果它的顶点集可以划分为S，K和R，使得（i）K是团，S是独立集，|S|为|K|（2）每个顶点 R与K的所有顶点相邻（连接操作），并且不与任何F. 库托，L.F.I.Cunha/Electronic Notes in Theoretical Computer Science 346（2019）355359（iii）存在一个双射f：S → K，使得对所有x∈ S，N（x）={f（x）}，称为细蜘蛛，或N（x）=K− {f（x）}，称为粗蜘蛛。Jamison和Olariu[14]构造性地刻画了P4-稀疏图.的曲线图G是P4-稀疏的当且仅当对它的每一个导出子图H，恰好满足下列条件之一：（i）H是不连通的;（ii）H是不连通的;(iii)H与蜘蛛同构。注意，第（i）和（ii）项建议工会以及在上图构造中应用的连接操作。为了构造P4-稀疏图，下面定义关于项（iii）的操作。让G1=（V1，E2）和G2=（V2，E2）是两个不相交图，其中V2={v}< $ K <$ R且使得：（a）|K|为|V1| + 1 ≥ 2;（b）K是团;（c）x∈ R与每个顶点XJ∈K相邻，且x不与v相邻;（d）存在一个顶点VJ∈K使得NG2（v）={VJ}或NG2（v）= K\{VJ}. 选择一个双射函数f：V1<$→K\{vJ}并定义操作模式 如下：G1-2 G2=（V1<$V2，E2<$EJ），其中EJ={xf（x）} |x∈V1}，如果NG2（v）={VJ}，或EJ={xz|x∈V1，z∈ K \ {VJ}}，若NG2（v）=K\{vJ}.一个图是一个蜘蛛当且仅当它可以由y_n ~ 2生成的两个真导出子图得到。更进一步，一个蜘蛛是P4-稀疏的当且仅当由R导出的子图是P4-稀疏的[14]。 这样，一个图G是P4-稀疏的，如果，只有当G可以从平凡图中得到，通过应用，以任何顺序，操作2010年，201年 和202年a finitenumberoftimes.因此，每个P4-稀疏图都有一棵关联树，称为PS-树。本质上，在PS树中，叶子是图的顶点，每个内部节点被标记为0， 1或2（相应于应用于相关子树的操作）。见[14]详细的结构。引理2.2设G是一个蜘蛛图。如果G是一个细蜘蛛，则σT（G）= 2。否则，σT（G）= 3。证据如果G是一个细蜘蛛，则K中的每个顶点都是K <$R-泛点。因此K<$R的生成星以K的任意顶点为中心。此外，由于S的每个顶点在G中是悬垂的，因此与任何悬垂的边关联的边都是tex在T中受力，则σT（G）= 2。现在，假设|K| f = 2，否则为G也是一个薄的蜘蛛，这已经在前面的情况下考虑。如果G是一个厚蜘蛛，G[K∈S]不同构于H aj′os图，即，g∈H（{a，b，c，d，e，f}，{ab，ad，bd，bc，ce，ce，de，de，ef}），则G是一个三连通的连通群。若σT（G）= 2，则G[7]存在一个生成星T，这是一个矛盾，因为G中没有单向顶点。如果G与Haj′os图同构，则G是σT（G）= 3的分裂图[8].否则，若G[K <$S]同构于Haj′os图，则K <$R是一个三连通component，且若σT（G）=2，则有是G的一个生成树T，使得T（K R）是一个星。除了v∈R是R-泛的情况外，这样的星必须以K顶点为中心。请注意，它仍然需要在T中放置S的顶点，这些顶点的度为2。显然，S的一个顶点不与中心相邻，而是在G中与星的两个叶相邻，这产生σT（G）= 3。若v∈ R是R-泛的，且星T∈（K <$R）是v-中心的，则S中没有顶点与v相邻.因此，σT（G）= 3。Q360F. 库托，L.F.I.Cunha/Electronic Notes in Theoretical Computer Science 346（2019）355引理2.1和2.2包含引理2.3。引理2.3设G是P4-稀疏图，则σ T（G）≤ 3.八面体图Ok是（2k−2）-正则图，即从K2k中去掉一个完美匹配而得到的图。最近，我们证明了σT（Ok）= 3，对于k >2[8]（O2同构于C4，结果如下）.注意，观察PS-树，一个连通的P4-稀疏图G，它不是一个蜘蛛，也不包含一个通用顶点，有一个广义八面体图作为一个导出子图。更具体地说，如果G有一个1-标号根，有k个子树，则有一个广义八面体Ok，其中包含S的两个顶点，对于每个2-标号根子树，如果它们存在，并且每个0-标签根的子树有两个不相邻的顶点（一）.在此基础上，得到了P4-稀疏图的拉伸指数.若G不是树且有泛顶点，则σT（G）= 2，若G是细蜘蛛也是如此。其次，我们确定了其他类型的P4-稀疏图的拉伸指数引理2.4若G是一个连通的P4-稀疏图，且G不是一个薄蜘蛛且没有泛顶点，则σT（G）= 3证据考虑一个连通的P4-稀疏图G的PS-树没有唯一顶点，只有两种可能的情况：(i) root的标签是2。 在这种情况下，G是一个蜘蛛，根据引理2.2，我们知道什么时候G是2-可容许的;(ii) root的标签是1。在这种情况下，这样的根至少有两个不是叶子的孩子，否则我们将有一个通用顶点。(a) 所有root的子节点都标记为0。 因此，在每个根的子树中，一对不相邻的顶点，其最低的共同祖先是这样一个子树的根，用0表示。因此，存在一个广义八面体图Ok作为G的导出子图，并且对G的每个顶点v∈V（G）\V（Ok），G[{v}<$V（Ok）]不存在泛顶点.(b) 至少有一个根在这种情况下，G至少有一个真的子图，它诱导出一个蜘蛛。如果G的所有蜘蛛都是细的，则存在一个广义八面体图作为G的导出子图，对于每个顶点v∈V（G）\V（Ok），G[{v}<$V（Ok）]不具有一个普遍的顶点如果G中有一个粗蜘蛛，比如A，那么一个顶点v∈V（A），它对于G的所有导出广义八面体的子图都是泛点.此外，还证明了由V（Ok），k≥2和关于Ok的所有泛点诱导的G的子图是G的三连通子图.我们主张，即使在G中存在一个关于对于G的广义八面体，σT（G）= 3.设Ok是G的一个广义八面体，A是G的一个粗蜘蛛，u∈V（A）是Ok-泛顶点. 通过矛盾，假设σT（G）= 2。在在这种情况下，存在G的生成树T，使得对于G的每个三连通分支H，TH是星[7]。由于一个Ok和Ok-泛点属于一个三连通分支H，且σT（Ok）= 3，F. 库托，L.F.I.Cunha/Electronic Notes in Theoretical Computer Science 346（2019）355361JOk的一个顶点必是TH的一个叶。 这样的中心，一个星必须是Ok-泛顶点，比如u。 注意u∈V（A）， 其中至少有两个叶子属于V（A），比如a，b。他们特别根据Ok的构造，它属于S观察到A中只有一个顶点不与u相邻，比如x，并且x在A中至少有2个邻居。我们有两种可能性：（i）u在G中的所有近邻都是u在T中的近邻，且在这种情况下dT（x，y）≥3，其中y∈NA（x）;（ii）u至少有一个近邻，比如w，不在 NT（u）中，但与G中的a或b相邻.因此，对于i∈ {a，b}， dT（w，i）≥3。由于PS树的根是1-标号的，因此没有1-标号的其次，对案例（a）和（b）进行分析，以完成证明。Q定理2.5一个P4-稀疏图G是2-可容许的当且仅当G有一个泛顶点或G是一个细蜘蛛。证据显然，如果G有一个泛顶点或G是一个细蜘蛛，则σT（G）= 2。反之，设G不是一个薄蜘蛛，也没有一个泛顶点。因此，它的PS树因此，根据引理2.2和2.4，σT（G）= 3.QP4-稀疏图的一个自然推广是P4-整齐图.一个图H是一个几乎蜘蛛图，如果H可以从一个蜘蛛图G=（S，K，R）通过添加一个顶点v来构造，该顶点v是v的假孪生或v的真孪生，使得v∈S <$K[15]。因此，我们称H为P-假几乎蜘蛛和P-真几乎蜘蛛，其中P是v所属的集合，即P ∈ {S，K}。 在同一如果是一个伪命题，那么，如果是一个伪命题，那么，如果是一个伪命题，那么，蜘蛛一个P4-序群G可以通过以下方法构造：i）G1≠0 G2，对于G1和G2，它们是P4-整齐图;ii）G1是P4-整齐图 G2对于G1和G2是P4-整齐的图; iii）G是蜘蛛; iv）G是几乎蜘蛛; v）G是P5，C5，P5或K1。由于PS-树表示P4-稀疏图，我们可以以类似的方式开发P4-整洁图的树表示[15]。引理2.6设G是几乎蜘蛛图，则σT（G）≤3。利用i）- v）和上面的结果，证明了如果G是P4-整齐图，则G是3-可容许的，但如果G是C5的除外.引理2.7设G是一个几乎蜘蛛图。 G是2-容许的，当且仅当G是一个S-几乎薄蜘蛛（假或真），还是一个K-真几乎薄蜘蛛。与定理2.5类似，我们也刻画了2-容许的P4定理2.8一个P4-整洁图G是2-容许的当仅当：G有一个泛顶点;或G是一个瘦蜘蛛;或G是一个S-几乎瘦蜘蛛（假或真）;或G是一个K-真几乎瘦蜘蛛。362F. 库托，L.F.I.Cunha/Electronic Notes in Theoretical Computer Science 346（2019）3553（k，l）-图的拉伸指数如表1所示，MSST没有被处理为（k，l）-图，考虑k+l≥3。虽然（0，2）-图已知是3-可容许的（cf. [7]）中，没有关于（0， 2）-图的2-容许性的刻画。（k，l）-图拟合在MSST有趣类的框架下，由于（0， 2）-图是3-容许的，而对于（2， 0）-图，MSST是NP-完全的（t≥5）.在第3.1节中，我们提出了考虑（k，l）-图的NP-完全情况，在第3.2节中，我们提出了考虑（k，l）-图的NP-完全情况。在第3.2节中，我们给出了（k，l）-图3.1疑难案件设G是一个图。一个独角图是由G的任意一个顶点加上一个悬挂点而得到的图。如果G属于类C，则由G得到的一个独角图称为独角-C图.由于边缘事件的任何悬挂顶点在任何生成树中是强制的，我们立即得到给定H从图G得到的独角图，σT（H）=t当且仅当σT（G）=t。因此，即使对独角二部图，MSST也是NP-完全的注意一个独角-（k，l）-图有一个（k，l）-划分，其中添加的悬挂顶点被分配给G的k个独立集之一或G的l个团之一（在这种情况下，这个团是一个K1）。接下来我们介绍两种构造为了证明（k，0）-图，k≥3，和（k，l+1）-图的MSSTk≥3，l≥ 0，是NP-完全的。构造1给定H =（VH，EH）是一个独角二部图，设v是H的附加悬挂点。因此，我们从H构造一个图W =（V W，E W）如下：i）V W= V H<$V（K k−1）; ii）E W=E H<${vy|y∈V（K k−1）}<$E（K k−1）.设H是一个图，W是由H通过构造1得到的图. 因此，很容易检验，给定t≥2，σT（W）=t当且仅当σT（H）=t，因此，我们有以下结果。引理3.1（k，0）-图的MSST，当k≥ 3时，当t ≥ 5时是NP-完全的.构造2设H =（VH，EH）是一个独角-（k，l）-图，v是H的附加悬挂点.我们构造一个特殊的例子W =（V W，E W）如下：i）V W= V H<$V（K k+1）; ii）E W= EH<${vy |y ∈ V（Kk+1）}<$E（Kk+1）.引理3.2如果（k，l）-图的MSST是NP-完全的，对k，l个固定整数，k，l≥0，则当t ≥ 5时，（k，l +1）-图的MSST是NP-完全的.证据给定一个单角-（k，l）-图H和由构造2得到的图W，证明单角-（k，l）-图H具有拉伸指数t >2当且仅当W是具有拉伸指数t >2的（k，l显然，W具有（k，l+ 1）-划分。此外，通过构造2，v是H的唯一顶点，与所加团Kk+1相邻。因此，在VH的顶点之间不存在包含Kk+1的顶点的路径。因此，σT（W）=t。相反，假设W是一个F. 库托，L.F.I.Cunha/Electronic Notes in Theoretical Computer Science 346（2019）355363DDDd−1i∈EDi∈Vd−1i∈EGi∈VG（k，l+1）-图通过构造2，我们通过鸽子洞原理保证W的l+1个团中至少有一个团仅由添加的顶点组成（如果v在这样的团中，则它可以在W的k个独立集合中的一个中替换而没有任何损失）。因此，在Kk+1去除W之后，所得图HJ是独角-（k，l）-图且σT（HJ） =t，因为我们可以保证存在两个VHJ\{v}的顶点其在T中的距离为t，否则，我们可以改进σT（W）。Q引理3.1和3.2直接推导出定理3.3。定理3.3（k，l）-图的MSST（k≥ 2，l≥ 0）是NP-完全的.接下来，我们证明了（0，l）-图的MSST是NP-完全的，提出了一个多项式时间约简从NP-完全问题MSST（2， 0）-图。由于任何n阶图都是（0，n）-图，因此（0，n）-图的MSST已知道它是NP-完全的，其中t≥4[7]。然而，这是一个有趣的问题，以确定什么是最小的l，其中MSST是NP-完全的。在接下来，我们处理这项任务。构造3给定G =（VG，EG）是一个二部图，d是一个整数，我们从G构造一个图Q =（VG，EQ），|E G|顶点完全图的副本ui，ui，.，u i，对于i ∈ E G，且|V G|顶点完全图的副本12dd−1vi，vi，.，vi，对于i∈VG，如下：1 2d−1• V Q= V GV（Ki） V（Ki）;• EQ=EG{aui，bui|ab∈EG}<${a va|a∈V（G）， j=一，二， . . . ，（d−D1）}E（K i）E（Ki）.GG事实3.4设Q =（V Q，E Q）是由G =（V G，E G）和整数d通过构造3构造的图。 我们有这个|V Q|= 0（|V G|+的|E G|），并且Q是（0，|V G|+的|E G|）-graph.引理3.5设Q是通过构造3从G获得的图，D. 则G是一个（2，0）-图，且σ T（G）= t当且仅当Q是一个（0，0）-图，|VQ|）-图其中σ T（Q）= t +2。由于图G =（V，E）的大小为|V|+的|E|，我们将大小为l的（2，0）-图和（0，l）-图定理3.6如果（2， 0）-图的MSST是NP-完全的，则（0，1）-图是NP-完全的.一个海胆-G图是由图G的每一个顶点加一个悬挂点而得到的图。显然，（0，1）-图的海胆-G图是（1，1）-图. 由于一个海胆-G图H有σ T（H）= σ T（G），我们陈述定理3.7.1J364F. 库托，L.F.I.Cunha/Electronic Notes in Theoretical Computer Science 346（2019）355定理3.7如果（0，l）的MSST是NP-完全的，则（1，l）-图的MSST是NP-完全。F. 库托，L.F.I.Cunha/Electronic Notes in Theoretical Computer Science 346（2019）3553653.2简单的案例虽然对于k和l的几个值，MSST是NP-完全的，但我们可以在多项式时间内确定某些（k，l）-图的拉伸指数（0，2）-图是3-可容许的，参见 [16]，并且，在这篇工作中，我们刻画了2-容许（0，2）-图。设H=G[VH]，其中VH是与G的每个横边关联的顶点的集合，即，边的一个极端在K1，另一个极端在K2。引理3.8设G =（K1<$K2，E）是（0，2）-图. G是2-容许的当且仅当G有泛点，G有割点或H是严格2-连通图且没有诱导C4.作为引理3.8的一个推论，我们得到一个由H=Kp和Q=Kq的并（p，q≥4）通过一个由H的两个顶点和Q的两个顶点组成的诱导C4连接它们而得到的（0，2）-图G有σT（G）= 3.（2， 1）-弦图如3.1节所证明的，（2， 1）-图的MSST是NP-完全的，弦图也是如此.然而，对于（2， 1）-弦图（在其他一些上下文中研究的类[9，10]），MSST在多项式时间内求解。 注意，a（2， 0）-弦图没有圈，所以弦图是（2， 0）-图当且仅当它是森林。因此，（2， 1）-弦图被划分为森林F和团K。给定任意图G的一个（F，K）-划分，在F中有一个极值的边和K中的另一条边称为横边。两条与F中同一棵树相交的横边在G中形成一个圈。如果这两条边与K的同一个顶点关联，则我们有一个1型圈，否则，有一个2型圈。特别地，如果G是弦的，则在1型圈中，K中的顶点必须与圈的其他顶点相邻。在一个2型圈中，我们有两种可能性：至少有一个K-顶点完全邻近于循环顶点;或者它们的邻域覆盖了具有某些交集的循环，如[9]所述。 在这项工作中，我们认为，顶点v在T i∈ F中，对于i ∈ {1，...， |F|}，是类型1顶点，当且仅当，|v∈Ti NK（v）|=1。否则，它们是类型2顶点。引理3.9（2，1）-弦图是4-容许的。其次，我们刻画了2-容许（2， 1）-弦图，其中（F，K）-划分使得K是最大的。如果一个图G是（2， 1）-弦图，但它的团不是最大的，则它至少有一个，至多有两个泛点对于Ti∈ F中的K，可以无损失地放置在K中。因此，从现在开始，我们只考虑（2， 1）-弦图的（F，K）-划分，使得K是最大的。双星B是通过将一颗恒星的一片叶子与另一颗恒星的中心相鉴别而得到的。中心为v，w的双星是中心为v，w的双星。 我们分别用L（v）和L（w）表示B中v和w引理3.10设G是（2，1）-弦图. 如果K T不同于恒星，则σ T（G）≥3。366F. 库托，L.F.I.Cunha/Electronic Notes in Theoretical Computer Science 346（2019）355JJ为了确定（2， 1）-弦图G的拉伸指数，我们首先对G进行预处理，得到一个图Gj，称为清洁（2，1）-弦图，如下：我们移动t∈V（F），使得NK（t） =N，且F的所有t个顶点都是1.Next，考虑每个2型圈Ck1，k2，k1，k2∈ K和相应的树T∈ F，使得k1，k2在Ck1， k2中不是泛圈，我们将顶点f∈Ck1，k2<$F，使得|NK（f）|=1且不与N Ck1，k2<$T（k1）<$N Ck1，k2<$T（k2）中的顶点相邻。如果一个标记的顶点属于另一个循环，并且在这种情况下没有标记，则标记被移除，并且顶点不能再被标记。最后，删除所有标记的顶点。显然，如果（2， 1）-弦图G有σT（G）=t，则它的清洁（2， 1）-弦图GJ有σT（GJ）=t.引理3.11设G =（F，K，E）是一个（2，1）-弦图，GJ=（FJ，K，EJ）是它的清洁（2，1）-弦图.σT（G）= 2当且仅当下列条件之一成立：（i）G中的所有圈（不是仅由团点构成的）都是1型圈;（ii）K中存在FJ-泛点.引理3.12设G =（F，K，E）是（2，1）-弦图.若σT（G）= 3，则存在树3-生成T使得T<$K是一个双星.给定一个v，w-中心双星和一对K-顶点（x，z），如果x只看到一个极值，z看到t，t，则称一条边TTJ∈E（Ti）为（x，z）-应力边.引理3.13设G =（F，K，E）是一个非2-容许（2，1）-弦图，GJ=（FJ，K，EJ）是它的清洁（2，1）-弦图.σT（G）= 3当且仅当K ∈T是一个v，w-中心双星，使得对于F j中的每棵树Ti，i = 1，.，|，以下条件之一恰好成立：|, exactly one ofthe following conditions holds:(i) NTi（v）<$NTi（w）=V（Ti）;(ii) NTi（v） =NTi（w） =NTi（L（w））=NTi（resp. NTi（L（v））=n）和reisf∈L（v）（resp. l∈L（w））是Ti-泛的.(iii) 第3.1条和第3.2条必须同时成立3.1. 对于（f，x）和（x，f）-应力边的每对（e1，e2）（分别为 （l，x）和（x，l）-应力边），f ∈ L（v），x ∈（{w}<$L（v））（分别 l ∈ L（w），x ∈（{v}<$L（w）），存在一个顶点t ∈ NTi（x）<$NTi（f）（分别 N Ti（x）<$N Ti（l）），它属于Ti中的e1和e2之间的路，并且使得vt∈E（GJ）（分别为. wt∈E（G））。3.2对于每个（f，l）或（l，f）-应力边，假设e1=TTJ，至少有一个中心见t或TJ，f ∈ L（v），l ∈ L（w）.引理3.9，3.11和3.13给出了在多项式时间内确定（2，1）-弦图的拉伸指数所需的条件 更具体地说，引理3.11条件可以通过寻找1型圈或FJ-泛顶点来验证更多-为了识别一个3-容许（2， 1）-弦图，我们试图构造一个v，w-中心双星，至少满足引理3.13因此，我们把每对v，w∈K看作双星中心的候选者，并通过观察NF′（v），NF′（w）和严格遵循引理3.13的条件来确定L（v）和L（w 如果不可能为某对v，w建立这样一个双星，F. 库托，L.F.I.Cunha/Electronic Notes in Theoretical Computer Science 346（2019）355367nnn[|p+1n. 在[8]中，我们展示了一棵最优树，nnnnnn2不n2np如果所有的答案都是否定的，我们就得出结论：σT（G）= 4。注意引理3. 13定理3.14（2，1）-弦图的MSST是多项式时间可解的。循环功率图一个p-圈幂图Cp是由一个Cn通过在所有的圈幂图在Cn中距离至多为p的顶点。 由于g（Cp）= 3，则σT（Cp）≥2。一p-圈幂图可以划分为n小团体因此，任何p-圈幂图都是（0，l）-图，对于[n|≤l≤p+1[2]对于p=2，其次，给出了一般p-循环幂律的指数表达式图表。u i和u p之间的转弯路径是路径u i uj（1）uj（2）. uj（s）u psuch则（i，j（1），j（2），...，j（s），p）是单调循环序列。一条不转弯的路径被称为之字形路径。引理3.15对于G = Cp的任何生成树T，至少存在一个外部非边u i u i+1，使得T中u i和u i+1之间的路径是一条转弯路径。作为引理3.15的结果，我们得到：对于幂循环图，其拉伸指数等于它的拉伸指数（即DT（Cp）=σT（Cp））。定理3.16给出了σT（Cp）的上界，它等于长度相对于外部非边缘的转弯路径定理3.16对于一个Cp，如果p≥[n]，则nσ（Cp）=2。否则，ifp<[n]，pn则：i）若n∈x（modp），对于x∈{0，1}，则nσ（C）=[n];ii）若n/n ∈x（modp），对于x∈{0， 1}，则σ（C p）=[n|.TNP4结论在这项工作中，我们提出了树拉伸指数的图与少数的P4的在这项工作中提出的策略，我们打算继续获得最佳树的t-空间的顶点/边操作构造的图。关于本文的结果还有一些问题没有解决，例如：确定一个固定的l值，使得（0，l）-图的MSST是NP-完全的，如果这样的值存在的话;以及完成（k，l）-图引用[1] Bansal，N.，联合费日河Krauthgamer，K.马卡雷切夫河谷Nagarajan，J.Seeanjiang和R.图的最小-最大划分和小集扩张，SIAM J。Comput. 43（2014），pp.872-904[2] Bhatt，S.，F. 钟氏T.Leighton和A.Rosenberg，树机器的最优模拟，在：计算机科学基础，1986年。第 27届 年度研讨会，IEEE，1986年，pp。274-282。不368F. 库托，L.F.I.Cunha/Electronic Notes in Theoretical Computer Science 346（2019）355[3] Bondy，J.和U. Murty，Graph Theory（2008）.[4]Brandstadt，A.，将图形划分为一个或两个独立的集合和集团，离散数学。152（1996），pp. 47比54[5] Brandstadt，A.，F. F.德拉甘，H.- O.勒河，巴西-地Uehara等人，二部图和探测区间图的树空间，《自然》47（2007），pp. 27比51[6] Brandstadt， A. ， F. F. 德 拉 甘 ， H.- O.Le 等 人 ， Trees poncho rdalgraphs ： complexityandalgorithms ，Theoretical Computer Science 310（2004），pp. 329-354.[7] 蔡湖，加-地和D. G. Corneil，Tree spectrum，SIAM J. Discrete Math.8（1995），pp. 359-387.[8] Couto ， F. 和 L. F. I. Cunha ， Tree t-spectrum of a graph ： Minimizing maximum distanceseeconciently，第12届组合优化与应用国际年会，COCOA 2018，LNCS11346（2018），pp.46比61[9] Couto，F.，L. Faria，S. Gravier和S. Klein，Chordal-（2，1）graph sandwich problem with boundaryconditions，Electronic Notes in Discrete Mathematics69（2018），pp.277-284。[10] Couto，F.，L. Faria和S. Klein，Chordal-（k，l）and strongly chordal-（k，l）graph sandwichproblems，Journal of the Brazilian Computer Society20：16（2014），pp.1比10[11] 库尼亚湖F.一、L. A. B.科瓦达河de A. Hausen和C. M.
我的内容管理
展开
