Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFurther results on random cubic planar graphs
174
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We provide precise asymptotic estimates for the number of several classes of labelled cubic planar graphs, and we analyze properties of such random graphs under the uniform distribution. This model was first analyzed by Bodirsky et al. (Random Structures Algorithms 2007). We revisit their work and obtain new results on the enumeration of cubic planar graphs and on random cubic planar graphs. In particular, we determine the exact probability of a random cubic planar graph being connected, and we show that the distribution of the number of triangles in random cubic planar graphs is asymptotically normal with linear expectation and variance. To the best of our knowledge, this is the first time one is able to determine the asymptotic distribution for the number of copies of a fixed graph containing a cycle in classes of random planar graphs arising from planar maps.
rate research
Read More
A emph{proper $t$-edge-coloring} of a graph $G$ is a mapping $alpha: E(G)rightarrow {1,ldots,t}$ such that all colors are used, and $alpha(e) eq alpha(e^{prime})$ for every pair of adjacent edges $e,e^{prime}in E(G)$. If $alpha $ is a proper edge-coloring of a graph $G$ and $vin V(G)$, then emph{the spectrum of a vertex $v$}, denoted by $Sleft(v,alpha right)$, is the set of all colors appearing on edges incident to $v$. emph{The deficiency of $alpha$ at vertex $vin V(G)$}, denoted by $def(v,alpha)$, is the minimum number of integers which must be added to $Sleft(v,alpha right)$ to form an interval, and emph{the deficiency $defleft(G,alpharight)$ of a proper edge-coloring $alpha$ of $G$} is defined as the sum $sum_{vin V(G)}def(v,alpha)$. emph{The deficiency of a graph $G$}, denoted by $def(G)$, is defined as follows: $def(G)=min_{alpha}defleft(G,alpharight)$, where minimum is taken over all possible proper edge-colorings of $G$. For a graph $G$, the smallest and the largest values of $t$ for which it has a proper $t$-edge-coloring $alpha$ with deficiency $def(G,alpha)=def(G)$ are denoted by $w_{def}(G)$ and $W_{def}(G)$, respectively. In this paper, we obtain some bounds on $w_{def}(G)$ and $W_{def}(G)$. In particular, we show that for any $lin mathbb{N}$, there exists a graph $G$ such that $def(G)>0$ and $W_{def}(G)-w_{def}(G)geq l$. It is known that for the complete graph $K_{2n+1}$, $def(K_{2n+1})=n$ ($nin mathbb{N}$). Recently, Borowiecka-Olszewska, Drgas-Burchardt and Ha{l}uszczak posed the following conjecture on the deficiency of near-complete graphs: if $nin mathbb{N}$, then $def(K_{2n+1}-e)=n-1$. In this paper, we confirm this conjecture.
In this article we associate a combinatorial differential graded algebra to a cubic planar graph G. This algebra is defined combinatorially by counting binary sequences, which we introduce, and several explicit computations are provided. In addition, in the appendix by K. Sackel the F(q)-rational points of its graded augmentation variety are shown to coincide with (q+1)-colorings of the dual graph.
Let $G$ be a nontrivial connected and vertex-colored graph. A subset $X$ of the vertex set of $G$ is called rainbow if any two vertices in $X$ have distinct colors. The graph $G$ is called emph{rainbow vertex-disconnected} if for any two vertices $x$ and $y$ of $G$, there exists a vertex subset $S$ such that when $x$ and $y$ are nonadjacent, $S$ is rainbow and $x$ and $y$ belong to different components of $G-S$; whereas when $x$ and $y$ are adjacent, $S+x$ or $S+y$ is rainbow and $x$ and $y$ belong to different components of $(G-xy)-S$. Such a vertex subset $S$ is called a emph{rainbow vertex-cut} of $G$. For a connected graph $G$, the emph{rainbow vertex-disconnection number} of $G$, denoted by $rvd(G)$, is the minimum number of colors that are needed to make $G$ rainbow vertex-disconnected. In this paper, we obtain bounds of the rainbow vertex-disconnection number of a graph in terms of the minimum degree and maximum degree of the graph. We give a tighter upper bound for the maximum size of a graph $G$ with $rvd(G)=k$ for $kgeqfrac{n}{2}$. We then characterize the graphs of order $n$ with rainbow vertex-disconnection number $n-1$ and obtain the maximum size of a graph $G$ with $rvd(G)=n-1$. Moreover, we get a sharp threshold function for the property $rvd(G(n,p))=n$ and prove that almost all graphs $G$ have $rvd(G)=rvd(overline{G})=n$. Finally, we obtain some Nordhaus-Gaddum-type results: $n-5leq rvd(G)+rvd(overline{G})leq 2n$ and $n-1leq rvd(G)cdot rvd(overline{G})leq n^2$ for the rainbow vertex-disconnection numbers of nontrivial connected graphs $G$ and $overline{G}$ with order $ngeq 24$.
A well-known conjecture by Lovasz and Plummer from the 1970s asserted that a bridgeless cubic graph has exponentially many perfect matchings. It was solved in the affirmative by Esperet et al. (Adv. Math. 2011). On the other hand, Chudnovsky and Seymour (Combinatorica 2012) proved the conjecture in the special case of cubic planar graphs. In our work we consider random bridgeless cubic planar graphs with the uniform distribution on graphs with $n$ vertices. Under this model we show that the expected number of perfect matchings in labeled bridgeless cubic planar graphs is asymptotically $cgamma^n$, where $c>0$ and $gamma sim 1.14196$ is an explicit algebraic number. We also compute the expected number of perfect matchings in (non necessarily bridgeless) cubic planar graphs and provide lower bounds for unlabeled graphs. Our starting point is a correspondence between counting perfect matchings in rooted cubic planar maps and the partition function of the Ising model in rooted triangulations.
A close relation between hitting times of the simple random walk on a graph, the Kirchhoff index, resistance-centrality, and related invariants of unicyclic graphs is displayed. Combining with the graph transformations and some other techniques, sharp upper and lower bounds on the cover cost (resp. reverse cover cost) of a vertex in an $n$-vertex unicyclic graph are determined. All the corresponding extremal graphs are identified, respectively.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
