اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSome new results on bar visibility of digraphs
104
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Visibility representation of digraphs was introduced by Axenovich, Beveridge, Hutch-inson, and West (emph{SIAM J. Discrete Math.} {bf 27}(3) (2013) 1429--1449) as a natural generalization of $t$-bar visibility representation of undirected graphs. A {it $t$-bar visibility representation} of a digraph $G$ assigns each vertex at most $t$ horizontal bars in the plane so that there is an arc $xy$ in the digraph if and only if some bar for $x$ sees some bar for $y$ above it along an unblocked vertical strip with positive width. The {it visibility number} $b(G)$ is the least $t$ such that $G$ has a $t$-bar visibility representation. In this paper, we solve several problems about $b(G)$ posed by Axenovich et al. and prove that determining whether the bar visibility number of a digraph is $2$ is NP-complete.
قيم البحث
اقرأ أيضاً
In this paper, we characterize the extremal digraphs with the maximal or minimal $alpha$-spectral radius among some digraph classes such as rose digraphs, generalized theta digraphs and tri-ring digraphs with given size $m$. These digraph classes are
denoted by $mathcal{R}_{m}^k$, $widetilde{boldsymbol{Theta}}_k(m)$ and $INF(m)$ respectively. The main results about spectral extremal digraph by Guo and Liu in cite{MR2954483} and Li and Wang in cite{MR3777498} are generalized to $alpha$-spectral graph theory. As a by-product of our main results, an open problem in cite{MR3777498} is answered. Furthermore, we determine the digraphs with the first three minimal $alpha$-spectral radius among all strongly connected digraphs. Meanwhile, we determine the unique digraph with the fourth minimal $alpha$-spectral radius among all strongly connected digraphs for $0le alpha le frac{1}{2}$.
A $t$-bar visibility representation of a graph assigns each vertex up to $t$ horizontal bars in the plane so that two vertices are adjacent if and only if some bar for one vertex can see some bar for the other via an unobstructed vertical channel of
positive width. The least $t$ such that $G$ has a $t$-bar visibility representation is the bar visibility number of $G$, denoted by $b(G)$. For the complete bipartite graph $K_{m,n}$, the lower bound $b(K_{m,n})gelceil{frac{mn+4}{2m+2n}}rceil$ from Eulers Formula is well known. We prove that equality holds.
Let $D=(V,A)$ be an acyclic digraph. For $xin V$ define $e_{_{D}}(x)$ to be the difference of the indegree and the outdegree of $x$. An acyclic ordering of the vertices of $D$ is a one-to-one map $g: V rightarrow [1,|V|] $ that has the property that
for all $x,yin V$ if $(x,y)in A$, then $g(x) < g(y)$. We prove that for every acyclic ordering $g$ of $D$ the following inequality holds: [sum_{xin V} e_{_{D}}(x)cdot g(x) ~geq~ frac{1}{2} sum_{xin V}[e_{_{D}}(x)]^2~.] The class of acyclic digraphs for which equality holds is determined as the class of comparbility digraphs of posets of order dimension two.
In 1965, Motzkin and Straus [5] provided a new proof of Turans theorem based on a continuous characterization of the clique number of a graph using the Lagrangian of a graph. This new proof aroused interests in the study of Lagrangians of r-uniform g
raphs. The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Sidorenko and Frankl-Furedi applied Lagrangians of hypergraphs in finding Turan densities of hypergraphs. Frankl and Rodl applied it in disproving Erdos jumping constant conjecture. In most applications, we need an upper bound for the Lagrangian of a hypergraph. Frankl and Furedi conjectured that the r-uniform graph with m edges formed by taking the first m sets in the colex ordering of $N^(r)$ has the largest Lagrangian of all r-uniform graphs with m edges. Talbot in [14] provided some evidences for Frankl and Furedis conjecture. In this paper, we prove that the r-uniform graph with m edges formed by taking the first m sets in the colex ordering of $N^(r)$ has the largest Lagrangian of all r-uniform graphs on t vertices with m edges when ${t choose r}-3$ or ${t choose r}-4$. As an implication, we also prove that Frankl and Furedis conjecture holds for 3-uniform graphs with ${t choose 3}-3$ or ${t choose 3}-4$ edges.
Given a proper edge coloring $varphi$ of a graph $G$, we define the palette $S_{G}(v,varphi)$ of a vertex $v in V(G)$ as the set of all colors appearing on edges incident with $v$. The palette index $check s(G)$ of $G$ is the minimum number of distin
ct palettes occurring in a proper edge coloring of $G$. In this paper we give various upper and lower bounds on the palette index of $G$ in terms of the vertex degrees of $G$, particularly for the case when $G$ is a bipartite graph with small vertex degrees. Some of our results concern $(a,b)$-biregular graphs; that is, bipartite graphs where all vertices in one part have degree $a$ and all vertices in the other part have degree $b$. We conjecture that if $G$ is $(a,b)$-biregular, then $check{s}(G)leq 1+max{a,b}$, and we prove that this conjecture holds for several families of $(a,b)$-biregular graphs. Additionally, we characterize the graphs whose palette index equals the number of vertices.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
