| An Archimedean tiling is a plane edge-to-edge tiling in which all tiles are regular polygons, and all vertices are of the same type. There exist precisely eleven such tilings,which are denoted by(44),(36),(63),(34.6),(3.6.3.6),(33.42),(32.4.3.4),(3.122),(4.82),(3.4.6.4) and(4.6.12) respectively. Obviously, in each of the tilings(44),(36) and(63), if we take the vertices and edges of the tiling as the vertices and edges of a graph, then we obtain a lattice graph, a triangular lattice graph and a regular hexagonal lattice graph respectively, whose properties have been widely examined.In this thesis we study some properties of the other 8 Archimedean tiling graphs,including the packing chromatic number, the locating-paired-dominating sets, and the Gallai’s property of their finite subgraphs.In Chapter 2 we discuss the packing chromatic numbers of Archimedean tiling graphs,and show that the tiling graphs of(34.6),(33.42) and(3.6.3.6) have infinite packing chromatic numbers; the packing chromatic numbers of the tiling graphs(4.82) and(4.6.12)are both equal to 7, and the packing chromatic number of(4.6.12) tiling graph lies between7 and 11.In Chapter 3 we investigate the optimal LPDS in Archimedean tiling graphs, and give complete characterizations of locating-paired-dominating sets with minimal density for the tiling graphs(4.8.8) and(3.6.3.6). Furthermore, we provide ranges of the density of the optimal for other 5 Archimedean tiling graphs(4.6.12),(3.122),(33.42),(32.4.3.4) and(34.6).In Chapter 4 we study Gallai’s property of finite subgraphs of Archimedean tiling graphs. Based on concrete constructions, we prove that there exist some connected subgraphs of(34.6),(33.42,(32.4.3.4),(3.6.3.6),(3.4.6.4),(4.82),(4.6.12),(3.122) tiling graphs, with 62, 46, 48, 92, 100, 166, 207, 191 vertices respectively, satisfying Gallai’s property; and 2-connected subgraphs with 152, 110, 110, 278, 224, 511, 541, 499 vertices respectively satisfying Gallai’s property. |
