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 [18] 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.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0620108-164144 |
| Date | 20 June 2008 |
| Creators | Chang, Chia-Jung |
| Contributors | Xuding Zhu, Tsai-Lien Wong, Li-Da Tong, D. J. Guan |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0620108-164144 |
| Rights | unrestricted, Copyright information available at source archive |
Page generated in 0.0064 seconds