The Connectedness Of Cubic Graphs With Two Orbits And Maximally Irregular Graphs

In recent years, with the rapid development of networks, the network performance comes into focus. The topology of network is wary important to in?uence the network performance. When designing the underlying toplogy of a multiprocessor network. What we care about most are the reliability of the network, that is, the ability of the network of function even when some vertices and/or edge fail. The underlying topology of a network is often modeled as a graph. Therfore, some classical notions of graph theory, such as the connectivity κ(G) and edge-connectivity λ(G), are utilized to measure the reliabity of network.Let G be a connected graph with two orbits, V1 and V2be its vertex orbits under the action of Aut(G) on V(G). Let G1= G[V1] and G2= G[V2], which are called the vertex transitive parts of G, then we say that G is an 2-vertex-orbit graph or graph with two orbits. Let G be a connected graph, the irregularity index t(G) of G is de?ned as the number of distinct terms in the degree sequence of G. We say that G is maximally irregular if t(G) = ?(G)- δ(G) + 1.In this paper, we mainly study the connectivity of cubic graphs with two orbits and the size of maximally irregular graphs. In chapter 1, we introduce the backgroud of our study, some notations and recall known results on connectivity of graphs and question about maximally irregular graphs. Chapter 2, we study the connectivity of cubic graphs with two orbits, we classify the connected cubic graph with two orbits and give the su?cient condition for a graph G to be κ-optimal. Chapter 3, we study the size of maximally irregular graphs, we give a tight upper bound and low bound on the size of maximally irregular graphs.