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"”.
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
Some problems in polynomial interpolation and topological complexity
… is closely related to the inequality in the arboricity theorem of Nash-Williams.
-
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.
-
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 …
-
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.
-
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 …
-
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.
-
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 …