اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the hyperbolicity constant of circular-arc graphs
92
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Gromov hyperbolicity is an interesting geometric property, and so it is natural to study it in the context of geometric graphs. It measures the tree-likeness of a graph from a metric viewpoint. In particular, we are interested in circular-arc graphs, which is an important class of geometric intersection graphs. In this paper we give sharp bounds for the hyperbolicity constant of (finite and infinite) circular-arc graphs. Moreover, we obtain bounds for the hyperbolicity constant of the complement and line of any circular-arc graph. In order to do that, we obtain new results about regular, chordal and line graphs which are interesting by themselves.
قيم البحث
اقرأ أيضاً
To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let $mathcal{G}(g,c,n)$ be the set of graphs $G$ with girth $g(G)=g$, circumference $c(G)=c$, and
$n$ vertices; and let $mathcal{H}(g,c,m)$ be the set of graphs with girth $g$, circumference $c$, and $m$ edges. In this work, we study the four following extremal problems on graphs: $A(g,c,n)=min{delta(G),|; G in mathcal{G}(g,c,n) }$, $B(g,c,n)=max{delta(G),|; G in mathcal{G}(g,c,n) }$, $alpha(g,c,m)=min{delta(G),|; in mathcal{H}(g,c,m) }$ and $beta(g,c,m)=max{delta(G),|; G in mathcal{H}(g,c,m) }$. In particular, we obtain bounds for $A(g,c,n)$ and $alpha(g,c,m)$, and we compute the precise value of $B(g,c,n)$ and $beta(g,c,m)$ for all values of $g$, $c$, $n$ and $m$.
If $X$ is a geodesic metric space and $x_{1},x_{2},x_{3} in X$, a geodesic triangle $T={x_{1},x_{2},x_{3}}$ is the union of the three geodesics $[x_{1}x_{2}]$, $[x_{2}x_{3}]$ and $[x_{3}x_{1}]$ in $X$. The space $X$ is $delta$-hyperbolic in the Gromo
v sense if any side of $T$ is contained in a $delta$-neighborhood of the union of the two other sides, for every geodesic triangle $T$ in $X$. If $X$ is hyperbolic, we denote by $delta(X)$ the sharp hyperbolicity constant of $X$, i.e. $delta(X) =inf { deltageq 0:{0.3cm}$ X ${0.2cm}$ $text{is} {0.2cm} delta text{-hyperbolic} }.$ To compute the hyperbolicity constant is a very hard problem. Then it is natural to try to bound the hyperbolycity constant in terms of some parameters of the graph. Denote by $mathcal{G}(n,m)$ the set of graphs $G$ with $n$ vertices and $m$ edges, and such that every edge has length $1$. In this work we estimate $A(n,m):=min{delta(G)mid G in mathcal{G}(n,m) }$ and $B(n,m):=max{delta(G)mid G in mathcal{G}(n,m) }$. In particular, we obtain good bounds for $B(n,m)$, and we compute the precise value of $A(n,m)$ for all values of $n$ and $m$. Besides, we apply these results to random graphs.
We study the dominating set reconfiguration problem with the token sliding rule. It consists, given a graph G=(V,E) and two dominating sets D_s and D_t of G, in determining if there exists a sequence S=<D_1:=D_s,...,D_l:=D_t> of dominating sets of G
such that for any two consecutive dominating sets D_r and D_{r+1} with r<t, D_{r+1}=(D_r u) U v, where uv is an edge of G. In a recent paper, Bonamy et al studied this problem and raised the following questions: what is the complexity of this problem on circular arc graphs? On circle graphs? In this paper, we answer both questions by proving that the problem is polynomial on circular-arc graphs and PSPACE-complete on circle graphs.
The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the intermediate class of intersection graphs for families of circular ar
cs that satisfy the Helly property. We solve the isomorphism problem for this class in logarithmic space. If an input graph has a Helly circular-arc model, our algorithm constructs it canonically, which means that the models constructed for isomorphic graphs are equal.
The arc graph $delta(G)$ of a digraph $G$ is the digraph with the set of arcs of $G$ as vertex-set, where the arcs of $delta(G)$ join consecutive arcs of $G$. In 1981, Poljak and R{o}dl characterised the chromatic number of $delta(G)$ in terms of the
chromatic number of $G$ when $G$ is symmetric (i.e., undirected). In contrast, directed graphs with equal chromatic numbers can have arc graphs with distinct chromatic numbers. Even though the arc graph of a symmetric graph is not symmetric, we show that the chromatic number of the iterated arc graph $delta^k(G)$ still only depends on the chromatic number of $G$ when $G$ is symmetric.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
