This paper describes local configurations of some planar triangulations. A Gauss-Bonnet-like formula holds locally for a kind of discrete “curvature” associated to such triangulations.

We approach the problem of defining curvature on a graph by attempting to attach a ‘best-fit polytope’ to each vertex, or more precisely what we refer to as a configured star. How this should be done depends upon the global structure of the graph which is reflected in its geometric spectrum. Mean curvature is the most natural curvature that arises in this context and corresponds to local liftings of the graph into a suitable Euclidean space. We discuss some examples.

If $L$ is the combinatorial Laplacian of a graph, $exp(-Lt)$ converges to a matrix with identical coefficients. The speed of convergence is measured by the maximal entropy distance. When the graph is the sum of a large number of components, a cut-off phenomenon may occur: before some instant the distance to equilibrium tends to infinity; after that instant it tends to $0$. A sufficient condition for cut-off is given, and the cut-off instant is expressed as a function of the gap and eigenvectors of components....

The paper studies the domatic numbers and the total domatic numbers of graphs having cut-vertices.

The cutwidth is an important graph-invariant in circuit layout designs. The cutwidth of a graph G is the minimum value of the maximum number of overlap edges when G is embedded into a line. A caterpillar is a tree which yields a path when all its leaves are removed. An iterated caterpillar is a tree which yields a caterpillar when all its leaves are removed. In this paper we present an exact formula for the cutwidth of the iterated caterpillars.

We prove that the cutwidth of the r-dimensional mesh of d-ary trees is of order $\Theta \left(d^{(r-1)n+1}\right)$, which improves and generalizes previous results.

We study two topological properties of the 5-ary $n$-cube $Q_n^5$. Given two arbitrary distinct nodes $x$ and $y$ in $Q_n^5$, we prove that there exists an $x$-$y$ path of every length ranging from $2n$ to $5^n-1$, where $n\ge 2$. Based on this result, we prove that $Q_n^5$ is 5-edge-pancyclic by showing that every edge in $Q_n^5$ lies on a cycle of every length ranging from $5$ to $5^n$.

We study two topological properties of the 5-ary n-cube $Q_n^5$. Given two arbitrary distinct nodes x and y in $Q_n^5$, we prove that there exists an x-y path of every length ranging from 2n to 5n - 1, where n ≥ 2. Based on this result, we prove that $Q_n^5$ is 5-edge-pancyclic by showing that every edge in $Q_n^5$ lies on a cycle of every length ranging from 5 to 5n.

In this paper, we study the existence of cycle double covers for infinite planar graphs. We show that every infinite locally finite bridgeless k-indivisible graph with a 2-basis admits a cycle double cover.

In the past years, many properties of the largest connected components of critical percolation on the high-dimensional torus, such as their sizes and diameter, have been established. The order of magnitude of these quantities equals the one for percolation on the complete graph or Erdős–Rényi random graph, raising the question whether the scaling limits of the largest connected components, as identified by Aldous (1997), are also equal. In this paper, we investigate the cycle structureof the largest...

Let T be a hamiltonian bipartite tournament with n vertices, γ a hamiltonian directed cycle of T, and k an even number. In this paper, the following question is studied: What is the maximum intersection with γ of a directed cycle of length k? It is proved that for an even k in the range 4 ≤ k ≤ [(n+4)/2], there exists a directed cycle $C_{h\left(k\right)}$ of length h(k), h(k) ∈ k,k-2 with $|A\left(C_{h\left(k\right)}\right)\cap A\left(\gamma \right)|\ge h\left(k\right)-3$ and the result is best possible. In a forthcoming paper the case of directed cycles of length k, k even and k < [(n+4)/2]...

Let T be a hamiltonian bipartite tournament with n vertices, γ a hamiltonian directed cycle of T, and k an even number. In this paper the following question is studied: What is the maximum intersection with γ of a directed cycle of length k contained in T[V(γ)]? It is proved that for an even k in the range (n+6)/2 ≤ k ≤ n-2, there exists a directed cycle $C_{h\left(k\right)}$ of length h(k), h(k) ∈ k,k-2 with $|A\left(C_{h\left(k\right)}\right)\cap A\left(\gamma \right)|\ge h\left(k\right)-4$ and the result is best possible. In a previous paper a similar result for 4 ≤ k ≤ (n+4)/2 was proved.