Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 12 of 12 for “"arboricity"”.

  1. On the linear vertex arboricity of graphs

    … a linear forest is defined as the linear-vertex arboricity of the graph. The linear-vertex arboricity of various classes of simple graphs are determined. In particular, the joins of various types of graphs turn out to provide nice structures that are related to their linear vertex arboricity. The …

    nus Repository record for On the linear vertex arboricity of graphs (opens in a new tab) Download file for On the linear vertex arboricity of graphs (opens in a new tab)

  2. Arboricity and transversal problems on bounded degree graphs

    In this thesis, we investigate arboricity and transversal problems on graphs in a bounded degree setting. We pay particular attention to problems involving both the maximum degree and maximum density of the graphs. The first topic is bounded degree arboricity. The arboricity of a multigraph $G$ is …

    waterloo Repository record for Arboricity and transversal problems on bounded degree graphs (opens in a new tab)

  3. Extremal problems on cycles, packing, and decomposition of graphs

    … are that every graph with fractional arboricity at most k + d/(k+d+1) has such a decomposition. When d = k +1, and also in the case where k = 1 and d ≤ 6, the d-bounded graph in the decomposition can also equired to be a forest. For d ≤ k + 1, we prove that every graph with fractional …

    uiuc Repository record for Extremal problems on cycles, packing, and decomposition of graphs (opens in a new tab)

  4. Fractional refinements of integral theorems

    … $k$ and $d$, if a graph $G$ has fractional arboricity at most $k + \frac{d}{k+d+1}$, then $G$ decomposes into $k+1$ forests, where one of the forests has maximum degree $d$. We prove a strengthening of the Nine Dragon Tree Theorem in certain cases. Let $k=1$ and $d \in \{3,4\}$. Every graph …

    waterloo Repository record for Fractional refinements of integral theorems (opens in a new tab)

  5. Thin Trees in Some Families of Graphs

    … analysis of Merker and Postle ("Bounded Diameter Arboricity", arXiv:1608.05352v1) and show that every 6-edge-connected planar graph has two edge-disjoint spanning trees 𝑇,𝑇′ such that 𝜌(𝑇),𝜌(𝑇′) ≤ 14⁄15. For 8-edge-connected planar graphs 𝐺, we present a simplified version of the techniques of …

    waterloo Repository record for Thin Trees in Some Families of Graphs (opens in a new tab)

  6. Some problems in polynomial interpolation and topological complexity

    … is closely related to the inequality in the arboricity theorem of Nash-Williams.

    uiuc Repository record for Some problems in polynomial interpolation and topological complexity (opens in a new tab)

  7. Transversal Problems In Sparse Graphs

    … for minimum weight dominating set in graphs of arboricity $a$. At the end, we propose five open problems for future research.

    waterloo Repository record for Transversal Problems In Sparse Graphs (opens in a new tab)

  8. Massively parallel algorithms for sparse graphs

    … uniformly sparse graphs, technically known as lowarboricity graphs. These graph families form the setting for most known lower bounds in MPC, and designing memory-optimal algorithms for them is notoriously difficult. Algorithm complexity is measured in communication rounds and is typically …

    aalto Repository record for Massively parallel algorithms for sparse graphs (opens in a new tab)

  9. Extremal problems on variations of graph colorings

    … a question by Raspaud and Wang regarding vertex arboricity for toroidal graphs. We also improve results regarding improper coloring of planar graphs, responding to a question of Montassier and Ochem.

    uiuc Repository record for Extremal problems on variations of graph colorings (opens in a new tab)

  10. Putting the pieces together: from graph decompositions to Ramsey theory

    … celebrated problem in this area is the Linear Arboricity Conjecture, which states that the edges of every graph with maximum degree $\Delta$ can be decomposed into at most $\lceil (\Delta+1)/2\rceil$ linear forests, where a linear forest is a collection of vertex-disjoint paths. Although this …

    oxford Repository record for Putting the pieces together: from graph decompositions to Ramsey theory (opens in a new tab)

  11. Approximating Properties of Data Streams

    … weight of a maximum weighted matching in bounded-arboricity graphs and in particular, a (48 + )-approximation estimator for the weight of a maximum weighted matching in planar graphs.

    purdue-thes Repository record for Approximating Properties of Data Streams (opens in a new tab)

  12. Irreversible k-threshold conversion processes on graphs

    Given a graph G and an initial colouring of its vertices with two colours, say black and white, an irreversible k-threshold conversion process on G is an iterative process in which a white vertex becomes permanently coloured black at time t if at least k of its neighbours are coloured black at time …

    uvic Repository record for Irreversible k-threshold conversion processes on graphs (opens in a new tab)