Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGraphs with many strong orientations
253
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Given a digraph $D$ with $m$ arcs and a bijection $tau: A(D)rightarrow {1, 2, ldots, m}$, we say $(D, tau)$ is an antimagic orientation of a graph $G$ if $D$ is an orientation of $G$ and no two vertices in $D$ have the same vertex-sum under $tau$, where the vertex-sum of a vertex $u$ in $D$ under $tau$ is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. Hefetz, M{u}tze, and Schwartz in 2010 initiated the study of antimagic orientations of graphs, and conjectured that every connected graph admits an antimagic orientation. This conjecture seems hard, and few related results are known. However, it has been verified to be true for regular graphs, biregular bipartite graphs, and graphs with large maximum degree. In this paper, we establish more evidence for the aforementioned conjecture by studying antimagic orientations of graphs $G$ with independence number at least $|V(G)|/2$ or at most four. We obtain several results. The method we develop in this paper may shed some light on attacking the aforementioned conjecture.
Given a digraph $D$ with $m $ arcs, a bijection $tau: A(D)rightarrow {1, 2, ldots, m}$ is an antimagic labeling of $D$ if no two vertices in $D$ have the same vertex-sum, where the vertex-sum of a vertex $u $ in $D$ under $tau$ is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. We say $(D, tau)$ is an antimagic orientation of a graph $G$ if $D$ is an orientation of $G$ and $tau$ is an antimagic labeling of $D$. Motivated by the conjecture of Hartsfield and Ringel from 1990 on antimagic labelings of graphs, Hefetz, M{u}tze, and Schwartz in 2010 initiated the study of antimagic orientations of graphs, and conjectured that every connected graph admits an antimagic orientation. This conjecture seems hard, and few related results are known. However, it has been verified to be true for regular graphs and biregular bipartite graphs. In this paper, we prove that every connected graph $G$ on $nge9$ vertices with maximum degree at least $n-5$ admits an antimagic orientation.
We give a characterization of Pfaffian graphs in terms of even orientations, extending the characterization of near bipartite non--pfaffian graphs by Fischer and Little cite{FL}. Our graph theoretical characterization is equivalent to the one proved by Little in cite{L73} (cf. cite{LR}) using linear algebra arguments.
Let $S_k(n)$ be the maximum number of orientations of an $n$-vertex graph $G$ in which no copy of $K_k$ is strongly connected. For all integers $n$, $kgeq 4$ where $ngeq 5$ or $kgeq 5$, we prove that $S_k(n) = 2^{t_{k-1}(n)}$, where $t_{k-1}(n)$ is the number of edges of the $n$-vertex $(k-1)$-partite Turan graph $T_{k-1}(n)$, and that $T_{k-1}(n)$ is the only $n$-vertex graph with this number of orientations. Furthermore, $S_4(4) = 40$ and this maximality is achieved only by $K_4$.
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].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
