图论本科毕业论文--符号控制数.doc 33页

'华东交通大学毕业论文图论本科毕业论文--符号控制数目录摘要2ABSTRACT3第一章引言4第二章图的符号边控制62.1、星图符号边控制数72.2、路径的符号边控制数82.3、圈的符号边控制数92.4、树的符号边控制数112.5、正则图的符号边控制数132.6、符号星控制数的界16第三章结论18第四章谢辞19参考文献20附录21A外文翻译原文部分21B外文翻译译文部分28-33- 华东交通大学毕业论文关于图的边控制数摘要本文综述了近期关于图的边控制数的若干结果，例如星图，路径，圈，树，正则图的符号边控制数的一些确切值或其界值。同时对其中的一些结果给出了另一种证明方法。在路径和圈的问题上，提出了结构单元的思想，从而有效地减少了讨论情况。在树的符号边控制数的论证过程中，提出了把树拆分成若干星图，利用星图的结论进行论证得到树的符号边控制数的下界。并且给出了等号成立的一种条件图。最后对一般图的符号星控制数给出了一个新的下界，并且给出了详细的证明过程。关键词：符号边控制函数，符号星控制函数，符号边控制数，符号星控制数,结构单元-33- 华东交通大学毕业论文OnedgedominationnumbersofgraphsABSTRACTThispapersummarizessomeresultsonedgedominationnumbersofgraphsinthepastperiods,suchassomeaccuratevaluesonedgedominationnumbersofthestargraph,path,circuit,treeandtheregulargraphortheirboundaryvalue.Meanwhileithasprovidedanothercertificatemethodtosomeresults.Inthetreeandthecircuitquestion,theauthorhasputforwardthestructuralunittheory,reducedtheclassificationdiscusscircumstanceeffectively.Duringtheproofprocessonedgedominationnumbersofthetree,theauthorputforwarddismantlingatreetoseveralstargraphs,andgetthelowerboundofthesignededgedominationnumberstree,gettheconclusionbymakinguseofthestargraph"s.Andtheauthorgivesanequalityconditiongraphwhentheequalmarkistenable.Finallygiveanewlowerboundtothegeneralgraphofthesignedstardominationnumber,andgivesthedetailedcertificateprocess.Keywords:Signededgedominationfunction,Signedstardominationfunction,Signededgedominationnumber,Signedstardominationnumber,Structuralunit-33- 华东交通大学毕业论文第一章引言本文所指的图，均为无向简单且连通图，本文中未加说明的符号和术语均同于文献[1]。设一图,其中分别是的点集和边集。当时，且记集合则表示点在中的邻域，同时集合表示点在中的闭邻域，为点在中的度，为了方便起见，有时将分别简记为若时，且记集合则表示点在中的邻域，表示边在中的闭邻域,表示边在中的度，很明显同理，将分别简记为若则记集合表示点在中的边邻域，简记.为了帮助理解以上几个概念，我们用图1-1说明如下：⑴⑵⑶图1-1-33- 华东交通大学毕业论文⑴、是原图；⑵、表示，和；⑶、表示和近几年来，图的控制理论研究的内容越来越广泛，各类控制概念相继产生，而且研究成果不断丰富，同时也为图论研究提供了许多新思维和新方法。T.W.Haynes等人的两部专著[5~6]综述了近些年来图的控制理论研究方面的主要研究成果，这部分主要讨论的绝大多数属于图的点控制。徐保根教授又在文[2~3]中分别引入了图的两种边控制概念即：符号边控制和符号星控制；在文[7]中引入了另一种边控制概念即：图的符号圈控制；近期徐教授还对边控制概念进行延拓，提出了局部符号控制概念。在这一系列的研究过程中徐教授得出了较多的研究成果，大力地推动了图的控制理论的发展。定义1.1：设是一个图,一个二值函数称作为符号边控制函数,如果对任意边都成立,的符号边控制数定义为：定义1.2：设是一个图,一个二值函数称作为符号星控制函数,如果对任意顶点都成立,的符号星控制数定义为：对于空图,有定义-33- 华东交通大学毕业论文第二章图的符号边控制引理2.1：(Xu[3])对于任何两个点不相交的图,我们有：和.若讨论的是图不连通则可以使用此引理得到相应的结果。定义2.1：设是一个图，表示图的顶点序列，称为，如果也就是说均包含一个圈和两个端点在圈上的一条路。图2-1定理2.1：任意一个均包含一个偶圈（圈含有偶数条边）证明：不失一般性，假设是一个连通图，首先我们把图分成两个子图，根据的定义，我们把度数为3的顶点进行标记为，，而两个子图满足：同时可以知道定点度数含有两种值。为此我们分以下两种情况讨论：⑴、我们假设中含有偶数个2.根据路-33- 华东交通大学毕业论文的长度也分为两种情况讨论：①、当为奇数，则为奇数，从而可知必定是一奇一偶，由的定义知均为圈，故必定有一个是偶圈.结论成立。②、当为偶数，则为偶数，故取则也为偶数，结论成立。⑵、我们假设中含有奇数个2.根据路的长度也分为两种情况讨论：①、当为奇数，则为偶数，故取则也为偶数，结论成立。②、当为偶数，则为奇数，从而可知必定是一奇一偶，由的定义知均为圈，故必定有一个是偶圈.结论成立。综上所述，我们得知结论成立。□2.1、星图符号边控制数定理2.2：设是一个星图，且，若为奇数则，若为偶数则.证明：如图2-2是一个星图，很明显，有对则.如果是的图2-2星图-33- 华东交通大学毕业论文则因为故分为两种情况：①、若为奇数，则令.则的取法为，其中任取条边标记为，记为且，取剩余的为，知，故.②、若为偶数，则令.则的取法为，其中任取条边标记为，记为且，取剩余的为，知，故.综上所述，结论成立。□2.2、路径的符号边控制数定理2.3：对任意一条路，那么它的符号边控制数由以下关系：证明：首先分析路的特性。在路中任选一条边，假设若对定义为，则两端的边必有；若对定义为，则两端的边必有两边的函数值之积为即：.由此，我们可以构造一个结构单元如图2-3⑴所示，使得.即此结构只在中间出现不能够在两端出现，同时必定有两端的四条边满足.⑴结构单元-33- 华东交通大学毕业论文⑵图2-3由以上定义的可知满足符号边控制函数的定义。接下来我们来讨论计算符号边控制数，分三种情况讨论：⑴则知有个结构单元剩余三条边不在结构单元中有定义知；⑵则知有个结构单元剩余四条边不在结构单元中有定义知；⑶则知有个结构单元剩余两条端边不在结构单元中有定义知.综上所述，本定理结论成立。□2.3、圈的符号边控制数定理2.4：对任意一条路，那么它的符号边控制数由以下关系：证明：同定理2.3首先分析圈的特性。我们同样通过构造如图2-3⑴的结构单元来定义符号边控制函数，如图2-4我们也分为三种情况进行讨论：-33- 华东交通大学毕业论文图2-4⑴则从开始三个一组划分，所有的边都在如图2-3⑴的结构中，且均满足符号边控制函数的定义，故.⑵则知除去终边外，从开始三个一组划分，所有的边都在如图2-3⑴的结构中，且均满足符号边控制函数的定义，而，故.⑶则知除去两条边外，从开始三个一组划分，所有的边都在如图2-3⑴的结构中，且均满足符号边控制函数的定义，而.故综上所述，本定理结论成立。□在以下的定理证明过程当中，首先需要对一些术语和数学符号进行声明一下。设是一个图，且，表示从图中通过删除边的同时增加一条新的边，其中.很明显有，且，如图2-5所示⑴图表示原图，⑵图表示。-33- 华东交通大学毕业论文⑴⑵图2-5设是一个图，它的为，则我们记为一个符号图。对于一个符号图，我们由定义1.1可知.简单地说，给定一个符号图，一条边，若则在图上标记为，类似地，若则在图上标记为.我们记：.对于任意的符号图，它的两个生成子图和定义为同时我们称和分别为符号图的正负子图。一般地，对于任意一个顶点，称为顶点在符号图上的符号度数，若有.在不混淆的情况下我们可以把简记为.2.4、树的符号边控制数定理2.5：对任意一棵树，则有其控制数.证明：很明显任意一棵树都可以分解为若干星图的并，即有，星图之间的连接边为依据上面所述，我们对下图进行分解-33- 华东交通大学毕业论文图2-6可以分解为分别以为中心的个星图。若是树的符号边控制函数，对于连接边来说需要分两种情况讨论：①、若，首先由定义知.有上边的不等式可知,为此我们构造以及同时重新定义符号边控制函数：如图2-6所示⑴⑵图2-7在这里顶点数增加了2，正边数增加了一条，同时符合符号边控制函数的定义；②、若，且假设包含条这样的边，则直接删除边，我们有符合符号边控制函数的定义；-33- 华东交通大学毕业论文因为，则可知，那么，最后我们得到个星图及其符号边控制函数，由定理2.2可知所以.最后得到定理结论.□同时，我们可以构造出一类图使得定理的等号成立（如图2-7所示）。若树有则树满足以下条件：①、对于任意顶点，有，且为奇数；②、当时，含有两条悬挂边时，只有一条边标，另一条边标；③、当时，含有悬挂边，且悬挂边标记为，非悬挂边标记为.图2-72.5、正则图的符号边控制数引理2.2：(吉[9])任意一个都可以分解为一个和一个.定理2.6：任意有-33- 华东交通大学毕业论文证明：首先证明，设为一个的一个，由的定义可知，对于，有都成立，且是正则图。由的定义可知，.设是一个，若对，对于边的闭邻域，有条边，在这些边中，我们至少要取条边为，而剩余的（最多条）边为，如图2-8所示。图2-8则有对于，有都成立，由此得到，故.对于我们用数学归纳法进行证明，首先我们需要分两种情况分比别讨论初值成立。①、，时，令，根据引理2.2知是一个，是一个。对此我们对于图定义二值函数:使得-33- 华东交通大学毕业论文如图2-9所示⑴⑵图2-9从而是一个图的显然有.命题成立。②、，时，令，根据引理2.2知是一个，是一个且无割边。对此我们对于图定义二值函数:使得如图2-10所示⑴⑵图2-10从而是一个图的显然有.命题成立。假设时命题也成立，即成立，且对于任意顶点.下面证明时命题也成立。设图是一个边连通正则图，由于，因此利用引理2.2两次可以把图分解为，其中和是两次分解中分别得到的，是最后一次得到的边连通正则图，同时可知.-33- 华东交通大学毕业论文现在我们来定义为，首先由假设可知存在的为，则我们可以如下定义函数：因此当时当时，记，当时，记，均有成立则，是的，同时又有故当时命题也成立。综上所述，命题结论成立。□2.6、符号星控制数的界定理2.7：对于任意给定的图表示顶点的最大度数，表示顶点的最小度数，则有成立。证明：取是图的，则对任意一条边有-33- 华东交通大学毕业论文对上式遍历图的每条边进行求和（注：每个顶点必须经历它在图中的算术顶点度数的统计）故上式等于由的定义知道故上式大于等于又且所以故成立。□-33- 华东交通大学毕业论文第三章结论本课题研究的是图控制中的边控制理论。在研究的过程中，我们了解了图的一些控制数的重要前沿理论，进一步地学习了数学思维的严谨性。同时系统地了解了图的基础理论，掌握了图论的研究思想和方法。最后，也尝试提出自己的方法对已有的结果进行重新论证，或者提出自己简单的猜想进行论证，最后得到结果。我们重新论证了常见图的一些符号边控制数的结论：⒈设是一个星图，且，若为奇数则，若为偶数则；⒉对任意一条路，那么它的符号边控制数由以下关系：；⒊对任意一个圈，那么它的符号边控制数由以下关系：；⒋对任意一棵树，则有其控制数；⒌任意有；另外还提出了自己的结论且给出了详细证明：⒍对于任意给定的图表示顶点的最大度数，表示顶点的最小度数，则有成立。-33- 华东交通大学毕业论文第四章谢辞值此论文完成之际，谨向给予我指导、关心和帮助的老师、同学、亲人朋友表示最衷心的感谢！首先，向我的指导老师徐保根、刘二根老师表示衷心的感谢。在本科阶段的学习和论文的撰写过程中，两位老师给予了我无私的指导和真诚的帮助。学习上，对我也是严格要求、一丝不苟，而徐老师和刘老师在学术上的谦虚好学与严谨性，在教学上的认真负责的风范更令我深深地折服。在课题研究的过程中得到了陈相兵、章志平、尹继昌、金科同学给予了我正确的指正和帮助，使得本课题得以顺利完成，在此向他们表示感谢。感谢我的室友，谢谢他们在生活上和学业上给予我的关心和帮助。向百忙之中抽空评阅本论文的老师表示衷心的感谢，并感谢他们的宝贵意见。感谢所有的师长，感谢他们在我大学四年的路程中给予本人思想上，生活上，学业上的教导。最后，我要感激我的父母和其他亲人所给予我的关怀和支持。-33- 华东交通大学毕业论文参考文献[1]F.哈拉里.图论[M].上海科技出版社，1980.[2]B.Xu.Onsignededgedominationnumbersofgraphs[J].DiscreteMath,239(2001)179-189[3]B.Xu.Onedgedominationnumbersofgraphs[J].DiscreteMath,249(2005)311-316[4]B.Xu.OnMinusDominationandSignedDominationinGraphs[J].JournalofMathematicalResearch&Exposition,1000-341X(2003)04-0586-05[5]T.W.Haynes,S.THedetniemi,P.J.slater.Dominationingraphs[M].NewYork,1998.[6]T.W.Haynes,S.THedetniemi,P.J.slater.Fundamentalsofdominationingraphs[M].NewYork,1998.[7]徐保根.图的符号控制.华东交通大学学报[J].1005-0523（2005）05-0135-03[8]BOHDANZELINKA,Liberec.Onsignededgedominationnumberoftrees[R].MathematicalBohemia,127(2002)No.148-55[9]吉日木图.关于正则图的符号边控制数[R].O157.5[10]Z.Zhang,B.Xu,Y.Li,L.Liu.Anoteonthelowerboundsofsigneddominationnumberofagraph[J].DiscreteMath，195(1999)-295-298[11]J.A.Bondy,V.S.R.Murty.GraphTheorywithApplications[M].Elsevier,Amsterdam,1976[12]徐保根.关于图的符号边控制数[J].华东交通大学学报，1005-0523（2003）02-0102-04[13]徐保根.一类偶图的符号边控制数[J].华东交通大学学报，1005-0523（2004）02-0102-03[14]徐保根.关于图的符号边控制数的下界[J].华东交通大学学报，1005-0523（2004）01-0110-04[15]徐保根.关于图的边函数控制数的注记[J].华东交通大学学报，1005-0523（1999）02-0072-03[16]E.J.Cockayne,C.M.Mynhardt.Onageneralizationofsigneddominationfunctionofgraphs[J].ArsCombin.43(1996)235-245[17]XUBao-gen,ZHOUShang-chao.Characterizationofconnectedgraphsforinequalitiesinvolvingdominationparameters[J].DiscreteMath.,2000,216:1-10-33- 华东交通大学毕业论文附录A外文翻译原文部分ONSIGNEDEDGEDOMINATIONNUMBERSOFTREES①BohdanZelinka,Liberec(ReceivedApril18,2000)Abstract.Thesignededgedominationnumberofagraphisanedgevariantofthesigneddominationnumber.Theclosedneighborhoodofanedgeeinagraphisthesetconsistingofeandofalledgeshavingacommonendvertexwithe.Letbeamappingoftheedgesetofintotheset.Ifforeach,theniscalledasignededgedominatingfunctionon.Theminimumofthevaluestakenoverallsignededgedominatingfunctionon,iscalledthesignededgedominationnumberofandisdenotedby.Ifinsteadoftheclosedneighborhoodweusetheopenneighborhood,weobtainthedefinitionofthesignededgetotaldominationnumberof.Inthispapertheseconceptsarestudiedfortrees.Thenumberisdeterminedforbeingastarofapathoracaterpillar.Moreover,alsoforacircuitoflengthnisdetermined.Foratreesatisfyingacertainconditiontheinequalityisstated.Anexistencetheoremforatreewithagivennumberofedgesandgivensignededgedominationnumberisproved.Attheendsimilarresultsareobtainedfor.Keywords:tree,signededgedominationnumber,signededgetotaldominationnumberMSC2000:05C69,05C05Weconsiderfiniteundirectedgraphswithoutloopsandmultipleedges.Theedgesetofagraphisdenotedby,itsvertexsetby.Twoedgesofarecalledadjacent-33- 华东交通大学毕业论文iftheyaredistinctandhaveacommonendvertex.Theopenneighborhoodofanedgeisthesetofalledgesadjacentto.Itsclosedneighborhood.Ifweconsideramappingand,thenwedenoteAmappingiscalledasignededgedominatingfunction(orsignededgetotaldominatingfunction)on,if(orrespectively)foreachedge.Theminimumofthevalues,takenoverallsignededgedominating(orallsignededgetotaldominating)functionson,iscalledthesignededgedominationnumber(orsignededgetotaldominationnumberrespectively)of.ThesignededgedominationnumberwasintroducedbyB.Xuin[1]andisdenotedby.Thesignededgetotaldominationnumberofisdenotedby.AsignededgedominatingfunctionwillbeshortlycalledSEDF,asignededgetotaldominationfunctionwillbecalledSETDF.Thenumberisanedgevariantofthesigneddominationnumber[2].Rememberanothernumericalinvariantofagraphwhichconcernsdomination.Asubsetoftheedgesetofagraphiscallededgedominatinginifeachedgeofeitherisin,orisadjacenttoanedgeof.Theminimumnumberofedgesofanedgedominatingsetiniscalledtheedgedominationnumberofanddenotedby.Weshallstudyandinthecasewhenisatree.Proposition1.Letbeagraphwithmedges.Then.Proof.LetbeaSFDFofsuchthat.Letbethenumberofedgesofsuchthat(orrespectively).Wehave,andhence.Thisimpliestheassertion.Proposition2.Letbethreeverticesofatreesuchthatisapendantvertexofand-33- 华东交通大学毕业论文isadjacenttoexactlytwovertices.LetfbeaSFDFon.ThenProof.Wehaveand.Thisimpliestheassertion.Proposition3.Letbeastarwithedges.Ifisodd,thenIfmiseven,then.Proof.Inastaralledgesarepairwiseadjacentandthusforeach.IfisaSEDF,thenandthus.Letbethenumberofedgesofsuchthat;then.Ifisodd,wemaychooseafunctionsuchthatandthen.Ifiseven,thevalueisalwayseven;wemaychooseafunctionsuchthatandthen.Let.Theneighborhoodsubtreeofisthesubtreeofwhoseedgesetisandwhosevertexsetisthesetofallendverticesoftheedgesof.Ifisapendantedgeof,thenisthestarwhosecentralvertexisthevertexofhavingthedegreegreaterthan1;thisisthemaximal(withrespecttosubtreeinclusion)subtreeofofdiameter2containing.Intheoppositecaseisthemaximalsubtreeofofdiameter3whosecentraledgeis.Thesetofallsubtreesforwillbedenotedby.Theorem1.Letbeatreehavingthepropertythatthereexistsasubsetofconsistingofedge-disjointtreeswhoseunionis.Then.Proof.Letbethesetofedgesesuchthat.Foreachthesetisthesetofneighboursofeandtheunionofallthesesetsis.Thusisanedgedominatingsetin-33- 华东交通大学毕业论文.Therefore.LetbeanSEDFofsuchthat.Asthetreesfromarepairwiseedge-disjoint,wehave.AsforeverytreeT,wehaveacorollary.Corollary1.LethavethepropertyfromTheorem1.Then.Conjecture.Foreverytreewehave.Bythesymbolwedenotethepathoflength,i.e.withedgesandvertices.Bywedenotethecircuitoflength.Theorem2.ForthesignededgedominationnumberonapathwithwehaveProof.LetbeanSEDFonsuchthat.Denote,.Evidentlyeachedgeofmustbeadjacenttoatleasttwoedgesofandeachedgeofisadjacenttoatmostoneedgeof.ByProposition2betweenanedgeofandanendvertexofthereareatleasttwoedgesofandalsobetweentwoedgesofthereareatleasttwoedgesof.Henceand.Ifwechooseoneendvertexofandnumbertheedgesofstartingatit,wemaychooseafunctionfsuchthatifandonlyifthenumberofeisdivisibleby3andlessthan.The-33- 华东交通大学毕业论文andthisis.Andthisnumbertretedseparatelyforparticularcongruenceclassesmodulo3canbeexpressedasinthetextofthetheorem.Asanaside,westateanassertiononcircuits;itsproofisquiteanalogoustotheproofofTheorem2.Theorem3.ForthesignededgedominationnumberofacircuitwehaveNowweshallinvestigatecaterpillars.Acaterpillarisatreewiththepropertythatupondeletingallpendantedgesfromitapathisobtained:thispathiscalledthebodyofthecaterpillar.Particularcasesofcaterpillarsincludestarsandpaths.Lettheverticesofthebodyofbeandedgesfor.Forletbethenumberofpendantedgesincidentto.Thefinitesequencedeterminesthecaterpillaruniquely.Fromthedefinitionitisclearthatand.Ifk=1,thensuchacaterpillarisastar.If,for,thenitisapath.Theorem4.Letbeafinitesequenceofintegerssuchthat,,for.Letbethenumberofevennumbersamongthenumbers.Letbethecaterpillardeterminedbythissequence.Then.Proof.Theassumptionofthetheoremimpliesthateachvertexofthebodyofisincidenttoatleastonependantedge.ForletbethesetofalledgesincidenttoLetbeavertexofthebodyofandletebeapendantedgeincidenttoit.Wehave.WehaveforHence.Thefunctionfmaybedescribedinthefollowing-33- 华东交通大学毕业论文way.Ifor,thenforexactlypendantedgesefromifisevenandforexactlyonesifisodd.If,thenforexactlypendantedgesefromifisevenandforexactlyonesifisodd.Foranedgeefromthebodyofalways.Ifor,thenforevenandforodd.If,thenforoddandforeven.Wehave,whichimpliestheassertion.Ourconsiderationsconcerningwillbefinishedbyanexistencetheorem.Proposition4.Letbeagraphwithmedgesandwithoutaconnectedcomponentisomorphicto.Then.TheproofisquitesimilartotheproofofProposition1.Proposition5.Letbeagraphwithoutaconnectedcomponentisomorphicto.Letforsomeedge.Thenforeach.Theproofisstraightforward.Thispropositionimpliestwocorollaries.Corollary2.Letbeapathoflength.ThenCorollary3.Letbeacircuitoflengthm.ThenNamely,inbothcasestheuniqueSETDFistheconstantequalto1.Theorem4.Letbeastarwithedges.Ifmisodd,then.Ifmiseven,then.Proof.LetbeaSETDFsuchthat.Evidentlythereexistsatleastoneedgesuchthat.WehaveandIfmiseven,thevalue2canbeattainedbyconstructingaSETDFsuchthatforedgeseandfor-33- 华东交通大学毕业论文edges.Ifmisodd,then,accordingtoProposition4,wehave.WemayconstructaSETDFfsuchthatf(e)=1foredgeseandforedgese.Wefinishagainbyanexistencetheorem.References[1]E.Xu:Onsigneddominationnumbersofgraphs.Discr.Math.(submitted).[2]T.W.Haynes,S.T.Hedetniemi,P.J.Slater:FundamentalsofDominationinGraphs.MarcelDekker,NewYork,1998.Author’saddress:BohdanZelinka,TechnicalUniversityLiberec,Voron..ska13,46001Liberec1,CzechRepublic,e-mail:bohdan.zelinka@vslib.cz.①：摘自MATHEMATICABOHEMICA127(2002)No.1,49.55-33- 华东交通大学毕业论文B外文翻译译文部分关于树的符号边控制数①BohdanZelinka,Liberec(ReceivedApril18,2000)摘要：图的符号边控制数是随着符号控制数的变化而改变的一个变量。表示边e在图中的闭邻域，它是由边e和所有与e相邻的边组成的集合。假设函数是图的边集到集合的映射。如果对任意都有成立的话，则称为图的符号边控制函数。同时在关于图的所有符号边控制函数中，得到的最小值，称作为图的符号边控制数，记为。同理，若用开邻域替闭邻域，我们得到图的符号全控制数的定义，我们把它记为。在这篇论文中研究的对象是树。数表示的星图，路径，或者毛虫树的符号边控制数。此外还有表示一个长度为n的圈的控制数。树满足不等式条件是确定的。对于给定边数，和给定符号边控制数的树，已经证明了它的存在性定理。最后，得到了完全控制数的一些类似结果。关键字：树，符号边控制数，符号全控制数MSC2000:05C69,05C05在这里我们考虑的都是没有自环和没有重边的有限无向简单图。图的边集记为且顶点集记为，图的两条边称为邻边，如果他们是有一个共同顶点的两条不同的边。对于边的开邻域表示的是与边相邻的所有边组成的集合。它的闭邻域则为。如果我们考虑映射且当，我们记。一个映射称为关于图-33- 华东交通大学毕业论文的符号边控制函数（或全符号边控制函数），如果（或分别成立）对任意一条边都成立。同时在关于图的所有符号边控制函数（或全符号边控制函数）中，得到的最小值，分别称为图的符号边控制数（或符号边全控制数，）关于符号边控制数在文献B.Xu[1]有介绍且记为。图的符号全控制数记为。符号边控制函数简记为SEDF，全符号边控制函数简记为SETDF，的值是随边控制数的变化而改变的一个边变量[2]。另外还有一种有关图的控制数。是一个边集合映射到图的一个函数，（当的每一条边都在中时或者邻接于时，图的边集的子集称为中的边控制数）若称是图的边控制函数，当的每一条边都在中或者邻接于。在图边控制集合中最小的边集数目就称为图的边控制数，记为。接下来我们研究的和都是关于树的结论。引理1、假设图有m条边那么证明：假设是的一个SEDF，且。令表示(或)这类边的数目。我们有同时，，因此，故结论成立。引理2、若是树的3个顶点，且是的一个悬挂顶点的两个邻接顶点分别是，定义为的SEDF则有：证明：我们知道且故结论成立。引理3、若是一个星图，它含有条边，当为奇数时，，当为偶数时，.证明：在星图中所有的边都连接在一起，因此对任意一条边都成立若是的SEDF，则有，故.设表示图中-33- 华东交通大学毕业论文的边数，那么.如果为奇数时，我们可以取一个函数使得满足，因此有.如果为偶数时，也是偶数我们可以选择一个函数使得，因此.当，则的邻域子树，是由的顶点集，和的边集构成的图。若是的一条悬挂边，那么是以边的一个顶点为中心，且中心度数大于1的星图。这就得到了包含边且直径为2的最大生成子树，.相反地是以边为中心且直径为3的最大生成子树。把所有的生成子树（其中）构成的集合记为定理1、在树中存在一个的子集，满足所邻接的树的并是，则有.证明：令是中的边集，对任意一条边，则集合是边e的邻域集，且所有集合的并是.因此是的一个边控制集.因此有.令是的一个SEDF所以.由于中的树是关联，我们有如下结论.我们已知对任意一个树都成立，所以有如下推论。推论1、当满足定理1的条件时，则有.猜想：对任意一个树，我们有成立。表示长度为的路径，也就是说含有条边以及个顶点的路径。则表示长度为的圈。定理2、对于路径（），它的符号边控制数有如下结论：-33- 华东交通大学毕业论文证明：令是路径的SEDF则，取，.很明显对中任意一条边必须至少邻接两条中的边，且中的任意一条边至多只能邻接中的一条边。据引理2可知，的端点和的边之间至少含有两条中的边，同理两条中的边之间至少含有两条中的边。因此且.如果我们选择中的一个端点开始对其边标号，我们可以这样选定函数，当且仅当边的序号数能被3整除，且小于时，令.这时有，且它就是.这个数值对对模3值分开表示，则得到定理给出的形式。令一方面我们来考虑圈的情况，证明方法十分类似于定理2.定理3、对于圈，它的符号边控制数有如下结论：下面我们来考虑毛虫树.把毛虫树的所有悬挂边删除后得到的是一条路径：也就是说，得到的这条路是毛虫树的主干。毛虫树的一些个别情况包括星图和路径。另的主体顶点标记为和边（）.令（）为顶点上的悬挂边的数目。有限序列决定了毛虫树的唯一性。根据定义所知很明显有且.若k=1，则这个毛虫树就是一个星图。若，（，）则它是一条路径。-33- 华东交通大学毕业论文定理4、令为一个整数有限序列，且，，，。令表示中所含奇数的数目则就是由此序列控制的毛虫树，得知.证明：由这个定理的假设可知的主体中每个顶点至少有一条悬挂边令为（）中所含的所有边构成的边集。令为的主体中一个顶点，当e为这个顶点的一条悬挂边，则有，且，故有.我们可以这样地定义函数：当或，且为偶数时，令中条悬挂边e的函数值.当或，且为奇数时，令条悬挂边e的函数值.若，且为偶数时，令中条悬挂边e的函数值.若且为奇数时，令条悬挂边e的函数值对于的主体中的边e总有.当或，且为偶数时，则，为奇数时，则.当,且为偶数时，则为奇数时，则,所以故结论成立。我们得出了的一个存在性定理引理4一个具有条边的图,且所有子图中不含有,那么有.此证明与引理1的证明很相似。引理5、若在图中所有子图中不含有，且对某些边成立，则对所有有.这个结论是很明显的。这个引理得出了两个推论。推论2、对于长度的路径，有推论3、对于长度为m的圈，有-33- 华东交通大学毕业论文也就是说，在这两种情况下，SETDF只有一个常数值为1.定理5、图表示一个边数的星图，若是奇数，则.若是偶数，则.证明：令是图的SETDF，则.很明显至少存在一条边使得.我们有，且，若m是偶数，我们可以取条边使得组成SETDF的为，取条边使得组成SETDF的为若m为奇数，据引理4有，我们可以取条边使得组成SETDF的为，取条边使得组成SETDF的为.我们再一次得出了一个存在性定理。参考文献[1]B.Xu:Onsigneddominationnumbersofgraphs.Discr.Math.(submitted).[2]T.W.Haynes,S.T.Hedetniemi,P.J.Slater:FundamentalsofDominationinGraphs.MarcelDekker,NewYork,1998.Author’saddress:BohdanZelinka,TechnicalUniversityLiberec,Voron..ska13,46001Liberec1,CzechRepublic,e-mail:bohdan.zelinka@vslib.cz.①：摘自MATHEMATICABOHEMICA127(2002)No.1,49.55-33-'