اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFull Orientability of the Square of a Cycle
313
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let D be an acyclic orientation of a simple graph G. An arc of D is called dependent if its reversal creates a directed cycle. Let d(D) denote the number of dependent arcs in D. Define m and M to be the minimum and the maximum number of d(D) over all acyclic orientations D of G. We call G fully orientable if G has an acyclic orientation with exactly k dependent arcs for every k satisfying m <= k <= M. In this paper, we prove that the square of a cycle C_n of length n is fully orientable except n=6.
قيم البحث
اقرأ أيضاً
An orientation of a graph is semi-transitive if it is acyclic, and for any directed path $v_0rightarrow v_1rightarrow cdotsrightarrow v_k$ either there is no arc between $v_0$ and $v_k$, or $v_irightarrow v_j$ is an arc for all $0leq i<jleq k$. An un
directed graph is semi-transitive if it admits a semi-transitive orientation. Semi-transitive graphs generalize several important classes of graphs and they are precisely the class of word-representable graphs studied extensively in the literature. Determining if a triangle-free graph is semi-transitive is an NP-hard problem. The existence of non-semi-transitive triangle-free graphs was established via ErdH{o}s theorem by Halld{o}rsson and the authors in 2011. However, no explicit examples of such graphs were known until recent work of the first author and Saito who have shown computationally that a certain subgraph on 16 vertices of the triangle-free Kneser graph $K(8,3)$ is not semi-transitive, and have raised the question on the existence of smaller triangle-free non-semi-transitive graphs. In this paper we prove that the smallest triangle-free 4-chromatic graph on 11 vertices (the Grotzsch graph) and the smallest triangle-free 4-chromatic 4-regular graph on 12 vertices (the Chvatal graph) are not semi-transitive. Hence, the Grotzsch graph is the smallest triangle-free non-semi-transitive graph. We also prove the existence of semi-transitive graphs of girth 4 with chromatic number 4 including a small one (the circulant graph $C(13;1,5)$ on 13 vertices) and dense ones (Tofts graphs). Finally, we show that each $4$-regular circulant graph (possibly containing triangles) is semi-transitive.
We consider the class of semi-transitively orientable graphs, which is a much larger class of graphs compared to transitively orientable graphs, in other words, comparability graphs. Ever since the concept of a semi-transitive orientation was defined
as a crucial ingredient of the characterization of alternation graphs, also knownas word-representable graphs, it has sparked independent interest. In this paper, we investigate graph operations and graph products that preserve semitransitive orientability of graphs. The main theme of this paper is to determine which graph operations satisfy the following statement: if a graph operation is possible on a semitransitively orientable graph, then the same graph operation can be executed on the graph while preserving the semi-transitive orientability. We were able to prove that this statement is true for edge-deletions, edge-additions, and edge-liftings. Moreover, for all three graph operations,we showthat the initial semi-transitive orientation can be extended to the new graph obtained by the graph operation. Also, Kitaev and Lozin explicitly asked if certain graph products preserve the semitransitive orientability. We answer their question in the negative for the tensor product, lexicographic product, and strong product.We also push the investigation further and initiate the study of sufficient conditions that guarantee a certain graph operation to preserve the semi-transitive orientability.
An orientation of a graph is semi-transitive if it is acyclic, and for any directed path $v_0rightarrow v_1rightarrow cdotsrightarrow v_k$ either there is no edge between $v_0$ and $v_k$, or $v_irightarrow v_j$ is an edge for all $0leq i<jleq k$. An
undirected graph is semi-transitive if it admits a semi-transitive orientation. Semi-transitive graphs include several important classes of graphs such as 3-colorable graphs, comparability graphs, and circle graphs, and they are precisely the class of word-representable graphs studied extensively in the literature. In this paper, we study semi-transitive orientability of the celebrated Kneser graph $K(n,k)$, which is the graph whose vertices correspond to the $k$-element subsets of a set of $n$ elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. We show that for $ngeq 15k-24$, $K(n,k)$ is not semi-transitive, while for $kleq nleq 2k+1$, $K(n,k)$ is semi-transitive. Also, we show computationally that a subgraph $S$ on 16 vertices and 36 edges of $K(8,3)$, and thus $K(8,3)$ itself on 56 vertices and 280 edges, is non-semi-transitive. $S$ and $K(8,3)$ are the first explicit examples of triangle-free non-semi-transitive graphs, whose existence was established via ErdH{o}s theorem by Halld{o}rsson et al. in 2011. Moreover, we show that the complement graph $overline{K(n,k)}$ of $K(n,k)$ is semi-transitive if and only if $ngeq 2k$.
Suppose that you add rigid bars between points in the plane, and suppose that a constant fraction $q$ of the points moves freely in the whole plane; the remaining fraction is constrained to move on fixed lines called sliders. When does a giant rigid
cluster emerge? Under a genericity condition, the answer only depends on the graph formed by the points (vertices) and the bars (edges). We find for the random graph $G in mathcal{G}(n,c/n)$ the threshold value of $c$ for the appearance of a linear-sized rigid component as a function of $q$, generalizing results of Kasiviswanathan et al. We show that this appearance of a giant component undergoes a continuous transition for $q leq 1/2$ and a discontinuous transition for $q > 1/2$. In our proofs, we introduce a generalized notion of orientability interpolating between 1- and 2-orientability, of cores interpolating between 2-core and 3-core, and of extended cores interpolating between 2+1-core and 3+2-core; we find the precise expressions for the respective thresholds and the sizes of the different cores above the threshold. In particular, this proves a conjecture of Kasiviswanathan et al. about the size of the 3+2-core. We also derive some structural properties of rigidity with sliders (matroid and decomposition into components) which can be of independent interest.
The Turan number of a graph H, ex(n,H), is the maximum number of edges in a graph on n vertices which does not have H as a subgraph. Let P_k be the path with k vertices, the square P^2_k of P_k is obtained by joining the pairs of vertices with distan
ce one or two in P_k. The powerful theorem of ErdH{o}s, Stone and Simonovits determines the asymptotic behavior of ex(n,P^2_k). In the present paper, we determine the exact value of ex(n,P^2_5) and ex(n,P^2_6) and pose a conjecture for the exact value of ex(n,P^2_k).
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
