In this paper we prove that random d-regular graphs with d ≥ 3 have traffic congestion of the order O(n logd−13 n) where n is the number of nodes and geodesic routing is used. We also show that these graphs are not asymptotically δ-hyperbolic for any non-negative δ almost surely as n → ∞.
We show using non-intersecting paths, that a random rhombus tiling of a hexagon, or a boxed planar partition, is described by a determinantal point process given by an extended Hahn kernel.
This paper determines all nonsingular unicyclic mixed graphs on at least nine vertices with at most three Laplacian eigenvalues greater than two.
Nordhaus-Gaddum results for weakly convex domination number of a graph G are studied.
Two decades ago, resistance distance was introduced to characterize “chemical distance” in (molecular) graphs. In this paper, we consider three resistance distance-based graph invariants, namely, the Kirchhoff index, the additive degree-Kirchhoff index, and the multiplicative degree-Kirchhoff index. Some Nordhaus-Gaddum-type results for these three molecular structure descriptors are obtained. In addition, a relation between these Kirchhoffian indices is established.