⊆、、、1+B、、、可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）309-320www.elsevier.com/locate/entcs直径为2的图的P3马西娅河作者：Erika M. M.作者声明：Dr. 席尔瓦1，2InstitutodeInform'aticaUniversidadeFederaldeGoi'asGoiGuania-GO我是波提，你是S。Souza苏扎1，3巴西里约热内卢联邦弗鲁米嫩塞大学摘要设G是一个顶点集为V（G）的有限简单无向图。若存在一个顶点子集SV（G），且V（G）的每一个在S中至少有两个相邻顶点的顶点也是S的一个顶点，则称S为P3-凸的S的P3-凸包是包含S的最小凸集.P3-壳数h（G）是指P3-凸包是整个图的最小顶点集的基数。本文给出了直径为2的图的P3-壳数的一些界特别是，在双连接的无C6直径为2的图的P3-壳数至多为4。 我们还建立了上界h（G）≤k+1或者h（G）≤logc+1（k.c+ 1）+ 1，对于强正则图G（n，k，b，c）.保留字：图，P3-凸性，壳数，直径21介绍对于图G，顶点集记为V（G），边集记为E（G）。我们考虑有限、简单和无向图。V（G）的子集的集合C是G中的凸性，如果n，V（G）∈C且C在交下闭C的每个元素都是一个凸集。子集S∈V（G）的凸包HC（S）是最小凸集，1作者感谢FAPEG、FAPERJ、CNPq和CAPES对本研究的支持2电子邮件：{marcia，erikamorais，hebert，braullyrocha}@ inf.ufg.br3电子邮件：{fabio，ueverton}@ ic.uff.brhttps://doi.org/10.1016/j.entcs.2019.08.0281571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。310M.R. Cappelle et al. /Electronic Notes in Theoretical Computer Science 346（2019）309S.如果HC（S）=V（G），则S是壳集.G中最小壳集的基数hC（G）称为G的壳数。图中的一些凸性由图中的路径集合P定义在这种情况下，当C包含属于P的路的所有顶点且其极端顶点也在C中时，子集C ∈V（G）是精确凸的。测地凸性认为P是G中所有最短路的集合[4，11，12，18]。在单声道凸性[9，13，17]中，P是所有诱导路径的集合三角形路凸性[7，15]和P3凸性认为P是所有三顶点路的集合[5，6，8，14]。壳数的概念是由Everett和Seidman [18]在大地凸性中引入的。考虑到这种凸性，对于二部图[1]，壳数的计算是NP困难的，但对于余图和分裂图[10]，（q，q−4）-图[1]，{paw，P5}-free图[11]，距离遗传图[21]。研究了其它图凸性下的壳数。在单音凸性[13]和三角形路径凸性[15]中，一般图的壳数可以在多项式时间内确定。在P3凸性下，壳数的计算是NP困难的，但壳数是可以确定的在多项式时间的余图和弦图[5]，并为互补棱镜[16]。最近，Penso等人。[22]研究了计算限制在平面图上的壳数的复杂性，表明它在最大度为3和4的平面图上仍然是NP困难的本文专门研究图G的P3-凸性C. 给予设S∈V（G），S的P3-区间I[S]由S加上S外的每个顶点与S中至少两个相邻点构成.如果I[S] =S，则集合S是P3-凸的.S的P3-凸包HC（S）是包含S的最小P3-凸集. 以来一个图G唯一地确定它的P3-凸性C，我们可以记为H（S），而不是HC（S）。 P3-凸包H（S）可以由序列Ip [S]构成，其中p是一个非负整数，I0[S] =S，I1[S] =I[S]，且Ip[S] =I[Ip−1[S]]（p≥2）。当对p有Iq[S] =Ip[S]时，对所有q≥p，则Ip[S]是P3-凸集.若H（S）=V（G），则称S是G的P3-壳集.G中最小P3-壳集的基数h（G）称为G的P3-壳数.研究了直径为2的图的P3我们提出了一个算法，提供了一个最大基数[log（Δ +1）]的外壳集，|+1。对于C6-free直径2图，我们证明了壳数至多为4.此外，我们还证明了对于直径为2的图的一个子类，即强正则图，壳数至多为3。在我们提出我们的结果和证明之前，我们总结一些符号和有用的定义。顶点v ∈ V（G）的开邻域为N（v）={w ∈ V（G）|vw ∈E（G）}，其闭邻域为N [v]= N（v）<${v}. 对于一个顶点集S，G，令N[S]=u∈S N[u]。 顶点v∈V（G）的度记为d（v），图G的最小度是δ（G）= min{d（v）|v∈V（G）}和最大值G的次数为Δ（G）= max{d（v）|v∈V（G）}. 如果u，v∈V（G），我们记为d（u，v）是u与v之间的距离，G的直径是G的所有顶点对之间的最大距离.因此，如果图G的直径为2，则M.R. Cappelle et al. /Electronic Notes in Theoretical Computer Science 346（2019）309311每对不相邻的顶点具有共同的邻居。图1显示了直径为2的一些图。Fig. 1. 直径为2的图的例子。直径为2的图的类是广泛的，包括一类感兴趣的这项工作。一个n阶图G（n，k，b，c）是强正则的，如果它是k-正则的，并且存在整数b和c使得每两个相邻的顶点有b个公共邻域，每两个不相邻的顶点有c个公共邻域.一个图G是连通的，如果对任意两个顶点u，v∈V（G），G中存在一条u-v路.一个连通图G称为双连通图，如果对任意顶点v∈V（G）， G-V是连通的。一个连通图G的割点v使得G−v是不连通的。一个图是C6-free的，如果它不包含6个顶点的诱导圈.一个子集S∈V（G）是一个控制集，如果每个不在S中的顶点都至少与S的一个成员相邻。我们说一个顶点集T是共凸的，如果T的每个顶点在T之外最多有一个邻居。 以下事实很容易证实。事实1.1设S是G的壳集，T是G的共凸集。然后，S包含T的一个顶点为了结束这一节，我们给出一些关于直径为2的图的观察。观察1设G是一个直径为2的图. 然后，以下属性为真：(a) 若u，v∈V（G），则N[u]<$N[v]<$;(b) N（v）是G的控制集<$v∈V（G）;(c) 若δ（G）= 1，则 Δ（G）=n− 1;(d) 若G有割点，则Δ（G）= n− 1。2结果在本节中，我们介绍了我们的结果。我们首先讨论了直径为2的图G的壳数的最坏情况，当G有一个割点时。请注意，等式对星形图K1，n成立，其中n≥2。命题2.1设G是一个直径为2的图，其割点为v。 则h（G）=ω（G − v），其中ω（G）是G的连通分支数。证据 设G是一个直径为 2的图，其割点为v。考虑GJ=G−312M.R. Cappelle et al. /Electronic Notes in Theoretical Computer Science 346（2019）309Jv.由于v是割点，GJ不连通，k = ω（GJ）≥ 2个连通分支，比如C1，. C k.设S是V（GJ）的一个子集，它恰好包含每个连通分支Ci的一个顶点，i = 1，.，K.注意|S|=k，并且还记得v与G的每个顶点相邻。我们将证明V（G）-S中的每个顶点都属于H（S）。首先证明v∈H（S）。设ui∈Ci且uj∈Cj，使得u i，u j∈S和ij. 由于u i，u j∈N（v），v∈H（{u i，u j}）. 现在，考虑一个顶点u∈ C i− S，对于某个i ∈ {1，...， k}。因为Ci是连通的，所以在Ci中存在一条路径P= u，u1，...，ul，其中l ≥ 1，使得ul∈ S. 由于v与P中的每个顶点相邻，并且v ∈ H（S），我们有ul−1∈ I2（S），ul−2∈ I3（S），依此类推，从而得到u∈ I|P|-2。故u∈H（S）。我们可以得出S是G的一个基数为k=ω（G−v）且h（G）≤k的壳集。对于下界，观察到每个连通分量C i在C i外部恰好有一个邻居v，i = 1，.，K. 因此，每个C i都是共凸的，并且遵循事实1.1 h（G）≥k。 因此，h（G）=ω（G−v）。Q根据观察1（c）和1（d），如果G的直径为2，Δ1且G没有割点。这些限制可用于建立集合S是G的壳集合的条件。引理2.2设G是一个双连通直径为2的图，SJ∈ V（G）. 若H（SJ）是G的控制集，则对任意v ∈ V（G）− H（SJ），集合S = SJ<${v}是G的壳集。证据设G是一个双连通直径为2的图，H（SJ）是G的一个支配集.注意，每个v∈V（G）−H（SJ）在H（SJ）中有一个邻居。考虑S=SJ<${v}，使得v∈V（G）−H（SJ）。我们将通过证明每个顶点u∈V（G）−H（SJ）属于S的凸包来证明S是一个壳集。1.由顶点集V（G）− H（SJ）导出的图G j是连通的。对于矛盾证明，假设GJ是不连通的。设G1和G2是GJ的两个连通分支，v1∈V（G1），v2∈V（G2）.当d（v1，v2）= 2时，存在w∈H（SJ）使得v1w，v2w∈E（G）.因此，w是v1和v2在H（S）中的单近邻. 使用相同的参数，可以得出G1和G2的所有顶点都只与H（SJ）中的w 由于H（SJ）是一个控制集，所以顶点w是唯一的，否则G1和G2的所有顶点都在H（SJ）中。因此，w是割点，这是一个矛盾，因为G是双连通的。Q根据权利要求1，考虑路径P = v，v1，v2，...，v k u在H（SJ）中。 当vv1∈E（G）且存在一个顶点v1J∈H（SJ），如果v1Jv1∈E（G），则v1∈I[S].类似地，由于v1v2∈E（G），且存在v2J∈H（SJ），所以v2Jv2∈E（G），则v2∈I2[S].因此，由于vn u∈E（G）且存在一个vertexvkJ∈H（SJ），如果vkJvk∈E（G），则可得u∈Ik+1[S]。所以，证据就完整了Q通过引理2.2可以得到一个简单的上界。推论2.3如果G是一个双连通直径为2的图，则h（G）≤ c（G）+1，其中c（G）是G中顶点的最小割的基数。M.R. Cappelle et al. /Electronic Notes in Theoretical Computer Science 346（2019）309313证据 设X是G的顶点的最小割. 因为G的直径为2，所以集合X是控制集。根据引理2.2，X∈ {v}，对所有v∈V（G）\H（X），是一个壳集。 因此，h（G）≤c（G）+1。Q我们可以通过提供一个多项式时间算法来改进这个界限，该算法以迭代的方式构造外壳集。该算法构造了一个集SJ，其凸壳是支配的。 因此，根据引理2.2，图G有一个壳集S=SJ<${v}，其中v∈V（G）−H（SJ）。该算法使用直径为2的图的以下性质。在一个直径为2的图G中，任何非空集C都可以用来将G的剩余顶点集划分为两个其他子集，如下所示：• 集合N：V（G）−C的子集，包含与某个顶点相邻的所有顶点，C，使得它们不属于C，即，N=N（C）−C。• 集合O：V（G）−C的子集，包含仅与N，即，O=N[N] −N[C]。如命题2.4所示，对于直径为2的图，集合C，N和O图V（G）命题2.4如果G是直径为2的图，则V（G）= C <$N<$O。证 据 对 于 一 个 反 证 法 ， 设 存 在 一 个 顶 点 v∈V （ G ） such ， 使 得 {v} <$ （ C<$N<$O）=<$. 考虑u∈N（v）. 在最好的情况下，如果u∈O，则d（v，w）= 3，对于w∈C，这是一个矛盾，因为G的直径为2。Q集合C、N和O的另一个重要性质是，它们可以用来识别一个集合何时是支配集。命题2.5设G是直径为2的图，S∈V（G）。考虑C= H（S），N = N（C）− C和O= V（G）− N [C]。那么，以下陈述为真：(a) 如果O = O，则H（S）是一个支配集。(b) 如果O ∈ O，则|N（o）N |≥ |H（S）|.是的。（a）. SinceO=H，由Propositin2.4，eierv∈H（S）orrv∈N. 通过定义集合C和N，H（S）是支配集，完成了（a）的证明。证明（b）。通过矛盾，假设o∈O，|N（o）N|<|H（S）|.通过定义集合O，顶点O不与H（S）中的任何顶点相邻。由于G是一个直径为2的图，H（S）中的每个顶点至少与一个顶点相邻 在N（o）中。 作为|N（o）N|<|H（S）|，则至少存在一个顶点v∈ N [C]<$N [O]使得|N [v ] N [v] C| ≥ 2。所以，v∈H（S），o∈N[C]。 这是一个矛盾，它证明了（b）。Q命题2.5给出了一个迭代选择V（G）中的顶点组成集合C的算法，使得C是一个控制集。考虑一个集合SJ和C=H（SJ）。观察N = N [C] −C是H（SJ）支配的集合，并且属于O = N [N] −N [C]的每个顶点v满足|N（v）N| ≥ |H（SJ）|. 当314M.R. Cappelle et al. /Electronic Notes in Theoretical Computer Science 346（2019）309J−|>Δ，我们有O = Π，因此H（SJ）将是一个控制集。|> Δ, we have O = ∅ and consequently H (SJ)will be a dominating set. 在这种情况下，根据引理2.2，存在基数的外壳集|SJ|+1。 我们将证明Sj的基数至多为[log（Δ（G）+1）]|.该算法首先将任意顶点v∈V（G）包含在SJ中，然后计算集合H=H（SJ），N和O.当O/=O时，算法选择O的任何顶点，将其添加到S，并计算集合H，N和O。迭代过程在O为空时结束，在这种情况下返回支配集H（SJ）。该过程的伪代码作为算法1给出。算法1：HULLSET（G）数据：直径二图G=（V，E）结果：SJ使得N（H（SJ））=V（G）1SJ←2 中文（简体）3 O←V4whileO/=05SJ←SJ{v}|v∈ O6H←H（SJ）7O←V−N[H]端89 returnSJ在接下来的证明中，我们分别将SiJ，Oi和Hi表示为集合SJ，O和H在算法1的第i次迭代中。我们可以观察到的第一个性质是集合H的基数在每次迭代时加倍。引理2.6考虑算法1的第i次迭代。如果Oi你好，|H（SiJ）| ≥二（|H（SiJ1）|+1）。证据 考虑算法1的第i次迭代，并假设N i= N（H i）-你好。 设u∈Oi−1，使得SiJ=SiJ1<${u}。 注意，−N（u）<$Ni−1ii−1。在H中至少有两个邻居，即u和它在H中的邻居因此，N（u）<$Ni−1<$Hi。 因此|H i| ≥ |H i−1|+的|N（u）<$N i−1|+1，其中单位项来自顶点u。 但根据2.5号提案，|N（u）<$N i−1| ≥ |H i−1|. 因此，我们认为，|H i| ≥ 2 |H i−1|+1。Q当|H（SJ）|> Δ，通过命题2.5，我们可以得出H（SJ）是支配集.下一个命题建立了实现这一点所需的最大迭代次数。命题2.7算法1至多运行k =[log（Δ（G）+ 1）]|迭代是的。 通过引理2.6，在算法1的每次迭代中，|H（SiJ）| ≥2|H（SiJ1）|+1。存在H（Si，j）的n次幂增长. 求解递归，T（n）≥−2·T（n−1）+1，集合的基数y可以由不等式来表示|H（SiJ）| ≥2i−1。通过命题2.5，Oi中的顶点的度必须大于基数M.R. Cappelle et al. /Electronic Notes in Theoretical Computer Science 346（2019）309315−−的H（SiJ1）。因此，当H（SiJ1）>Δ时，O i是emp t y，即， 当2k≥Δ+1. 隔离k，我们有k≥log（Δ + 1）。 因此k =[log（Δ（G）+1）]|.Q推论2.8如果G是一个双连通直径为2的图，则h（G）≤ [log（Δ（G）+1）]|+1。证据 根据命题2.7，算法1最多运行[log（Δ（G）+1）]|迭代。在算法的每次迭代中，集合SJ递增1。所以，|SJ| ≤ [log（Δ（G）+ 1）|而H（SJ）是一个支配集。由于存在基数[log Δ + 1]的支配集，|，由引理2.2我们有h（G）≤ [log（Δ +1）]|+1。Q如果我们添加一些与直径为2的图相关的约束，我们可以建立一个更清晰的界限。定理2.9若G是具有一对真/假孪生顶点的直径为2的双连通图，则h（G）≤ 3。证据如果G有一对顶点u，v，使得u和v是真或假孪生，则根据定义，N（u）=N（v）。因此，H（{u，v}）<$N（v）。由于G是直径为2的双连通的，因此N（v）是一个控制集。因此，根据引理2.2，{u，v，w}是G的壳集，其中w（如果有的话）是不属于H（{u，v}）的顶点Q定理2.10若G是一个双连通的无C6直径2图，则h（G）≤ 4.证据设G是一个双连通的无C6直径为2的图，S ={a，b，c}是一个大小为3的顶点集，使得|H（S）|是最大的。如果H（S）是控制集，根据引理2.2，定理成立。否则，由于H（S）不是控制集，因此S的每个顶点至少有一个不同的邻居w，使得w∈/H（S）。否则，一个顶点的邻边都将是H（S），并且H（S）是一个控制集. 定义一个s_w为a∈S（w∈/H（S））的一个neig h_b或. 我们有以下案例：情形1：G [S]至少包含一条边。设ab是G[S]的一条边。在这种情况下，H（{w，b，c}）包含a，因此H（S）<$H（{w，b，c}）。 因为w∈/H（S），所以{w，b，c}是一个大小为3的集合，其中h的大小大于|H（S）|这是一个矛盾。例2：S是一个独立集合。由于G的直径为tw0，因此，{a，b}、{a，c}和{b，c}对具有公共邻居。(i) 如果有一个顶点z是a，b和c的邻居，则H（{w，b，c}）包含z. 因此，它也包含a，其中h意味着H（S）<$H（{w，b，c}）（w∈/H（S）），与H（S）的极大性相316M.R. Cappelle et al. /Electronic Notes in Theoretical Computer Science 346（2019）3091+B、、、N（v）-OH（SiJ）. 当i≥K1+B，集合H（SiJ）是一个支配集，|=，k，.|= ,k ,.Q(ii) 否则，G包含一个C6：a，x1，b，x2，c，x3，a.设{a，b，c}是一个内边集 ，且G没有诱导C6，则G[{x1，x2，x3}]诱导一条边. 设（x1，x2）是G[{x1，x2，x3}]的一个可积. 由于H（S）不是控制集，x1有一个neig hb或usu c h使得u∈/H（S）. 考虑H（{a，c，u}）。很容易假设H（{a，c，u}）包含x1（u和a的邻居）。因此，它也被...图2是x2（c和x1的邻居）和b（x1和x2的邻居）。因此，H（{a，c，u}）<$H（S={a，b，c}）是因为u∈/H（S），它与H（S）的极大值因此，如果G是一个双连通的C6-free图，则G有一个大小为3的顶点集，使得H（S）是一个控制集，这意味着，由引理2.2，h（G）≤4。Q我们现在考虑强正则图，直径为2的图的一个子类。我们首先分析强正则图G（n，k，b，c），当c= 0时.在这种情况下，每个这样的图是不相交的完全图的并集定理2.11若G是强正则图G（n，k，b，c），c= 0，则h（G）≤2 ω（G）。证据若G是强正则图，且c= 0，则G有ω（G）连通分支.每个这样的连通分支都是一个具有k+ 1 =b+ 2个顶点的完全图。G的壳集可以通过连接每个分量的壳集来构造。由于组件是完全图，因此每个组件的外壳数为2。 因此，h（G）≤2ω（G）. Qc >0的强正则图是连通的非平凡k-正则图，它不是完全图。定理2.10的结果对双连通无C6一般来说，我们可以给出强正则图的一个上界，其中c>定理2.12若G是强正则图G（n，k，b，c），且c> 0，则存在一个集合SJ，使得|SJ|≤k而H（SJ）是一个支配集。证据 对于任意v∈V（G），我们有|N（v）|= k且N（v）是支配集。 考虑u∈N（v），S1={v，u}. 由于u与v相邻，u和v具有B.邻居的共同点 所以，|H（S1）|≥ |S1|+ B. 假设H（S1）至少有b+ 1个v的邻居。若N（v）<$H（S1），则H（S1）是控制集.否则存在w∈N（v）\H（S1），我们设S2={u，v，w}. 同样，由于有b是v和w之间的公共邻居，则可以得出，|H（S2）|≥ |H（S1）|+（1）+（|S1|+ b）+（b + 1），即，|H（S2）|≥ 2 b + 3。注意，由于S2的假定结构，顶点v属于H（S2\ {v}）。 因此，通过将S2重置为S2={u，w}，可以看出H（S2）至少有2个b+2个v的邻居。这个过程可以是连续的，选择顶点wi∈N（v）\H（SiJ1）并设置SJ=SJ{w i}。在第i次迭代中，H（SJ）≥i·b+i.当我·− ≥k，我们有i i−11+B，，我b+iM.R. Cappelle et al. /Electronic Notes in Theoretical Computer Science 346（2019）309317，，≤引理2.2，G有一个全集S，|S| ≤+1。Q1+B、、、1+B、、、我C−推论2.13若G是强正则图G（n，k，b，c），其中c>0，则h（G） k+1。1+B证据 根据定理2.12，G有一个控制集SJ，|SJ|≤k . 因此，1+B定理2.13给出了强正则图的一个紧界，但它没有考虑参数c。存在参数k和b之间的关系不提供紧边界的图，例如，参数为（112，30，2，10）的图GQ（3，9关于定理2.13中给出的界限，壳数至多为k+ 1 = 11，但我们通过计算确认的实际界限为2。强正则图类的另一个界可以使用参数c和算法1来建立。当H（SJ）的基数大于k时，由命题2.5可以得出H（SJ）是控制集的结论。因此，我们要确定发生这种情况时的最大迭代次数。在下面的结果中建立了这个数字的界限。引理2.14当算法1应用于强正则图G（n，k，b，c）且c> 0时，考虑算法1的第i次迭代。 如果O i/= 0，则|H（S i）|（1）（1）（|H（S i−1）|+1）。证据 考虑算法1的第i次迭代. 请注意，Oi与Hi−1的每个顶点只有c个公共顶点。所选顶点u∈Oi将被添加到Si，并且N（u）<$N（Hi−1）中的所有顶点将被包括在Hi=H（Si）。 注意|N（u）<$N（Hi−1）|=c×|Hi−1|，thatis，H（SiJ）<$H（SiJ1）<$（N（u）<$N（Hi−1））<${u}. 所以，|H（SiJ）| ≥|H（SiJ1−）|+|（N（u）<$N（H i−1）|+|{u}|. 以来|=c × |H（S i j 1）|，我们可以得出结论，|H（S i j）|≥（C + 1）| H（S i j 1）|+|+1.− −Q命题2.15如果算法1应用于强正则图G（n，k，b，c），它至多运行于i =[logc+1（kc+ 1）]|迭代证据 根据引理2.14，在算法1的每次迭代中，|H（S i）|≥（c + 1）×|+1。|+ 1.因此，在最坏的情况下，H（Si）呈指数增长。 通过求解递归式T（n）≥（c + 1）·T（n− 1）+ 1，可以证明增长率有界于|H（SJ）|≥（c +1）i−1 +1。 此外，根据2.5号提案，|> H（Si j 1）意味着O i / = 0。|>H(SiJ1)impliesthatOi/=∅. 当H（SiJ1）>k时，S oO i = 0，即当（c+1）i−1− −c+ 1≥k。 求解i，我们有i≥logc+1（kc+ 1）。 当i=[log c+1（kc + 1）|我们有H（Si）≥ k。Q给定引理2.14中证明的H（Sj）的最小增长率，我们可以分析算法1的每次迭代中集合H、S和O的基数的增长。在每次迭代中，一个新的顶点被添加到SJ，并且H（SJ）的基数乘以c+1。 也就是说，|H（S i）|≥（c +1）× |H（S i−1）|+1。318M.R. Cappelle et al. /Electronic Notes in Theoretical Computer Science 346（2019）309、、定理2.16若G是强正则图，且c>0，则h（G）≤ [log c+1（kc +1）]|+1。证据 根据引理2.14，G有一个集合SJ，使得H（SJ）是一个支配集，并且|= log c +1（kc + 1）。|= log c+1 (kc + 1) .因此，根据引理2.2，h（G）≤logc+1（kc+ 1）+1。Q表1强正则图壳数的比较结果图H科罗2.13Theor. 2.16C5（5，2，0，1）33310，3，0，1（1）343年龄：16，5，0，2363（4，4）-钩（16，6，2，2）233何鸿燊-辛格尔顿（50，7，0，1）484Geobritz（56，10，0，2）3114Brouwer-Haemers（81，20，1，6）2113M22（77，16，0，4）2174H（2， 10）（100，18，8，2）234（100，22，0，6）2234第一次潜水 McLaughlin（112，30，2，10）253卡梅伦（231，30，9，3）244贝勒坎普湖（243，22，1，2）3124麦克劳克林（275，112，30，56）253格拉斯曼J2（6， 2）（651，90，33，9）244G2（4）（416，100，36，20）243游戏（729，112，1，20）*574我们已经做了一个比较的上限上的壳数的各种图，算法1和使用的理论结果报告M.R. Cappelle et al. /Electronic Notes in Theoretical Computer Science 346（2019）309319在这项工作中。表1给出了[19，23，24]中强正则连通图的结果。320M.R. Cappelle et al. /Electronic Notes in Theoretical Computer Science 346（2019）309、1+B、、、3最后发言我们证明了如何利用P3-凸性的概念来计算直径为2的图的P3我们提出了一个多项式时间算法来确定一个P3-壳集，大小k+ 1。该算法还有利于识别的P3-壳集的强正则图的最大尺寸[logc+1（k，c+ 1）+ 1]最后，证明了双连通无C6直径2图的P3壳数至多为4，这使得在O（n4）时间内计算该子类的P3对于未来的工作，我们建议确定的P3-壳数的直径为2的图一般，即，图的直径为2，包含C6作为一个诱导子图。我们还建议确定直径为3的图的P3引用[1] Araujo，J.，V. Campos，F. Giroire，N.尼斯湖Sampaio和R. Soares，On the hull number of somegraph classes，Theoretical Computer Science，475（2013），1[2] 赤脚角，K. Casey，D. Fisher，K. Fraughnaugh，F Harary，Size in maximum triangle-free graphsand minimum graphs of diameter 2，Discrete Mathematics，138（1995），93[3] Brandt，S.，无三角形图和禁止子图，离散应用数学，120（2002），25[4] C'aceres，J.，C. Hernando，M. 莫拉岛 M. 你好，M。L. Puertas和C. Seara，Ong eodetic setsform edbyboundary vertices，Discrete Mathematics，306-2（2006），188-198.[5] 森特诺角C.的方法，L. D. Penso，D. Rautenbach和V.G.张文，张文，等。27-2（2013），717[6] 森特诺角C.的方法，M. C.多拉多湖D. Penso，D. Rautenbach和J. L. Szwarc fiter，Irreversibleconversion of graphs，Theoretical Computer Science，412-29（2011），3693[7]Changat，M.，和j.Mathew，On triangle path convexity in graphs，离散数学，206-1（1999），91[8] Coelho， E.M. M.， M. C. 多拉多湾 Raute n ba ch和J. L. Sz warc filter，弦图的凸性的Ca rat h'eodorynumber ber，离散应用数学，172（2014），104-108。[9] Costa，E. R.，M. C. Dourado，和R. M. Sampaio，与单声道凸性相关的不可逼近性结果，离散应用数学，197（2015），70[10] 多拉多湾C.的方法， J. G. Gi mbel，J. Krat ochv'ıl，F. Protti和J. L. Sz warc filter，关于图的壳数的计算，离散数学，309-18（2009），5668-5674。[11] 多拉多湾C.的方法，L. D. Penso和D. Rautenbach，关于Pk-free图的大地壳数，理论计算机科学，640（2016），52[12] 多拉多湾C.和F. Protti，D. Rautenbach和J. L. Szwarc fiter，关于无三角形图的壳数，SIAM Journal onDiscrete Mathematics，23-4（2010），2163[13] 多拉多湾C. F. Protti和J. L. Szwarc过滤器，与单声道凸性相关的复杂性结果，离散应用数学，158-12（2010），1268[14] 多拉多湾C.的方法，D. Raute n ba ch，V. Fernandes，P. M. S chafer和J. L.Sz warc filter，OntheCa rath'eodorynumber berofintervalandgraph convexitie s，TheoreticalComputerScience，510（2013），127-135.M.R. Cappelle et al. /Electronic Notes in Theoretical Computer Science 346（2019）309321[15] 多拉多湾C.的方法，和R.M. Sampaio，三角形路径凸性的复杂性方面，离散应用数学，206（2016），39[16] 杜阿尔特，M。一、L. D. Penso，D.Rautenbach和U.S. Souza，Complexity Properties ofComplementary Prisms，Journal of Combinatorial Optimization，33-2（2017），365[17] Duchet，P.，图中的凸集，II。最小路径凸性，组合理论杂志，44-3（1988），307[18] Everett，M. G.，和S. B. Seidman，图的壳数，离散数学，57-3（1985），217-223。[19] Brinkmann，G.，K. Coolsaet和J. Goedgebeur，House of Graphs：a database of interestinggraphs，Discrete Applied Mathematics，161（2013），311-314。[20] Ho Chuanman，A. J.， 和R. R. Singleton，On Moore Graphs with Diameters 2 and 3，IBM J. Res. 德夫，4-5（1960），497[21] 你 好 ， M 。 M. 和 L. Nourine， Polynomialtimealgorithmsfor computing aminimumhul setindistance-hereditary and chordal graphs ， SOFSEM 2013 ： Theory and Practice of Computer Science ，（2013），268-279。[22] 彭索湖D、F. Protti，D. Raute n ba ch和U. S. Souza，有界度和平面图上P3- c凸问题的复杂性分析，理论计算机科学，607（2015），83-95。[23] Spence，E.，Strongly Regular Graphs on至多64 vertices，10th Annual ACM-SIAM Symposium onDiscrete Algorithms（2012）。[24] Weisstein，E.W.，http://mathworld.wolfram.com/StronglyRegularGraph.html网站。
