Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMidrange crossing constants for graphs classes
58
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 the 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.
145 -
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 invariant 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
