اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNote on semi-proper orientations of outerplanar graphs
133
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A semi-proper orientation of a given graph $G$, denoted by $(D,w)$, is an orientation $D$ with a weight function $w: A(D)rightarrow mathbb{Z}_+$, such that the in-weight of any adjacent vertices are distinct, where the in-weight of $v$ in $D$, denoted by $w^-_D(v)$, is the sum of the weights of arcs towards $v$. The semi-proper orientation number of a graph $G$, denoted by $overrightarrow{chi}_s(G)$, is the minimum of maximum in-weight of $v$ in $D$ over all semi-proper orientation $(D,w)$ of $G$. This parameter was first introduced by Dehghan (2019). When the weights of all edges eqaul to one, this parameter is equal to the proper orientation number of $G$. The optimal semi-proper orientation is a semi-proper orientation $(D,w)$ such that $max_{vin V(G)}w_D^-(v)=overrightarrow{chi}_s(G)$. Araujo et al. (2016) showed that $overrightarrow{chi}(G)le 7$ for every cactus $G$ and the bound is tight. We prove that for every cactus $G$, $overrightarrow{chi}_s(G) le 3$ and the bound is tight. Ara{u}jo et al. (2015) asked whether there is a constant $c$ such that $overrightarrow{chi}(G)le c$ for all outerplanar graphs $G.$ While this problem remains open, we consider it in the weighted case. We prove that for every outerplanar graph $G,$ $overrightarrow{chi}_s(G)le 4$ and the bound is tight.
قيم البحث
اقرأ أيضاً
An orientation of $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of two possible arcs with the same endpoints. We call an orientation emph{proper} if neighbouring vertices have different in-degrees. The proper orientation nu
mber of a graph $G$, denoted by $vec{chi}(G)$, is the minimum maximum in-degree of a proper orientation of G. Araujo et al. (Theor. Comput. Sci. 639 (2016) 14--25) asked whether there is a constant $c$ such that $vec{chi}(G)leq c$ for every outerplanar graph $G$ and showed that $vec{chi}(G)leq 7$ for every cactus $G.$ We prove that $vec{chi}(G)leq 3$ if $G$ is a triangle-free $2$-connected outerplanar graph and $vec{chi}(G)leq 4$ if $G$ is a triangle-free bridgeless outerplanar graph.
Motivated by the conjecture of Hartsfield and Ringel on antimagic labelings of undirected graphs, Hefetz, M{u}tze, and Schwartz initiated the study of antimagic labelings of digraphs in 2010. Very recently, it has been conjectured in [Antimagic orien
tation of even regular graphs, J. Graph Theory, 90 (2019), 46-53.] that every graph admits an antimagtic orientation, which is a strengthening of an earlier conjecture of Hefetz, M{u}tze and Schwartz. In this paper, we prove that every $2d$-regular graph (not necessarily connected) admits an antimagic orientation, where $dge2$. Together with known results, our main result implies that the above-mentioned conjecture is true for all regular graphs.
A graph G is 1-extendable if every edge belongs to at least one 1-factor. Let G be a graph with a 1-factor F. Then an even F-orientation of G is an orientation in which each F-alternating cycle has exactly an even number of edges directed in the same
fixed direction around the cycle. In this paper, we examine the structure of 1-extendible graphs G which have no even F-orientation where F is a fixed 1-factor of G. In the case of cubic graphs we give a characterization. In a companion paper [M. Abreu, D. Labbate and J. Sheehan. Even orientations of graphs: Part II], we complete this characterization in the case of regular graphs, graphs of connectivity at least four and k--regular graphs for $kge3$. Moreover, we will point out a relationship between our results on even orientations and Pfaffian graphs developed in [M. Abreu, D. Labbate and J. Sheehan. Even orientations and Pfaffian graphs].
We count orientations of $G(n,p)$ avoiding certain classes of oriented graphs. In particular, we study $T_r(n,p)$, the number of orientations of the binomial random graph $G(n,p)$ in which every copy of $K_r$ is transitive, and $S_r(n,p)$, the number
of orientations of $G(n,p)$ containing no strongly connected copy of $K_r$. We give the correct order of growth of $log T_r(n,p)$ and $log S_r(n,p)$ up to polylogarithmic factors; for orientations with no cyclic triangle, this significantly improves a result of Allen, Kohayakawa, Mota and Parente. We also discuss the problem for a single forbidden oriented graph, and state a number of open problems and conjectures.
We establish mild conditions under which a possibly irregular, sparse graph $G$ has many strong orientations. Given a graph $G$ on $n$ vertices, orient each edge in either direction with probability $1/2$ independently. We show that if $G$ satisfies
a minimum degree condition of $(1+c_1)log_2{n}$ and has Cheeger constant at least $c_2frac{log_2log_2{n}}{log_2{n}}$, then the resulting randomly oriented directed graph is strongly connected with high probability. This Cheeger constant bound can be replaced by an analogous spectral condition via the Cheeger inequality. Additionally, we provide an explicit construction to show our minimum degree condition is tight while the Cheeger constant bound is tight up to a $log_2log_2{n}$ factor.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
