冠图P25Cm的2种度结合边重构数*1

石黄萍， 马美杰

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

冠图P25Cm的2种度结合边重构数*1

石黄萍， 马美杰

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

通过分析冠图P5C的一个边主子图可能重构的图的结构,确定了它的2种边度结合重构数,进一步丰富了结构图论的内容.

冠图;重构;边主子图;度结合边重构数

0 引 言

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的边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等[5]确定了当图G为正则图、完全二部图、路、轮图、双星图或平衡三部图时,dern(G)和adern(G)的值.

G1和G2的冠图,是指G1的一个拷贝和G2的|V(G1)|个拷贝,且G1的第i个顶点与G2的第i个拷贝的每个顶点均相连,记为G15G2.2011年,田京京[6]研究了某些广义冠图的强边染色;2013年,Monikandan等[7]确定了Cn5Km和Pn5K1的2种度结合边重构数.

记Δ(G)为G的最大度,δ(G)为G的最小度;用Pn(n≥1)表示n阶路;Cm(m≥3)表示m阶圈.记Pn5Cm为Pn和Cm的冠图.

1 主要结果

引理1若图G有一条边e满足d(e)=0或者在G-e中除e的端点之外的任何2个不相邻点的度和不等于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.引理1证毕.

定理1令G=P25Cm(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的证明可以得到如下推论:

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

定理2令G=P25Cm,若m≥3,则

证明 图G中的度结合边主子图只有3种情况,分别为:(G-e1,4),(G-e2,m+2),(G-e3,2m).则它们的边度分别为4,m+2,2m.由推论1知,边度为4的度结合边主子图(G-e1,4)可重构图G.

下证度结合边主子图(G-e3,2m)可重构图G.令H′表示可由(G-e3,2m)重构的图,即在边主子图G-e3中添加一条2m度边e′.当m=3时,G-e3中所有的顶点都是3度点,任意连接2个不相邻的3度点得到图H′, 有H′≅G.当m≥ 4时,在边主子图G-e3中除边e3的2个端点外,任何2个不相邻点的度和不等于d(e3).由引理1知,该边主子图可重构图G.

故下面考虑边度为m+2的度结合边主子图的重构.

当m=3时,只须证明3个度结合边主子图(G-e2,5)可重构图G.由图G-e2的结构知,图G-e2恰有一条割边.图H′表示在边主子图G-e2中添加一条5度边e′得到的图.若H′G,则在H′中只有在2条5度边删除后才有割边,故H′至多含有2个(G-e2,5).因此,adern(G)≤3.由图1(a)与图G有2个相同的公共度结合边主子图(G-e2,5)可知,adern(G)≥3.

当m=4时,只须证明2个度结合边主子图(G-e2,6)可重构图G.由于边主子图Δ(G-e2)=5且只有一个最大度点,不妨设d(v)=Δ(G-e2)=5,则v在G-e2中有一个4度邻点.图H′表示在边主子图G-e2中添加一条6度边e′得到的图.若H′G,则图H′只含一个最大度点v且d(v)=5.若在图H′中删除不同于e′的6度边e"后得到边主子图G-e2,则边e"与点v不关联.若e′的端点分别在图G的2个Cm圈中,则此时H′无割边,且在图H′中删除不同于边e′的6度边e"后得到的图都不含割边.而在边主子图G-e2中有一条割边.若e′的端点在图G的同一Cm圈中且e2的端点不在该圈上,则图H′中的6度边都与点v关联.若e′的端点在图G的同一Cm圈中且e2的一个端点在该圈上,则在H′-e"中与v相邻的点均为3度点,而在G-e2中与v相邻的点有一个4度点.故图H′的边主子图集不含2个边主子图G-e2.因此,adern(G)≤2.由图1(b)与图G有一个公共的度结合边主子图(G-e2,6)知,adern(G)≥2.

图1 与图G有公共度结合边主子图的重构图

当m≥5时,在边主子图G-e2中,由于m+2≥7,所以除去边e2的2个端点外,任何2个不相邻点的度和不等于m+2.由引理1知,该边主子图可重构图G.因此,adern(G)=1.定理2证毕.

2 结 语

本文通过分析冠图P25Cm的一个边主子图可能重构的图的结构,确定了它的2种边度结合重构数.对于一般的冠图Pn5Cm,笔者将进一步确定它的2种边度结合重构数.

[1]Ulam S M.A collection of mathematical problems[M].New York:Interscience Publishers,1960:20.

[2]Harary F.On the reconstruction of a graph from a collection of subgraphs[C]//Fielder M.Theory of Graphs and its Applications.New York:Academic Press,1964:47-52.

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

[4]杜鹃,吕嘉钧.有向路的重构[J].南通大学学报:自然科学版,2006,5(1):1517.

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

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

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

(责任编辑 陶立方)

TwokindsofdegreeassociatededgereconstructionnumbersofcoronagraphP25Cm

SHI Huangping, MA Meijie

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,JinhuaZhejiang321004,China)

Two kinds of degree associated edge reconstruction numbers of the graphP25Cmwere determined by considering the possible reconstructions from a degree-associate edge-card. The results enriched the structure property of graphs.

corona graph; reconstruction; edge-card; degree-associate edge reconstruction number

10.16218/j.issn.1001-5051.2015.02.09

2014-11-03

国家自然科学基金项目资助(11101378)

石黄萍(1990-),女,江西上饶人,硕士研究生.研究方向:图论.

马美杰.E-mail: mameij@zjnu.cn

O157.5

A

1001-5051(2015)02-0176-03