论文部分内容阅读
图的重构猜想由Ulam和Kelly于1942年提出,它是图论中至今未被解决的难题之一.重构猜想是指每个至少含有三个顶点的图都能唯一地被它的主子图集所确定.对于图G,称删去图的一个顶点v以及与该顶点相关联的边后得到的子图为主子图.度结合主子图是指一个有序对(G-v,d(v)),由一个主子图G-v以及被删去的点v的度数组成.度结合重构数的概念是指重构图G所需的度结合主子图的最少个数,记为drn(G).一致度结合重构数是指最小的整数k,使得任意k个度结合主子图集都能够重构图G,记为adrn(G).对于图G,称删去图的一条边e后得到的子图为边主子图.边重构猜想是指每个至少含有四条边的图都能唯一地被它的边主子图集所确定.度结合边主子图是指一个有序对(G-e,d(e)),由一个边主子图G-e以及被删去的边e的度数组成.度结合边重构数是指重构图G所需的度结合边主子图的最少个数,记作dern(G).一致度结合边重构数是指最小的整数k,使得任意k个度结合边主子图集都能够重构图G,记为adern(G).本文主要研究了冠图P_n(?)C_m的基本结构性质,确定了冠图P_n(?)C_m的度结合重构数,一致度结合重构数,度结合边重构数,一致度结合边重构数.本论文分为四章,第一章介绍了本论文所涉及的相关概念与基本知识,并介绍了图的度结合重构数的研究现状.第二章确定了冠图P_n(?)C_m的两种度结合重构数.第三章确定了冠图P_n(?)C_m的两种度结合边重构数.第四章总结了本论文的结果以及所采用的证明方法,提出了几个可进一步讨论的问题.