• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Triangle-free subcubic graphs with small bipartite density

Chang, Chia-Jung 20 June 2008 (has links)
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.

Page generated in 0.0942 seconds