冠图P3·Cm的两种度结合边重构数

黄陈辰，石黄萍

（浙江师范大学 数理与信息工程学院，浙江金华321004）

冠图P3·Cm的两种度结合边重构数

黄陈辰，石黄萍

（浙江师范大学 数理与信息工程学院，浙江金华321004）

摘要：边重构猜想是指至少含有边的图能被它的边主子图集所决定,通过分析冠图的一个边主子图可能重构的图的结构,确定了它的两种边度结合重构数,进一步丰富了结构图论的内容.

关键词：冠图;重构;边主子图;度结合边重构数

Ulam猜想［1］:如果图G和H分别是包含n个顶点ui和vi的图(n≥3)，对于所有的i，都有G-ui同构于H-vi，则G和H同构.Ulam猜想吸引许多学者对其进行研究.其后，Harary提出了边重构猜想［2］，即至少含4条边的图能够被它的边主子图集所决定，其中，边主子图是指在图G中删除一条边e后所得到的子图，记为G-e.用d(v)表示图G中顶点v的度，记△(G)为G的最大度，δ(G)为G的最小度，对于图G的边e=uv，其边度为d(e)=d(u)+d(v)-2.度结合边主子图是指由边主子图和它所删除边的边度组成，记为(G-e,d(e)).度结合边重构数是指能重构图G的所需的度结合边主子图的最少个数，记为dern(G).一致度结合边重构数是指任意k个度结合边主子图都能重构图G的最小整数k,记为adern(G).本文主要考虑度结合边主子图的边重构问题，以进一步丰富结构图论的内容.

关于图的重构已经有了一些重要的结论.2003年，刘桂真等给出了两类图同构的一个充分必要条件［3］; 2006年，杜鹃等研究了有向路的重构［4］；2012年，Monikandan等确定了当图G为正则图、完全二部图、路、轮图、双星图或平衡三部图时，这两种度结合边重构数的值［5］.2011年，田京京研究了某些广义冠图的强边染色［6］;2013年，Monikandan等确定了Cn·Km和Pn·K1的两种度结合边重构数［7］.本文是在这些结论的基础上继续研究冠图的两种边度结合重构数.

1　相关引理

G1和G2的冠图，是指G1的一个拷贝和G2的|V(G1)|个拷贝，且G1的第i个顶点与G2的第i个拷贝的每个顶点均相连，记为G1·G2.本文研究的是冠图P3·Cm，其中P3是指3个顶点的路，Cm是指m个顶点的圈.

引理1若图G有一条边e满足:d(e)=0或者在G-e中除e的端点之外的任何两个不相邻点的度和不等于d(e)，则度结合边主子图(G-e,d(e))可重构G.

证考虑在边主子图G-e中加一条边度为d(e)的边e的重构图.若d(e)=0，则边e的2个端点在边主子图G-e中的度都为0，即边e是连接G-e中的2个孤立点，故产生的图与G同构.对于另一种情况，考虑G-e中不相邻的2个顶点的度和.因为只有边e的2个端点的度和为d(e)，所以边e的2个端点只能是边e的2个端点，从而获得的图也同构于G.证毕.

引理2令G=P3·Cm(m≥3)，则G的度结合边主子图(G-e,2m+1)可重构图G.

证图H表示在边主子图G-e中添加一条2m+1度边e得到的图.因为2m+1≥9，边e的端点只能是G-e中2个不相邻的m和m+1度点，由引理1知，H≅G.

引理3令G=P3·Cm(m≥3)，则G的任意两个不同的度结合边主子图S可重构图G.

证令H表示可由S重构的图.若S包含边度为4的度结合边主子图(S-e,4)，则由引理1知，H≅G.下面考虑S不包含边度为4的度结合边主子图.图G中不等于4的边度可能情况为:m+2,m+3,2m+1.记其度结合边主子图分别为(G-e1,m+2)，(G-e2,m+3)，(G-e3,2m+1).

若(G-e3,2m+1)∈S，图H表示在边主子图G-e3中添加一条2m+1度边e得到的图.当m≥4时，由引理2知，有H≅G.当m=3时，若H≇G，此时边e的2个端点在G-e3的同一分支K中，即H含有2个连通分支.而边主子图G-e1，G-e2都是连通图.因此图H的边主子图集不含G-ej(j∈{1,2}).即集合S可重构图G.

下设S={(G-e1,m+2),(G-e2,m+3)}，图H表示在边主子图G-e2中添加一条m+3度边e,得到的图.若H≇G，因为m≥3，边e的2个端点分别在路P3和某个圈Cm上，且m=3时，边e的2个端点还可能在2个Cm圈上，但重构图H都至多有1条割边，从H中删除m+2度边后的图仍至多有1条割边，而边主子图G-e2有2条割边，故图H的边主子图集不含G-e1.因此集合S可重构图G.证毕.

2　主要结果

定理1令G=P3·Cm(m≥3)，则dern(G)=1.

证在G中取Cm中的一条边e，其度结合边主子图为(G-e,4).在G-e中，由m≥3知，除去边e的2个端点外，任何2个不相邻点的度和至少为5.由引理1知，由G-e重构的图同构于G.故dern(G)=1.证毕.

由定理1的证明，得到如下推论.

推论1令G=P3·Cm(m≥3)，则G的度结合边主子图(G-e,4)可重构图G.

定理2令G=P3·Cm(m≥3)，则：

证由推论1知，度结合边主子图(G-e,4)可重构图G.由引理3知，任意2个不同的度结合边主子图可重构图G，故下面只考虑度结合边主子图集S含有相同的且边度大于4的度结合边主子图.图G中不等于4的边度的可能情况分别为:m+2,m+3,2m+1.记其度结合边主子图分别为(G-e1,m+2)，(G-e2,m+3)，(G-e3,2m+1).

情况1m+3.

由图1中的重构图与图G有2个公共的度结合边主子图(G-e3,7)可知，adern(G)≥3.下面证图G的任何3个相同的度结合边主子图集S都能重构图G.

若(G-e2,6)∈S，则图H表示在边主子图G-e2中添加一条6度边e得到的图.若H≇G且e的端点在图H-e的不同Cm圈中，则此时H中只有1条不同于e的6度边e″满足删除它后有2条割边，但H-e″的直径至少为5，而G-e2的直径为4.若H≇G且e的端点分别在图G-e3的路P3和某个Cm圈中，则此时H只有1条割边，H-e″仍只有1条割边，而G-e2有2条割边.故若H≇G时，它的边主子图集不含2个度结合边主子图(G-e2,6).

若(G-e1,5)∈S，图H表示在边主子图G-e1中添加1条5度边e得到的图.若H≇G，则此时H至多有1条割边，令e″表示不同于e的5度边，则H-e″仍至多有1条割边，而G-e1有2条割边.故若H≇G时，它的边主子图集不含2个度结合边主子图(G-e1,5).

因此，adern(G)=3.

情况2m≥4.

由引理1知，adern(G)≥2.只要证明图G的任何2个相同的度结合边主子图集S都能重构图G即可.由引理2知，S不包含度结合边主子图(G-e3,2m+1).

若(G-e2,m+3)∈S，图H表示在边主子图G-e2中添加一条m+3度边e得到的图.因为m+3≥7，所以若H≇G，则e的2个端点分别在路P3和某个Cm上.此时H至多有1条割边，从中删除不同于e的m+3度边e″后仍至多有1条割边，而G-e3有2条割边.故若H≇G,时，它的边主子图集不含2个度结合边主子图(G-e2,m+3).

若(G-e1,m+2)∈S，图H表示在边主子图G-e1中添加一条m+2度边e得到的图.当m≥5时，由m+ 2≥7和引理1可知有H≅G.当m=4时，若H≇G且e的2个端点在不同C4圈中，则此时H至多有1条割边，从中删除不同于e的6度边e″后仍至多有1条割边，而G-e1有2条割边.若H≇G且e的2个端点在同一圈C4中，则H有3个4度点，而G-e1只有一个4度点.故删除不同于e的6度边e″的2个端点都为4度点.所以在H-e″中无4度点与6度点相邻，而在G-e1中一个4度点与6度点相邻.故若H≇G时，它的边主子图集不含2个度结合边主子图(G-e1,m+2).

因此adern(G)=2.证毕.

3　结语

本文通过分析冠图P3·Cm的一个边主子图可能重构的图的结构,确定了它的两种边度结合重构数,结论分别为:当m≥4时,adern(G)=2,当m=3时，adern(G)=3.对于一般的冠图Pn·Cm,由于边主子图集里的边主子图是多样的,重构过程很复杂,未来可进一步确定它的两种边度结合重构数.

参考文献:

［1］Ulam S M.A collection of mathematical problems［M］.New York-London：Interscience Publishers，1960:20.

［2］Harary F.On the reconstruction of a graph from a collection of subgraphs［M］.Prague：Theory of Graphs and its Applications,1964: 47-52.

［3］刘桂真,禹继国,谢力同.两类图同构的充分必要条件［J］.山东大学学报:理学版,2003,3(1):1-4.

［4］杜鹃,吕嘉钧.有向路的重构［J］.南通大学学报:自然科学版,2006,5(1):15-17.

［5］Monikandan S,Anusha Devi P,Sundar Raj S.Degree associated edge reconstruction number［J］.Combinatorial Algorithms,2012, 7643(3):100-109.

［6］田京京.若干圈的广义冠图的-强边染色［J］.数学杂志,2011,31(5):938-944.

［7］Monikandan S,Anusha Devi P,Sundar Raj S.Degree associated edge reconstruction number of graphs［J］.Journal of Discrete Algorithms,2013,23(2):35-41.

（责任编辑：邵晓军）

中图分类号：O157.5

文献标识码：A

文章编号：1007-5348（2015）06-0005-03

［收稿日期］2014-11-06

［基金项目］国家自然科学基金项目（11101378）.

［作者简介］黄陈辰（1990-），女，浙江海宁人，浙江师范大学数理与信息工程学院硕士研究生；研究方向：图论.

Two Kinds of Degree-associated Edge Reconstruction Numbers of P3· Cm

HUANG Chen-chen,SHI Huang-ping
（College of Mathematics,Physics and Information Engineering, Zhejiang Normal University,Jinhua 321004,Zhejiang,China）

Abstract:Edge-reconstruction conjecture states that every graph with more than three edges is determined by its edge-card.Two kinds of degree associated edge reconstruction numbers of the graph P3·Cmare determined by considering the possible reconstructions from a degree-associate edge-card.The results enrich the structure property of graphs.

Key words:corona graph;reconstruction;edge-card;degree-associate edge reconstruction number