Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the number of clusters for planar graphs
129
0
0.0
(
0
)
Authors
Jean-Michel Billiot
Ask ChatGPT about the research
No Arabic abstract
The Tutte polynomial is a powerfull analytic tool to study the structure of planar graphs. In this paper, we establish some relations between the number of clusters per bond for planar graph and its dual : these relations bring into play the coordination number of the graphs. The factorial moment measure of the number of clusters per bond are given using the derivative of the Tutte polynomial. Examples are presented for simple planar graph. The cases of square, triangular, honeycomb, Archimedean and Laves lattices are discussed.
rate research
Read More
We consider the asymptotic shape of clusters in the Eden model on a d-dimensional hypercubical lattice. We discuss two improvements for the well-known upper bound to the growth velocity in different directions by that of the independent branching process (IBP). In the IBP, each cell gives rise to a daughter cell at a neighboring site at a constant rate. In the first improvement, we do not allow such births along the bond connecting the cell to its mother cell. In the second, we iteratively evolve the system by a growth as IBP for a duration $Delta$ t, followed by culling process in which if any cell produced a descendant within this interval, who occupies the same site as the cell itself, then the descendant is removed. We study the improvement on the upper bound on the velocity for different dimensions d. The bounds are asymptotically exact in the large-d limit. But in $d =2$, the improvement over the IBP approximation is only a few percent.
We prove that the spectral gap of a finite planar graph $X$ is bounded by $lambda_1(X)le C(frac{log(diam X)}{diam X})^2$ where $C$ depends only on the degree of $X$. We then give a sequence of such graphs showing the the above estimate cannot be improved. This yields a negative answer to a question of Benjamini and Curien on the mixing times of the simple random walk on planar graphs.
We prove that the number of Hamilton cycles in the random graph G(n,p) is n!p^n(1+o(1))^n a.a.s., provided that pgeq (ln n+ln ln n+omega(1))/n. Furthermore, we prove the hitting-time version of this statement, showing that in the random graph process, the edge that creates a graph of minimum degree 2 creates (ln n/e)^n(1+o(1))^n Hamilton cycles a.a.s.
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.
Wegner conjectured in 1977 that the square of every planar graph with maximum degree at most $3$ is $7$-colorable. We prove this conjecture using the discharging method and computational techniques to verify reducible configurations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
