关于阿基米德铺砌图相关性质的研究

发布时间：2018-02-10 06:12

本文关键词： 阿基米德铺砌图填装着色填装着色数定位配对控制集 Gallai性质　出处：《河北师范大学》2016年博士论文　论文类型：学位论文

【摘要】：阿基米德铺砌是指每个铺砌元都是正多边形,且每个铺砌顶点的顶点特征都相同的边对边铺砌,其有且仅有11种,按照顶点特征分别记为:(44),(36),(63),(34.6),(3.6.3.6),(33.42),(32.4.3.4),(3.122),(4.82),(3.4.6.4)和(4.6.12).显然,如果分别取铺砌(44),(36),(63)的顶点为顶点,铺砌边为边则得到众所周知的格图,三角形格图以及正六边形格图,其诸多性质已经得到了广泛的研究.本文主要研究其余8种阿基米德铺砌图的相关性质,包括填装着色问题,定位配对控制集问题,以及有限子图的Gallai性质.论文第二章研究了阿基米德铺砌图的填装着色数,证明了铺砌图(34.6),(33.42),(3.6.3.6)的填装着色数为无穷,铺砌图(4.82)和(4.6.12)的填装着色数均为7,铺砌图(4.6.12)的填装着色数在7与11之间.论文第三章研究了阿基米德铺砌图的最优定位配对控制集问题,刻画了铺砌图(4.82)和(3.6.3.6)具有最小密度的定位配对控制集,并给出了(4.6.12),(3.122),(33.42),(32.4.3.4)和(34.6)等5种阿基米德铺砌图的最优定位配对控制集密度的上下界.论文第四章研究了阿基米德铺砌图有限子图的Gallai性质,通过具体构造的方法证明了在阿基米德铺砌图(34.6),(33.42),(32.4.3.4),(3.6.3.6),(3.4.6.4),(4.82),(4.6.12),(3.122)中分别存在62个顶点,46个顶点,48个顶点,92个顶点,100个顶点,166个顶点,207个顶点,191个顶点的连通子图满足Gallai性质;分别存在152个顶点,110个顶点,110个顶点,278个顶点,224个顶点,511个顶点,541个顶点,499个顶点的2-连通子图满足Gallai性质.
[Abstract]:Archimedes paving means that each paving element is a regular polygon, and that the vertices of each paving vertex have the same vertex characteristics. There are and only 11 kinds of paving, which are respectively counted as:: 44 / 3 / 36 / 3 / 3 / 3 / 34 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 2 and 3.82 / 4 / 4, respectively, respectively, according to the characteristics of the vertex, which are recorded as 3.422.36 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3 / 3. If we take the vertices of the paver 44 and 36, respectively as the vertices, and the edges of the paving edges as the vertices, we can get the well-known lattice graphs, triangular lattice graphs and regular hexagonal lattice graphs. In this paper, the related properties of the other eight Archimedes paving diagrams are studied, including the filling coloring problem, the location-pairing control set problem, and so on. In chapter 2, we study the filling coloring number of Archimedes paving diagram, and prove that the filling coloring number of Archimedes paving diagram is infinite. The filling coloring number of paving drawing 4.82) and that of paving drawing 4.6.12) are both 7 and 4.6.12) respectively. In chapter 3, the optimal location pairing control set of Archimedes paving is studied, and the coloring number of packing coloring is between 7 and 11. The location-pairing control sets with minimum density are described for paving drawings 4.82) and 3.6.3.6). The upper and lower bounds of optimal location control set density for five Archimedes paving maps are given. Chapter 4th studies the Gallai properties of Archimedean paving maps with finite subgraphs, and gives the upper and lower bounds of the optimal location pairing control set density for five Archimedes paving maps, such as 3.42 and 34.6). In chapter 4th, we study the Gallai properties of the finite subgraphs of Archimedean paving maps, and give the upper and lower bounds of the optimal location pairing control set density for the five Archimedes paving maps. It is proved by concrete construction that there are 62 vertices, 46 vertices, 48 vertices, 92 vertices, 100 vertices, 166 vertices, 207 vertices and 191 vertices in Archimedean paving graph with 62 vertices, 46 vertices, 48 vertices, 92 vertices, 100 vertices, 166 vertices, 207 vertices and 191 vertices respectively. There are 152 vertices, 110 vertices, 110 vertices with 278 vertices, 224 vertices with 511 vertices and 541 vertices with 499 vertices. The 2-connected subgraphs satisfy the Gallai property.
【学位授予单位】：河北师范大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】