浅议一类优美图

《浅议一类优美图》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文一类优美图AClassofGracefulGraphs作者姓名：学科、专业：学号：指导教师：完成日期：奎董至让篡扭厘旦燕丕20309260扬丞生熬援2Q笾生!!目大连理工大学DalianUniversityofTechnology可825384大连理工大学硕士学位论文摘要优美图是图论中极有趣的研究课题之一．它的研究始于1963年G．Ringel提出的一个猜想和1966年A．Rosa的一篇论文．1972年，S．W．Golomb明确给出了优美图的定义．对一个给定的简单图G=(Z(63坝G))，1坎G)闻I耳⑦1分别是图G的顶点数和边数，令陋(G)1=g

2、，如果存在一个一一映射yV(63一{0，1⋯2，．，q}，使得对所有边(甜，v)∈耳q，由，(“，v)=扳u)-gv)l所导出的函数／：顾G)--+{1⋯2。g)是一个一一对应，则称厂是图G的一个优美标号，图G被称为优美图．本文研究月为奇数时c!”图的优美性．令c?’图为有一个公共顶点v的r个长度为以的回路所组成的图．用“，v：，vi，⋯，K一．表示qo图第i(IZi9)个长度为n的回路上的顶点，对所有的i，有“=y．A．Rosa给出了具有q条边的欧拉图为优美图的必要条件为萨O，3(rood4)，a‘’图是欧拉图，因此a‘’图是优美图的必要条件为n芦o，3(m

3、od4)．1979年，K．M．Koh等人猜想：当且仅当nt=-0，3(mod4)时，do图是优美图．已经证明了当n=3，5，4p，妒心她1)时该猜想成立．本文设计了计算机辅助下求解畔’图优美标号的算法，并利用q。图的对称性，对顶点进行合理的分组，采用顶点的分布规律制约边的分布规律的策略，给出了搜索q”图的优美标号的有效的分支限界条件，给出了当n=7，9，11,13时，d”图的一种优美标号，并证明了当n=7，9，11，13，K．M．Koh等人的猜想成立．关键词：优美图；顶点标号；边标号大连理工大学硕士学位论文AClassofGracefulGraphsAbstt

4、'actThegracefullabelingisoneoftheimportantbranchesofGraphTheory．OnecantraceitsSOUrCefromaconjecturegivenbyG．Ringelin1963and19．paperwrittenbyA．Rosain1966．In1972．S．W．Golombgivesthedefinitionaboutgrace彻graph．LetG=(㈣，耳⑩beasimplegraphwithfK63【verticesandIE(⑦Iedges．LetIE(G)I=q，ifthereexis

5、ts，坎回_÷{O，1⋯2．．，g}beallinjeetivemapping，anddefineaninducedfunction厂：耳回一{l，2⋯，订bysettingf(u，力一l必u)-J(v)lforall(“，v)∈耳G)．Ifymaps坝⑦Olqtto{1,2，，，g}，thenfissaidtobeagracefullabelingofG，thegraphGissaidtobeagracefulgraph．LetCtdenotethecyclewithHvertices，andC：ldenotethegraphsconsistingoftco

6、piesofGwithfl,vertexinC01TIITIOn．Thispaperdosomeresearchonthegracefullabelingsofd”forHisodd．Let“，《，V；，⋯，《一1betheverticesofi-th(1<_i茎4)cycleGoflengthn，％。Vforalli，AnecessaryconditionforanEulergraphwithqedgestobegracefulisthatq-=0，3(rood4)．SincethegraphqoisEulergraph，ifg”isgracefulthen

7、删Eo，3(rood4)．In1979，K．M．Koheta1．conjecturedthatq“isgracefulifandonlyifnt==0，3(mod4)．Theconjecturehasbeenshowntrueforrr23，5，印，4p+2(}硅1)．Thepapergivesanalgorithmtosearchthegracefullabelingsofgraphq“bycomputer．UsingthesymmetricofgraphC!j，thispapergivesalleffectiveboundstrategybydividin

8、gverticesintodiffer