Generating unlabeled connected cubic planar graphs uniformly at random

We present an expected polynomial time algorithm to generate an unlabeled connected cubic planar graph uniformly at random. We first consider rooted connected cubic planar graphs, i.e., we count connected cubic planar graphs up to isomorphisms that fix a certain directed edge. Based on decompositions along the connectivity structure, we derive recurrence formulas for the exact number of rooted cubic planar graphs. This leads to rooted 3‐connected cubic planar graphs, which have a unique embedding on the sphere. Special care has to be taken for rooted graphs that have a sense‐reversing automorphism. Therefore we introduce the concept of colored networks, which stand in bijective correspondence to rooted 3‐connected cubic planar graphs with given symmetries. Colored networks can again be decomposed along the connectivity structure. For rooted 3‐connected cubic planar graphs embedded in the plane, we switch to the dual and count rooted triangulations. Since all these numbers can be evaluated in polynomial time using dynamic programming, rooted connected cubic planar graphs can be generated uniformly at random in polynomial time by inverting the decomposition along the connectivity structure. To generate connected cubic planar graphs without a root uniformly at random, we apply rejection sampling and obtain an expected polynomial time algorithm. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Threshold functions for small subgraphs in simple graphs and multigraphs

We revisit the problem of counting the number of copies of a fixed graph in a random graph or multigraph, for various models of random (multi)graphs. For our proofs we introduce the notion of patchworks to describe the possible overlappings of copies of subgraphs. Furthermore, the proofs are based on analytic combinatorics to carry out asymptotic computations. The flexibility of our approach allows us to tackle a wide range of problems. We obtain the asymptotic number and the limiting distribution of the number of subgraphs which are isomorphic to a graph from a given set of graphs. The results apply to multigraphs as well as to (multi)graphs with degree constraints. One application is to scale-free multigraphs, where the degree distribution follows a power law, for which we show how to obtain the asymptotic number of copies of a given subgraph and give as an illustration the expected number of small cycles.     

Asymptotic connectivity of infinite graphs

We introduce the notion of the asymptotic connectivity of a graph by generalizing to infinite graphs average connectivity as defined by Beineke, Oellermann, and Pippert. Combinatorial and geometric properties of asymptotic connectivity are then explored. In particular, we compute the asymptotic connectivity of a number of planar graphs in order to determine the extent to which this measure correlates with the large-scale geometry of the graph.     

Greedy maximal independent sets via local limits

The random greedy algorithm for finding a maximal independent set in a graph constructs a maximal independent set by inspecting the graph's vertices in a random order, adding the current vertex to the independent set if it is not adjacent to any previously added vertex. In this paper, we present a general framework for computing the asymptotic density of the random greedy independent set for sequences of (possibly random) graphs by employing a notion of local convergence. We use this framework to give straightforward proofs for results on previously studied families of graphs, like paths and binomial random graphs, and to study new ones, like random trees and sparse random planar graphs. We conclude by analysing the random greedy algorithm more closely when the base graph is a tree.     

Thickness-Two Graphs Part Two: More New Nine-Critical Graphs,Independence Ratio,Cloned Planar Graphs,and Singly and Doubly Outerplanar Graphs

There are numerous means for measuring the closeness to planarity of a graph such as crossing number, splitting number, and a variety of thickness parameters. We focus on the classical concept of the thickness of a graph, and we add to earlier work in [4]. In particular, we offer new 9-critical thickness-two graphs on 17, 25, and 33 vertices, all of which provide counterexamples to a conjecture on independence ratio of Albertson; we investigate three classes of graphs, namely singly and doubly outerplanar graphs, and cloned planar graphs. We give a sharp upper bound for the largest chromatic number of the cloned planar graphs, and we give upper and lower bounds for the largest chromatic number of the former two classes.     

Asymptotic normality in random graphs with given vertex degrees

We consider random graphs with a given degree sequence and show, under weak technical conditions, asymptotic normality of the number of components isomorphic to a given tree, first for the random multigraph given by the configuration model and then, by a conditioning argument, for the simple uniform random graph with the given degree sequence. Such conditioning is standard for convergence in probability, but much less straightforward for convergence in distribution as here. The proof uses the method of moments, and is based on a new estimate of mixed cumulants in a case of weakly dependent variables. The result on small components is applied to give a new proof of a recent result by Barbour and Röllin on asymptotic normality of the size of the giant component in the random multigraph; moreover, we extend this to the random simple graph.     

Asymptotic for the cumulative distribution function of the degrees and homomorphism densities for random graphs sampled from a graphon

We give asymptotics for the cumulative distribution function (CDF) for degrees of large dense random graphs sampled from a graphon. The proof is based on precise asymptotics for binomial random variables. This result is a first step for giving a nonparametric test for identifying the degree function of a large random graph. Replacing the indicator function in the empirical CDF by a smoother function, we get general asymptotic results for functionals of homomorphism densities for partially labeled graphs. This general setting allows to recover recent results on asymptotics for homomorphism densities of sampled graphon.     

Hypohamiltonian Planar Cubic Graphs with Girth 5

A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4‐cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices.     

Graph Decomposition and Parity

Motivated by a recent extension of the zero‐one law by Kolaitis and Kopparty, we study the distribution of the number of copies of a fixed disconnected graph in the random graph . We use an idea of graph decompositions to give a sufficient condition for this distribution to tend to uniform modulo q. We determine the asymptotic distribution of all fixed two‐component graphs in for all q, and we give infinite families of many‐component graphs with a uniform asymptotic distribution for all q. We also prove a negative result that no recursive proof of the simplest form exists for a uniform asymptotic distribution for arbitrary graphs.     

Matching theory and Barnette's conjecture

Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity.As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. (1985) [14]. These allow us to check whether a graph we generated is a brace.     

A full characterization of invariant embeddability of unimodular planar graphs

When can a unimodular random planar graph be drawn in the Euclidean or the hyperbolic plane in a way that the distribution of the random drawing is isometry-invariant? This question was answered for one-ended unimodular graphs in Benjamini and Timar, using the fact that such graphs automatically have locally finite (simply connected) drawings into the plane. For the case of graphs with multiple ends the question was left open. We revisit Halin's graph theoretic characterization of graphs that have a locally finite embedding into the plane. Then we prove that such unimodular random graphs do have a locally finite invariant embedding into the Euclidean or the hyperbolic plane, depending on whether the graph is amenable or not.     

The Degree Profile in Some Classes of Random Graphs that Generalize Recursive Trees

We study the degree profile for a number of classes of random graphs that arise as generalizations of recursive trees, including random circuits and random recursive trees endowed with the power of choice. We investigate the distribution of the degrees of nodes that appear in various stages of the insertion process in each of these graph types. For these classes, we will see phase transitions in degrees depending on the stage—early stages are associated with normal distributions, intermediate stages are associated with the Poisson distribution and in the late stages the degrees become degenerate.     

Homomorphisms of 2-edge-colored graphs

In this paper, we study homomorphisms of 2-edge-colored graphs, that is graphs with edges colored with two colors. We consider various graph classes (outerplanar graphs, partial 2-trees, partial 3-trees, planar graphs) and the problem is to find, for each class, the smallest number of vertices of a 2-edge-colored graph H such that each graph of the considered class admits a homomorphism to H.     

一类RNA二级结构的计数

多核苷酸的二级结构可视为一类顶点标号平面图，通常通过枚举每类RNA二级结构图的各种子图来计算其递推公式。本文作者给出了限制端环长度的RNA二级结构的递推公式，并运用隐式估计法计算它的渐近值。     

Homomorphisms of 2-edge-colored graphs

In this paper, we study homomorphisms of 2-edge-colored graphs, that is graphs with edges colored with two colors. We consider various graph classes (outerplanar graphs, partial 2-trees, partial 3-trees, planar graphs) and the problem is to find, for each class, the smallest number of vertices of a 2-edge-colored graph H such that each graph of the considered class admits a homomorphism to H.     

Three small cubic graphs with interesting hamiltonian properties

We present here three graphs, which are the smallest known ones of their kind: a cubic three-connected planar nontraceable graph, a cubic three-connected planar graph which is not homogeneously traceable, and a cubic one-Hamiltonian graph which is not Hamiltonian connected.     

splitting number is NP-complete

We consider two graph invariants that are used as a measure of nonplanarity: the splitting number of a graph and the size of a maximum planar subgraph. The splitting number of a graph G is the smallest integer k⩾0, such that a planar graph can be obtained from G by k splitting operations. Such operation replaces a vertex v by two nonadjacent vertices v₁ and v₂, and attaches the neighbors of v either to v₁ or to v₂. We prove that the splitting number decision problem is NP-complete when restricted to cubic graphs. We obtain as a consequence that planar subgraph remains NP-complete when restricted to cubic graphs. Note that NP-completeness for cubic graphs implies NP-completeness for graphs not containing a subdivision of K₅ as a subgraph.     

Finite cubic graphs admitting a cyclic group of automorphism with at most three orbits on vertices

The theory of voltage graphs has become a standard tool in the study of graphs admitting a semiregular group of automorphisms. We introduce the notion of a cyclic generalised voltage graph to extend the scope of this theory to graphs admitting a cyclic group of automorphisms that may not be semiregular. We use this new tool to classify all cubic graphs admitting a cyclic group of automorphisms with at most three vertex-orbits and we characterise vertex-transitivity for each of these classes. In particular, we show that a cubic vertex-transitive graph admitting a cyclic group of automorphisms with at most three orbits on vertices either belongs to one of 5 infinite families or is isomorphic to the well-known Tutte–Coxeter graph.     

Triple Crossing Numbers of Graphs

We introduce the triple crossing number,a variation of the crossing number,of a graph,which is the minimal number of crossing points in all drawings of the graph with only triple crossings.It is defined to be zero for planar graphs,and to be infinite for non-planar graphs which do not admit a drawing with only triple crossings.In this paper,we determine the triple crossing numbers for all complete multipartite graphs which include all complete graphs.