字典序积图的厚度的研究

作     者：KEITA BREHIMA 

作者单位：湖南大学 

学位级别：硕士

导师姓名：陈仪朝

授予年度：2018年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：路图 完全图 字典序积 厚度 

摘      要：在图论中,图G和H的字典序积(或合成图)G ·H是一个图,使得:G·H的顶点集是笛卡儿积V(G)×V(H)G· H中任何两个顶点(u,v)和(x,y)相邻当且仅当u与x在G中是相邻的或u = x且v与y在H中是相邻的。图G的厚度t(G)是将G分解成不交的平面子图的并的最少平面子图数。确定任意图的厚度是NP困难的,因此很难获得一个图的精确的厚度值。在本文中,我们将研究两条不同路图的字典序积的厚度以及路图和完全图的字典序积的厚度。第一章主要介绍图的厚度的起源还有本文所需的一些基本知识。第二章主要通过引入平面图及研究平面性的一些已知的结果。第三章主要介绍两类特定的图:图运算将应用的路图和完全图。第四章主要介绍字典序积的基本结构,展示其他图乘积的一些特殊性。在第五章主要研究两条路图的字典序积的厚度以及路图和完全图的字典序积的厚度。