Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNetwork routing on regular directed graphs from spanning factorizations
162
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
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.
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.
We prove that for each $Dge 2$ there exists $c>0$ such that whenever $ble cbig(tfrac{n}{log n}big)^{1/D}$, in the $(1:b)$ Maker-Breaker game played on $E(K_n)$, Maker has a strategy to guarantee claiming a graph $G$ containing copies of all graphs $H$ with $v(H)le n$ and $Delta(H)le D$. We show further that the graph $G$ guaranteed by this strategy also contains copies of any graph $H$ with bounded maximum degree and degeneracy at most $tfrac{D-1}{2}$. This lower bound on the threshold bias is sharp up to the $log$-factor when $H$ consists of $tfrac{n}{3}$ vertex-disjoint triangles or $tfrac{n}{4}$ vertex-disjoint $K_4$-copies.
In this article, we discuss when one can extend an r-regular graph to an r + 1 regular by adding edges. Different conditions on the num- ber of vertices n and regularity r are developed. We derive an upper bound of r, depending on n, for which, every regular graph G(n, r) can be extended to an r + 1-regular graph with n vertices. Presence of induced complete bipartite subgraph and complete subgraph is dis- cussed, separately, for the extension of regularity.
We study the curvature-dimension inequality in regular graphs. We develop techniques for calculating the curvature of such graphs, and we give characterizations of classes of graphs with positive, zero, and negative curvature. Our main result is to compare the curvature-dimension inequality in these classes to the so-called Ollivier curvature. A consequence of our results is that in the case that the graph contains no subgraph isomorphic to either $K_3$ or $K_{2,3}$ these curvatures usually have the same sign, and we characterize the exceptions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
