 ### Title page for etd-0620108-164144

URN etd-0620108-164144 Chia-Jung Chang m952040009@student.nsysu.edu.tw This thesis had been viewed 5577 times. Download 1164 times. Applied Mathematics 2007 2 Master English Triangle-free subcubic graphs with small bipartite density 2008-05-23 39 planar graph triangle-free subcubic bipartite density bipartite ratio Suppose G is a graph with n vertices and m edges. Let n′ be the maximum number of vertices in an induced bipartite subgraph of G and let m′ be the maximum number of edges in a spanning bipartite subgraph of G. Then b(G) = m′/m is called the bipartite density of G, and b∗(G) = n′/n is called the bipartite ratio of G. It is proved in  that if G is a 2-connected triangle-free subcubic graph, then apart from seven exceptional graphs, we have b(G) ≥ 17/21. If G is a 2-connected triangle-free subcubic graph, then b∗(G) ≥ 5/7 provided that G is not the Petersen graph and not the dodecahedron. These two results are consequences of a more technical result which is proved by induction: If G is a 2-connected triangle-free subcubic graph with minimum degree 2, then G has an induced bipartite subgraph H with |V (H)| ≥ (5n3 + 6n2 + ǫ(G))/7, where ni = ni(G) are the number of degree i vertices of G, and ǫ(G) ∈ {−2,−1, 0, 1}. To determine ǫ(G), four classes of graphs G1, G2, G3 and F-cycles are onstructed.For G ∈ Gi, we have ǫ(G) = −3 + i and for an F-cycle G, we have ǫ(G) = 0. Otherwise, ǫ(G) = 1. To construct these graph classes, eleven graph operations are used. This thesis studies the structural property of graphs in G1, G2, G3. First of all, a computer algorithm is used to generate all the graphs in Gi for i = 1, 2, 3. Let P be the set of 2-edge connected subcubic triangle-free planar graphs with minimum degree 2. Let G′1 be the set of graphs in P with all faces of degree 5,G′2 the set of graphs in P with all faces of degree 5 except that one face has degree 7, and G′3 the set of graphs in P with all faces of degree 5 except that either two faces are of degree 7 or one face is of degree 9. By checking the graphs generated by the computer algorithm, it is easy to see that Gi ⊆ G′i for i = 1, 2, 3. The main results of this thesis are that for i = 1, 2, Gi = G′i and G′3 = G3 ∪R, where R is a set of nine F-cycles. D. J. Guan - chair Tsai-Lien Wong - co-chair Li-Da Tong - co-chair Xuding Zhu - advisor indicate access worldwide 2008-06-20

Browse | Search All Available ETDs