Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProper Orientation Number of Triangle-free Bridgeless Outerplanar Graphs
91
0
0.0
(
0
)
Added by
Gregory Gutin
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 number 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.
rate research
Read More
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.
For all $nge 9$, we show that the only triangle-free graphs on $n$ vertices maximizing the number $5$-cycles are balanced blow-ups of a 5-cycle. This completely resolves a conjecture by ErdH{o}s, and extends results by Grzesik and Hatami, Hladky, Kr{a}l, Norin and Razborov, where they independently showed this same result for large $n$ and for all $n$ divisible by $5$.
Switches are operations which make local changes to the edges of a graph, usually with the aim of preserving the vertex degrees. We study a restricted set of switches, called triangle switches. Each triangle switch creates or deletes at least one triangle. Triangle switches can be used to define Markov chains which generate graphs with a given degree sequence and with many more triangles (3-cycles) than is typical in a uniformly random graph with the same degrees. We show that the set of triangle switches connects the set of all $d$-regular graphs on $n$ vertices, for all $dgeq 3$. Hence, any Markov chain which assigns positive probability to all triangle switches is irreducible on these graphs. We also investigate this question for 2-regular graphs.
In this paper, we investigate the ratio of the numbers of odd and even cycles in outerplanar graphs. We verify that the ratio generally diverges to infinity as the order of a graph diverges to infinity. We also give sharp estimations of the ratio for several classes of outerplanar graphs, and obtain a constant upper bound of the ratio for some of them. Furthermore, we consider similar problems in graphs with some pairs of forbidden subgraphs/minors, and propose a challenging problem concerning claw-free graphs.
In this short note, we show that for any $epsilon >0$ and $k<n^{0.5-epsilon}$ the choice number of the Kneser graph $KG_{n,k}$ is $Theta (nlog n)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
