关于图pebbling数的若干问题研究-应用数学专业论文.docx

中文摘疆攘鬟 中文摘疆 攘鬟 图的Pebbling数问题是j黩年来图论上的热点问题。农过去的二十年里，它深 深建设粤|着数学窳们的眼球。用它可以解决～些在数论上不易解决的潮题，著且 它与数论有着密切的联系。图G静pebbling数，(G)是最小的整数m，往得不论m 个pebbles如何放置在G的顶点上，总可以通过一系列的pebbling移幼把1个 pebble移裂饪塞～令顶点土，其中豹pebbling移动是扶一令】耍煮然移走嚣个 pebbles而把其中盼一个移到鸯冀褶邻的一个顶点上。C_mflmm猜想对予任意的连通 图G和日有f(Gx哪≤，(G)，(盯)。 本文锌对霆戆pebbling数邂嚣了骚究，会绥了图pebbling瓣磅交鹜豢；著麓 单介绍了图pebbling数的发展及现状，介绍了图的2-pebbling性质。在前人研究的 基础上，本文重点研究了刺图和中间图的pebbling数，研究的是完全图的刺图和 星黧熬孛麓图豹pebbling数：求窭了宅嚣】务蠡懿pebbling数；莠显骏谖了它襄都 满足2-pebbling性质；最后，证明了对于一个完全图的刺圈或一个星图的中间图G 和～个满足2-pebbling性质的网凹的乘积来说，Graham猜想成立；并熙求出了完 全嚣戆襄l囤黍获瓣pebbling数魏赛纛星图豹◇蓠蚕乘积豹pebbling数魏赛。 关键词：Pebbllng；最优pebbling数；剌图；中间图：笛卡尔积：合成网；字典式 获 英文摘要Reserch 英文摘要 Reserch on the Pebbling Number of Graphs Abstract In recent years,the graph pebbling has become a hot topic in the graph theory． W。i髓n the past twenty years．it has been attracting the mathematicians deeply．It is closely related to number theory and it can deal with some unresolved problems on number theory．The pebbling number of a graphG，，(G)，is the least聊such that,no matter how／7／pebbles are placed orl the vertices OfG，one pebble can be moved{。 any vertex by a sequence of pebbling moves，each move taking two pebbles off one vertex and placing one on an adjacant vertex．Graham conjectured that for all connected graphsGandH，f◇x嚣)s，≤G)f≤鞋)。 This paper studies the pebbling of graphs．T11e research background of the graph pebbling is introduced；the development of the pebbling number of the graph and the 2-pebbling property of graph are presented。Based on the previous studies,this paper mainly focuses on the pebbling number of thom graphs and middle graphs．Thc main investigation is the pebbling number of the thorn graph of complete and the middle graph ofstar．Inthispaper,we computerthepebblingnumberofthesegraphsand show that Graham’s conjecture holds whenG is a thorn graph of complete or a middle graph of star and H satifles 2-pebbling property．At last,we also obtain the bound on the pebbling number of a Cartesian product of thorn graphs