Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn digraphs with polygonal restricted numerical range
119
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In 2020, Cameron et al. introduced the restricted numerical range of a digraph (directed graph) as a tool for characterizing digraphs and studying their algebraic connectivity. In particular, digraphs with a restricted numerical range of a single point, a horizontal line segment, and a vertical line segment were characterized as $k$-imploding stars, directed joins of bidirectional digraphs, and regular tournaments, respectively. In this article, we extend these results by investigating digraphs whose restricted numerical range is a convex polygon in the complex plane. We provide computational methods for identifying these polygonal digraphs and show that these digraphs can be broken into three disjoint classes: normal, restricted-normal, and pseudo-normal digraphs, all of which are closed under the digraph complement. We prove sufficient conditions for normal digraphs and show that the directed join of two normal digraphs results in a restricted-normal digraph. Also, we prove that directed joins are the only restricted-normal digraphs when the order is square-free or twice a square-free number. Finally, we provide methods to construct restricted-normal digraphs that are not directed joins for all orders that are neither square-free nor twice a square-free number.
rate research
Read More
Let g be a strategy-proof rule on the domain NP of profiles where no alternative Pareto-dominates any other and let g have range S on NP. We complete the proof of a Gibbard-Satterthwaite result - if S contains more than two elements, then g is dictatorial - by establishing a full range result on two subdomains of NP.
We discuss transpose (sometimes called universal exchange or all-to-all) on vertex symmetric networks. We provide a method to compare the efficiency of transpose schemes on two different networks with a cost function based on the number processors and wires needed to complete a given algorithm in a given time.
We prove a conjecture of Fox, Huang, and Lee that characterizes directed graphs that have constant density in all tournaments: they are disjoint unions of trees that are each constructed in a certain recursive way.
The cutoff phenomenon was recently confirmed for random walks on Ramanujan graphs by the first author and Peres. In this work, we obtain analogs in higher dimensions, for random walk operators on any Ramanujan complex associated with a simple group $G$ over a local field $F$. We show that if $T$ is any $k$-regular $G$-equivariant operator on the Bruhat-Tits building with a simple combinatorial property (collision-free), the associated random walk on the $n$-vertex Ramanujan complex has cutoff at time $log_k n$. The high dimensional case, unlike that of graphs, requires tools from non-commutative harmonic analysis and the infinite-dimensional representation theory of $G$. Via these, we show that operators $T$ as above on Ramanujan complexes give rise to Ramanujan digraphs with a special property ($r$-normal), implying cutoff. Applications include geodesic flow operators, geometric implications, and a confirmation of the Riemann Hypothesis for the associated zeta functions over every group $G$, previously known for groups of type $widetilde A_n$ and $widetilde C_2$.
Let $D=(V,A)$ be a digraphs without isolated vertices. A vertex-degree based invariant $I(D)$ related to a real function $varphi$ of $D$ is defined as a summation over all arcs, $I(D) = frac{1}{2}sum_{uvin A}{varphi(d_u^+,d_v^-)}$, where $d_u^+$ (resp. $d_u^-$) denotes the out-degree (resp. in-degree) of a vertex $u$. In this paper, we give the extremal values and extremal digraphs of $I(D)$ over all digraphs with $n$ non-isolated vertices. Applying these results, we obtain the extremal values of some vertex-degree based topological indices of digraphs, such as the Randi{c} index, the Zagreb index, the sum-connectivity index, the $GA$ index, the $ABC$ index and the harmonic index, and the corresponding extremal digraphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
