اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMidrange crossing constants for graphs classes
58
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
For positive integers $n$ and $e$, let $kappa(n,e)$ be the minimum crossing number (the standard planar crossing number) taken over all graphs with $n$ vertices and at least $e$ edges. Pach, Spencer and Toth [Discrete and Computational Geometry 24 623--644, (2000)] showed that $kappa(n,e) n^2/e^3$ tends to a positive constant (called midrange crossing constant) as $nto infty$ and $n ll e ll n^2$, proving a conjecture of ErdH{o}s and Guy. In this note, we extend their proof to show that the midrange crossing constant exists for graph classes that satisfy a certain set of graph properties. As a corollary, we show that the the midrange crossing constant exists for the family of bipartite graphs. All these results have their analogues for rectilinear crossing numbers.
قيم البحث
اقرأ أيضاً
Let $mathcal G$ be an addable, minor-closed class of graphs. We prove that the zero-one law holds in monadic second-order logic (MSO) for the random graph drawn uniformly at random from all {em connected} graphs in $mathcal G$ on $n$ vertices, and th
e convergence law in MSO holds if we draw uniformly at random from all graphs in $mathcal G$ on $n$ vertices. We also prove analogues of these results for the class of graphs embeddable on a fixed surface, provided we restrict attention to first order logic (FO). Moreover, the limiting probability that a given FO sentence is satisfied is independent of the surface $S$. We also prove that the closure of the set of limiting probabilities is always the finite union of at least two disjoint intervals, and that it is the same for FO and MSO. For the classes of forests and planar graphs we are able to determine the closure of the set of limiting probabilities precisely. For planar graphs it consists of exactly 108 intervals, each of length $approx 5cdot 10^{-6}$. Finally, we analyse examples of non-addable classes where the behaviour is quite different. For instance, the zero-one law does not hold for the random caterpillar on $n$ vertices, even in FO.
86 -
Sunil Kumar R (Research Scholar
, Department of Computer Applications
, n Cochin University of Science
2014
There are several centrality measures that have been introduced and studied for real world networks. They account for the different vertex characteristics that permit them to be ranked in order of importance in the network. Betweenness centrality is
a measure of the influence of a vertex over the flow of information between every pair of vertices under the assumption that information primarily flows over the shortest path between them. In this paper we present betweenness centrality of some important classes of graphs.
We develop a local positivity theory for movable curves on projective varieties similar to the classical Seshadri constants of nef divisors. We give analogues of the Seshadri ampleness criterion, of a characterization of the augmented base locus of a
big and nef divisor, and of the interpretation of Seshadri constants as an asymptotic measure of jet separation. We also study the case of arbitrary codimension.
We introduce a family of multi-way Cheeger-type constants ${h_k^{sigma}, k=1,2,ldots, n}$ on a signed graph $Gamma=(G,sigma)$ such that $h_k^{sigma}=0$ if and only if $Gamma$ has $k$ balanced connected components. These constants are switching invari
ant and bring together in a unified viewpoint a number of important graph-theoretical concepts, including the classical Cheeger constant, those measures of bipartiteness introduced by Desai-Rao, Trevisan, Bauer-Jost, respectively, on unsigned graphs,, and the frustration index (originally called the line index of balance by Harary) on signed graphs. We further unify the (higher-order or improved) Cheeger and dual Cheeger inequalities for unsigned graphs as well as the underlying algorithmic proof techniques by establishing their correspondi
For a given class $mathcal{C}$ of graphs and given integers $m leq n$, let $f_mathcal{C}(n,m)$ be the minimal number $k$ such that every $k$ independent $n$-sets in any graph belonging to $mathcal{C}$ have a (possibly partial) rainbow independent $m$
-set. Motivated by known results on the finiteness and actual value of $f_mathcal{C}(n,m)$ when $mathcal{C}$ is the class of line graphs of graphs, we study this function for various other classes.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
