Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSpanning trees in dense directed graphs
200
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In 2001, Komlos, Sarkozy and Szemeredi proved that, for each $alpha>0$, there is some $c>0$ and $n_0$ such that, if $ngeq n_0$, then every $n$-vertex graph with minimum degree at least $(1/2+alpha)n$ contains a copy of every $n$-vertex tree with maximum degree at most $cn/log n$. We prove the corresponding result for directed graphs. That is, for each $alpha>0$, there is some $c>0$ and $n_0$ such that, if $ngeq n_0$, then every $n$-vertex directed graph with minimum semi-degree at least $(1/2+alpha)n$ contains a copy of every $n$-vertex oriented tree whose underlying maximum degree is at most $cn/log n$. As with Komlos, Sarkozy and Szemeredis theorem, this is tight up to the value of $c$. Our result improves a recent result of Mycroft and Naia, which requires the oriented trees to have underlying maximum degree at most $Delta$, for any constant $Delta$ and sufficiently large $n$. In contrast to the previous work on spanning trees in dense directed or undirected graphs, our methods do not use Szemeredis regularity lemma.
rate research
Read More
We show that, in almost every $n$-vertex random directed graph process, a copy of every possible $n$-vertex oriented cycle will appear strictly before a directed Hamilton cycle does, except of course for the directed cycle itself. Furthermore, given an arbitrary $n$-vertex oriented cycle, we determine the sharp threshold for its appearance in the binomial random directed graph. These results confirm, in a strong form, a conjecture of Ferber and Long.
A rainbow spanning tree in an edge-colored graph is a spanning tree in which each edge is a different color. Carraher, Hartke, and Horn showed that for $n$ and $C$ large enough, if $G$ is an edge-colored copy of $K_n$ in which each color class has size at most $n/2$, then $G$ has at least $lfloor n/(Clog n)rfloor$ edge-disjoint rainbow spanning trees. Here we strengthen this result by showing that if $G$ is any edge-colored graph with $n$ vertices in which each color appears on at most $deltacdotlambda_1/2$ edges, where $deltageq Clog n$ for $n$ and $C$ sufficiently large and $lambda_1$ is the second-smallest eigenvalue of the normalized Laplacian matrix of $G$, then $G$ contains at least $leftlfloorfrac{deltacdotlambda_1}{Clog n}rightrfloor$ edge-disjoint rainbow spanning trees.
A spanning tree of an edge-colored graph is rainbow provided that each of its edges receives a distinct color. In this paper we consider the natural extremal problem of maximizing and minimizing the number of rainbow spanning trees in a graph $G$. Such a question clearly needs restrictions on the colorings to be meaningful. For edge-colorings using $n-1$ colors and without rainbow cycles, known in the literature as JL-colorings, there turns out to be a particularly nice way of counting the rainbow spanning trees and we solve this problem completely for JL-colored complete graphs $K_n$ and complete bipartite graphs $K_{n,m}$. In both cases, we find tight upper and lower bounds; the lower bound for $K_n$, in particular, proves to have an unexpectedly chaotic and interesting behavior. We further investigate this question for JL-colorings of general graphs and prove several results including characterizing graphs which have JL-colorings achieving the lowest possible number of rainbow spanning trees. We establish other results for general $n-1$ colorings, including providing an analogue of Kirchoffs matrix tree theorem which yields a way of counting rainbow spanning trees in a general graph $G$.
Networks with a high degree of symmetry are useful models for parallel processor networks. In earlier papers, we defined several global communication tasks (universal exchange, universal broadcast, universal summation) that can be critical tasks when complex algorithms are mapped to parallel machines. We showed that utilizing the symmetry can make network optimization a tractable problem. In particular, we showed that Cayley graphs have the desirable property that certain routing schemes starting from a single node can be transferred to all nodes in a way that does not introduce conflicts. In this paper, we define the concept of spanning factorizations and show that this property can also be used to transfer routing schemes from a single node to all other nodes. We show that all Cayley graphs and many (perhaps all) vertex transitive graphs have spanning factorizations.
The {sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we obtain two combinatorial results on the number of leaves in out-branchings. We show that - every strongly connected $n$-vertex digraph $D$ with minimum in-degree at least 3 has an out-branching with at least $(n/4)^{1/3}-1$ leaves; - if a strongly connected digraph $D$ does not contain an out-branching with $k$ leaves, then the pathwidth of its underlying graph UG($D$) is $O(klog k)$. Moreover, if the digraph is acyclic, the pathwidth is at most $4k$. The last result implies that it can be decided in time $2^{O(klog^2 k)}cdot n^{O(1)}$ whether a strongly connected digraph on $n$ vertices has an out-branching with at least $k$ leaves. On acyclic digraphs the running time of our algorithm is $2^{O(klog k)}cdot n^{O(1)}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
