Structural Properties Of Sierpinski-like Graphs

The original of graph theory went back to1730s at the earliest. The hallmark event is that the Konigsberg seven bridge problem was settled by Leonhard Euler (April15,1707～September18,1783), who is a great mathe-matician from Switzerland. The publication of the paper on Konigsberg sev-en bridge problem is recognized as a milestone in graph theory of the birth. Since1950s, with the rapid development of the computer science, graph theo-ry has developed very fast. Now, graph theory becomes a backbone branch in discrete mathematics. It includes great theoretical and practical significance and is extensively applied in chemistry, informatics, network design, manage-ment science, communications engineering, computer science, bioinformatics and other fields.The hamiltonicity, coloring theory and shortest paths of graphs, which are classical problems in graph theory, have been focused on by lots of ex-perts in discrete mathematics. In this thesis, we mainly investigate The hamiltonicity, coloring theory and shortest paths of Sierpinski-like graphs, where coloring theory includes path coloring, linear coloring and2-distance coloring.Sierpiiiski-like graphs constitute an extensively studied family of graphs of fractal nature applicable in topology, mathematics of the Tower of Hanoi, computer science, and elsewhere. The Sierpinski-like graph S(n, k), S+(n, k), S++(n, k) and S[n, k] are defined as follows. For n≥1and k≥1, the vertex set of S(n, k) consists of all n-tuples of integers1,2,..., k, that is, V(S(n, k))={1,..., k}n. Two different vertices u=(u1,u2...,un) and v=(v1, v2....vn) are adjacent if and only if there exists an h G [1, n] such that(a) ut=vt for t G {1,..., h-1};(b) uh≠vh;(c) ut=vh and vt-uh for t G {h+1,..., n}.In S(n. k), the vertex of form (i,..., i), i G {1,..., k}, is called extreme vertex of S(n, k); the vertices of form (i,j,..., j) or (i,..., i, j) are called almost-extreme vertex of S(n, k). The edge that do not belong to any com-plete graph is called bridging edge of S(n, k).For n≥1and k1≥1, the graph S+(n,k) is obtained from Sierpinski graph S(n,k) by adding a new vertex w and edges joining w with k extreme vertices of S(n, k).For n=1, let S++(l,k)=Kk+1. For n≥2and k≥1, the graph S++(n,k) can be obtained from the vertex disjoint union of a copy of S(n, k) and a copy S(n-1, k) such that the extreme vertices of S(n, k) and the extreme vertices of S(n-1, k) are connected by a matching.Graphs S[n, k] are obtained from the Sierpinski graphs S(n, k) by con-tracting all bridge edges.Given a graph G, if a path in G traverses all vertices of G, then the path is called Hamiltonian path of G. Similarly, if a cycle in G passes through all vertices of G, then the cycle is called Hamiltonian cycle of G. G is Hamiltonian if G contains a Hamiltonian cycle.A t-coloring of a graph G is a mapping φ from V(G) to {1,...,t}. With respect to a given t-coloring φ, φ-1(i) is denoted by the set of all vertices of G colored i, and G[φ-1(i)] is denoted by the subgraph induced by φ-1(i) in G.If φ-1(i) is an independent set for any i∈{1,..., t}, then φ is called a proper t-coloring. The chromatic number χ(G) of a graph G is the minimum t for which G has a proper t-coloring.If every G[φ-1(i)], i∈{1,..., t}, is a linear forest, then φ is called a path t-coloring, where linear forest is a graph of which each connected component is a path. The vertex linear arboricity of a graph G, denoted by vla(G), is the minimum t for which G has a path t-coloring. In other words, the vertex linear arboricity vla(G) of a graph G is the minimum number of subsets into which the vertex set V(G) can be partitioned so that each subset induces a subgraph which is a linear forest.If every G[φ-1(i)∪φ-1(j)], i,j∈{1,..., t} with i≠j, is a linear forest, then φ is called a linear t-coloring. The linear chromatic number of a graph G, denoted by lc(G), is the minimum t for which G has a linear t-coloring.The2-distance coloring of a graph is to color the vertices of a graph such that any two vertices at distance at most two receive different colors.Given a graph G, for any two vertices u, v∈V(G), the shortest path between u and v is the path with minimum length.This thesis is concerned with some topics on hamiltonicity, colorings and shortest paths of Sierpinki-like graphs. We mainly discuss the hamiltonici-ty, path coloring, linear coloring of Sierpinki-like graphs and the2-distance coloring, shortest paths of Sierpinki graphs S(n,k). We have organized our work in four chapters.In Chapter1, first, we introduce some basic definitions and notations on theory graph; then we give the definitions and research status of Sierpinski-like graphs; at last, we list out the main results of this thesis.In Chapter2, the numbers of edge disjoint Hamiltonian paths and Hamiltonian cycles in S(n,k), S+(n,k) and S++(n, k) are completely de-termined, respectively.In Chapter3, we study the path t-coloring, linear coloring and2-distance coloring of Sierpinski-like graphs S(n, k), S+(n, k), S++(n, k) and S[n, k].In Chapter4, we investigate the shortest paths in Sierpinski graphs S(n, k). We completely determine the setSu={v∈V(S(n, k)):there exist two shortest u, v-paths in S(n, k)}, where u is any almost-extreme vertex of S(n, k).Moreover, for S(n,3), we find out (n-3)·3n+3·2n pairs of vertices of which each pair is connected by two different shortest paths, and characterize them, thus we present the sufficient condition for the number of shortest paths between two vertices to be two.