Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the local genus distribution of graph embeddings
79
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The $2$-cell embeddings of graphs on closed surfaces have been widely studied. It is well known that ($2$-cell) embedding a given graph $G$ on a closed orientable surface is equivalent to cyclically ordering the edges incident to each vertex of $G$. In this paper, we study the following problem: given a genus $g$ embedding $epsilon$ of the graph $G$ and a vertex of $G$, how many different ways of reembedding the vertex such that the resulting embedding $epsilon$ is of genus $g+Delta g$? We give formulas to compute this quantity and the local minimal genus achieved by reembedding. In the process we obtain miscellaneous results. In particular, if there exists a one-face embedding of $G$, then the probability of a random embedding of $G$ to be one-face is at least $prod_{ uin V(G)}frac{2}{deg( u)+2}$, where $deg( u)$ denotes the vertex degree of $ u$. Furthermore we obtain an easy-to-check necessary condition for a given embedding of $G$ to be an embedding of minimum genus.
rate research
Read More
The $2$-cell embeddings of graphs on closed surfaces have been widely studied. It is well known that ($2$-cell) embedding a given graph $G$ on a closed orientable surface is equivalent to cyclically ordering the edges incident to each vertex of $G$. In this paper, we study the following problem: given a genus $g$ embedding $mathbb{E}$ of the graph $G$, if we randomly rearrange the edges around a vertex, i.e., re-embedding, what is the probability of the resulting embedding $mathbb{E}$ having genus $g+Delta g$? We give a formula to compute this probability. Meanwhile, some other known and unknown results are also obtained. For example, we show that the probability of preserving the genus is at least $frac{2}{deg(v)+2}$ for re-embedding any vertex $v$ of degree $deg(v)$ in a one-face embedding; and we obtain a necessary condition for a given embedding of $G$ to be an embedding with the minimum genus.
It is known that the cop number $c(G)$ of a connected graph $G$ can be bounded as a function of the genus of the graph $g(G)$. The best known bound, that $c(G) leq leftlfloor frac{3 g(G)}{2}rightrfloor + 3$, was given by Schr{o}der, who conjectured that in fact $c(G) leq g(G) + 3$. We give the first improvement to Schr{o}ders bound, showing that $c(G) leq frac{4g(G)}{3} + frac{10}{3}$.
The first author together with Jenssen, Perkins and Roberts (2017) recently showed how local properties of the hard-core model on triangle-free graphs guarantee the existence of large independent sets, of size matching the best-known asymptotics due to Shearer (1983). The present work strengthens this in two ways: first, by guaranteeing stronger graph structure in terms of colourings through applications of the Lovasz local lemma; and second, by extending beyond triangle-free graphs in terms of local sparsity, treating for example graphs of bounded local edge density, of bounded local Hall ratio, and of bounded clique number. This generalises and improves upon much other earlier work, including that of Shearer (1995), Alon (1996) and Alon, Krivelevich and Sudakov (1999), and more recent results of Molloy (2019), Bernshteyn (2019) and Achlioptas, Iliopoulos and Sinclair (2019). Our results derive from a common framework built around the hard-core model. It pivots on a property we call local occupancy, giving a clean separation between the methods for deriving graph structure with probabilistic information and verifying the requisite probabilistic information itself.
The reconstruction conjecture has remained open for simple undirected graphs since it was suggested in 1941 by Kelly and Ulam. In an attempt to prove the conjecture, many graph invariants have been shown to be reconstructible from the vertex-deleted deck, and in particular, some prominent graph polynomials. Among these are the Tutte polynomial, the chromatic polynomial and the characteristic polynomial. We show that the interlace polynomial, the U -polynomial, the universal edge elimination polynomial xi and the colore
Frankl and Furedi (1989) conjectured that the $r$-graph with $m$ edges formed by taking the first $m$ sets in the colex ordering of ${mathbb N}^{(r)}$ has the largest graph-Lagrangian of all $r$-graphs with $m$ edges. In this paper, we establish some bounds for graph-Lagrangians of some special $r$-graphs that support this conjecture.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
