笛卡尔乘积图的配对控制数
发布时间：2018-03-27 21:36
本文选题：笛卡尔乘积图 切入点：控制数 出处：《浙江师范大学》2015年硕士论文
【摘要】：设图G=(V,E)是一个没有孤立点的无向简单图.如果V的一个非空子集D满足V\D中的每个顶点都有一个邻点在D中,则称D是图G的一个控制集.进一步,如果D是图G的一个控制集并且由D导出的子图G[D]中有一个完美匹配,则称D是图G的一个配对控制集.一个图G的配对控制数,即图G的最小的配对控制集的大小,记为γp(G).配对控制数最初是由Haynes和Slater提出的,同时他们证明了对于一般图,确定其配对控制数是NP-完全的.本文确定了一些特殊图的配对控制数,主要内容分为四章.第一章介绍了配对控制数的背景以及本论文所涉及的有关定义,并对路和圈的笛卡尔乘积的配对控制数的研究现状做了一个综述.第二章根据圈和圈的笛卡尔乘积的结构,利用反证法,确定了n圈和5圈的笛卡尔乘积的笛卡尔乘积的配对控制数.第三章给出n圈和m(m=2,3)路和n路和m(m=3,4,5)圈的配对控制数.第四章对本文进行了总结并给出笛卡尔乘积图配对控制数的一些可研究问题.
[Abstract]:璁惧浘G=(V,E)鏄竴涓病鏈夊绔嬬偣鐨勬棤鍚戠畝鍗曞浘.濡傛灉V鐨勪竴涓潪绌哄瓙闆咲婊¤冻VD涓殑姣忎釜椤剁偣閮芥湁涓，
本文编号：1673303
本文链接：https://www.wllwen.com/kejilunwen/yysx/1673303.html
