Connectedness And Domination Of Several Kinds Of Graphs

Within the last thirty years, with the rapid development of such areas as com-puter science, large-scale network technology, electrical and computer engineering, many theoretical problems, e.g. the reliability and dominance of network come into focus. The reliability of the network is the ability of the network to function even when some vertices and/or edges fail. The underlying topology of a network is often modeled as a graph or a digraph, and some classical notions of graph theory, such as the connectivity and the edge(arc)-connectivity are used to measure the reliability of networks. The domination set of a graph can be used to study the dominance of the corresponding network. For further study, many variations have been in-troduced, which are known as higher connectedness and conditional domination, such as super connectivity (super-edge connectivity), restricted edge connectivity (restricted arc connectivity), restrained domination set, total domination set, total restrained domination set etc. In the design of large-scale network, lots of graphs with recursive structure, such as Cartesian-product graphs, Hierarchical-product graphs, line graphs, jump graphs come into being. In this paper, we mainly study the connectedness of several kinds of graphs and digraphs, and determine the re-strained domination number and total domination number of some special kinds of Cartesian-product graphs.In chapter 1, we introduce the backgrounds of the connectedness and domina-tion of graphs and some related notations, and give definitions of line graphs, jump graphs, Cartesian-product graphs,Hierarchical-product graphs, dominating sets, total dominating sets and total restrained dominating sets etc. We survey results on all kinds of connectivity and dominating sets of graphs. In chapter 2, we first study the connectivity, edge connectivity, super-edge connectivity of jump graphs. Then, we determine the connectivity of generalized Hierarchical-product of two graphs. Finally, we give a sufficient condition for bipartite graph to be A'-optimal. In chapter 3, we first study the restricted arc connectivity of Cartesian-product of two digraphs. Then, we study the A'-optimal of bipartite digraphs. Finally, we char-acterize the arc atoms of 3-regular strongly connected digraph with two orbits and ?(D)< 3. Further, we determine the arc-connectivity of it. In chapter 4, we study the domination of graphs. We characterize the graphs with?tr(G)= n or n - 2. And determine the total domination number and restrained domination number of some Cartesian-product graphs.