Factors And Graphic Parameters | | Posted on:2011-08-21 | Degree:Doctor | Type:Dissertation | | Country:China | Candidate:H X Liu | Full Text:PDF | | GTID:1100360305450907 | Subject:Operational Research and Cybernetics | | Abstract/Summary: |  PDF Full Text Request | | Since 1960s, as a young branch of mathematics, the graph theory has expe-rienced the explosion growth. It has extensive applications in physics, chemistry, biology, network theory, information science, computer science and other fields. As a sub field in combinatorial mathematics, the graph theory has attracted much attention from all perspectives.We focus on the factor theory of graphs. Factor theory is one of the funda-mental areas in graph theory. Factors have many applications in various areas, e.g., the file transfer problems on computer networks, scheduling problems and so on, which are related to the factors, factorizations and orthogonal factorizations of graphs [1,11,67]. In this thesis we fous on the relationship between graphic parameters and factors, fractional factors, critical graphs and connected factors of graphs.The graphs considered in this paper will be finite simple graphs. Let G be a graph with vertex set V(G) and edge set E(G). For x∈V(G), we denote by dG(x) the degree of x in G and by NG(x) the set of vertices adjacent to x in G. The minimum degree of G is denoted byδ(G). For any subset S C V(G), we denote by NG(S) the union of NG(x) for every x∈S, and by G[S] the subgraph of G induced by S, by G-S the subgraph obtained from G by deleting the vertices in S together with the edges incident to the vertices in S. If S, T(?)V(G), then we write eG(S,T) for the number of edges in G joining a vertex in S to a vertex in T. A vertex cut of a connected graph G is a subset S of V(G) such that G-S is disconnected. A k-vertex cut is a vertex cut of k elements. The connectivity k(G) of G is the minimum k for which G has k-vertex cut. G is said to be k-connected ifκ(G)≥k. An edge cut of G is a subset of E(G) of the form [S, V(G)\S], where S is a nonempty subset of V(G). A k-edge cut is an edge cut of k elements. The edge connectivityλ(G) of G is the minimum k for which G has a k-edge cut. G is said to be k-edge-connected ifλ(G)≥k.Let g(x) and f(x) be two nonnegative integer-valued functions defined on V(G) with g(x)≤f(x) for any x∈V(G). Then a spanning subgraph F of G is called a (g,f)-factor if g(x)≤dF(x)≤f(x) holds for any x∈V(G). If g(x)= f(x) for all x∈V(G), then a (g,f)-factor is called an f-factor. Let a and b be two integers such that 0≤a≤b. If g(x)≡a and f(x)= b for all x∈V(G), then a (g,f)-factor is called an [a,b]-factor. An [a,b]-factor is called a k-factor if a= b= k, which is a regular factor. Especially, when g(x)= f(x)= 1 for every x∈V(G), a (g,f)-factor is called a 1-factor, i.e., a perfect matching.The first study of factors was due to Danish mathematician Petersen (1891), who proved that every graph of even degrees can be decomposed into the union of edge-disjoint 2-factors. He also showed that every 2-connected cubic graph has a 1-factor. These two results can be viewed as a forerunner of modern graph factor theory. For matchings in bipartite graphs, Konig (1931) and Hall (1935) obtained the so-called Konig-Hall Theorem (sometimes, it is known as Hall's Theorem). In 1947, Tutte[115] gave a characterization (i.e, so-called Tutte's 1-Factor Theorem) for the existence of perfect matchings in arbitrary graphs and it has become a cornerstone of factor theory. Till now, this elegant theorem is still one of the most fundamental results in factor theory. Subsequently, Tutte[116] (1952) extended the techniques in the proof of 1-Factor Theorem to obtain a sufficient and necessary condition for a graph to have an f-factor. The most general degree-constrained factors, (g,f)-factors, were studied by Lovasz[86] (1970). He gave necessary and sufficient conditions for a graph to have a (g,f)-factor. This theorem generalized the criteria of all other factors, such as 1-factors, k-factors,f-factors and [a, b]-factors. Since then numerous results on factor theory sprung forth.A graph G is said to be (g,f, n)-cr.itical if G-N has a (g,f)-factor for each N(?)V(G) with|N|=n.If g(x)= a and f(x)= b for all x∈V(G), then a(g,f, n)-critical graph is an (a,b, n)-critical graph. That is, a graph G is (a, b, n)-critical if after deleting any n vertices of G the remaining graph of G has an [a,b]-factor. If a= b= k, then an (a, b, n)-critical graph is called a (k, n)-critical graph. If k= 1, then a (k, n)-critical graph is simply called an n-critical graph.Factor-criticality can be viewed as extensions of factor theory. Plummer [101] and Lovasz [85] studied the properties of 2-critical graphs. Yu [130] gave the characterization of n-critical graphs. Liu and Yu [76] studied the characterization of (k, n)-critical graphs. A necessary and sufficient condition for a graph to be (a, b, n)-critical with a1 = (?) . Ifbind(G)≥λ1 andδ(G)≥1 +(?), then G is an (a, b, n)-critical graph.We extend Theorem 3.1.4 to (g, f, n)-critical graphs.Theorem 3.1.5. Let G be a graph of order p, and let a,b and n be nonnegative integers such that 1≤a < b and p≥(?). Let g(x) and f(x) be two nonneg-ative integer-valued functions defined on V(G) such that a≤g(x) < f(x)≤b for any x∈V(G). Putλ2 =(?) If bind(G)≥λ2 andδ(G)≥1 +(?), then G is a (g, f, n)-critical graph.Theorem 3.2.3. Let G be a graph of order p, and a, b and n be nonnegative inte-gers such that 2≤a2.Theorem 4.2.5. Let G be a graph, a, b and n be nonnegative integers such that a≤b, and g(x) and f(x) be two nonnegative integer-valued functions defined on V(G) such that a≤g(x)≤f(x)≤b for every x∈V(G). Ifδ(G)≥b, and stability number a(G)≤(?), then G is fractional (g,f,n)-critical. In Chapter 5, we deal with connected factors in graphs. The problem of whether a graph has a connected factor is NP-complete.It is closely related to hamiltonian problem since a connected 2-factor is just a Hamiltonian cycle. Here some sufficient conditions related to neighborhood union and neighbor set for graphs to have connected (g,f)-factors and Hamilton (g, f)-factors are given. Our results are extensions of some known resits.Theorem 5.1.4. Let k≥3 be an integer, and G a 2-connected graph of order n with n>(?), andδ(G)≥k. If holds for any two nonadjacent vertices u and v of V(G), then G has a Hamiltonian [k, k +1]-factor.Theorem 5.2.4. Let G be a graph of order n, and let a, b and n be nonnegative integers such that 2≤a≤b and n≥(?).Let g(x) and f(x) be two nonnegative integer-valued functions defined on V(G) such that a≤g(x) < f(x)≤b for any x∈V(G). Letλ'=(?). Suppose for any subset X(?)V(G), we have Then G has a Hamilton (g, f)-factor.
| | Keywords/Search Tags: | graph, factor, fractional factor, binding number, minimum degree, neighborhood union, neighbor set, critical graph, connected factor | | PDF Full Text Request | Related items |
| |
|
