To every finite metric space X, including all connected unweighted graphs with the minimum edge-distance metric, we attach an invariant that we call its blowup-polynomial $p_X(\{ n_x : x \in X \})$. This is obtained from the blowup $X[\mathbf {n}]$ – which contains $n_x$ copies of each point x – by computing the determinant of the distance matrix of $X[\mathbf {n}]$ and removing an exponential factor. We prove that as a function of the sizes $n_x$, $p_X(\mathbf {n})$ is a polynomial, is multi-affine, and is real-stable. This naturally associates a hitherto unstudied delta-matroid to each metric space X; we produce another novel delta-matroid for each tree, which interestingly does not generalize to all graphs. We next specialize to the case of $X = G$ a connected unweighted graph – so $p_G$ is “partially symmetric” in $\{ n_v : v \in V(G) \}$ – and show three further results: (a) We show that the polynomial $p_G$ is indeed a graph invariant, in that $p_G$ and its symmetries recover the graph G and its isometries, respectively. (b) We show that the univariate specialization $u_G(x) := p_G(x,\dots ,x)$ is a transform of the characteristic polynomial of the distance matrix $D_G$; this connects the blowup-polynomial of G to the well-studied “distance spectrum” of G. (c) We obtain a novel characterization of complete multipartite graphs, as precisely those for which the “homogenization at $-1$” of $p_G(\mathbf { n})$ is real-stable (equivalently, Lorentzian, or strongly/completely log-concave), if and only if the normalization of $p_G(-\mathbf { n})$ is strongly Rayleigh.

In this note, we bound the metric dimension of the circulant graphs $C_n(1,2,\ldots ,t)$. We shall prove that if $n=2tk+t$ and if t is odd, then $\dim (C_n(1,2,\ldots ,t))=t+1$, which confirms Conjecture 4.1.1 in Chau and Gosselin (2017, Opuscula Mathematica 37, 509–534). In Vetrík (2017, Canadian Mathematical Bulletin 60, 206–216; 2020, Discussiones Mathematicae. Graph Theory 40, 67–76), the author has shown that $\dim (C_n(1,2,\ldots ,t))\leq t+\left \lceil \frac {p}{2}\right \rceil $ for $n=2tk+t+p$, where $t\geq 4$ is even, $1\leq p\leq t+1$, and $k\geq 1$. Inspired by his work, we show that $\dim (C_n(1,2,\ldots ,t))\leq t+\left \lfloor \frac {p}{2}\right \rfloor $ for $n=2tk+t+p$, where $t\geq 5$ is odd, $2\leq p\leq t+1$, and $k\geq 2$.

Let G be a graph. Assume that to each vertex of a set of vertices $S\subseteq V(G)$ a robot is assigned. At each stage one robot can move to a neighbouring vertex. Then S is a mobile general position set of G if there exists a sequence of moves of the robots such that all the vertices of G are visited while maintaining the general position property at all times. The mobile general position number of G is the cardinality of a largest mobile general position set of G. We give bounds on the mobile general position number and determine exact values for certain common classes of graphs, including block graphs, rooted products, unicyclic graphs, Kneser graphs $K(n,2)$ and line graphs of complete graphs.

We introduce a broad class of multi-hooking networks, wherein multiple copies of a seed are hooked at each step at random locations, and the number of copies follows a predetermined building sequence of numbers. We analyze the degree profile in random multi-hooking networks by tracking two kinds of node degrees—the local average degree of a specific node over time and the global overall average degree in the graph. The former experiences phases and the latter is invariant with respect to the type of building sequence and is somewhat similar to the average degree in the initial seed. We also discuss the expected number of nodes of the smallest degree. Additionally, we study distances in the network through the lens of the average total path length, the average depth of a node, the eccentricity of a node, and the diameter of the graph.

We derive three critical exponents for Bernoulli site percolation on the uniform infinite planar triangulation (UIPT). First, we compute explicitly the probability that the root cluster is infinite. As a consequence, we show that the off-critical exponent for site percolation on the UIPT is $\beta = 1/2$. Then we establish an integral formula for the generating function of the number of vertices in the root cluster. We use this formula to prove that, at criticality, the probability that the root cluster has at least n vertices decays like $n^{-1/7}$. Finally, we also derive an expression for the law of the perimeter of the root cluster and use it to establish that, at criticality, the probability that the perimeter of the root cluster is equal to n decays like $n^{-4/3}$. Among these three exponents, only the last one was previously known. Our main tools are the so-called gasket decomposition of percolation clusters, generic properties of random Boltzmann maps, and analytic combinatorics.

We explore the tree limits recently defined by Elek and Tardos. In particular, we find tree limits for many classes of random trees. We give general theorems for three classes of conditional Galton–Watson trees and simply generated trees, for split trees and generalized split trees (as defined here), and for trees defined by a continuous-time branching process. These general results include, for example, random labelled trees, ordered trees, random recursive trees, preferential attachment trees, and binary search trees.

A graph is called radially maximal if it is not complete and the addition of any new edge decreases its radius. Harary and Thomassen [‘Anticritical graphs’, Math. Proc. Cambridge Philos. Soc.79(1) (1976), 11–18] proved that the radius r and diameter d of any radially maximal graph satisfy $r\le d\le 2r-2.$ Dutton et al. [‘Changing and unchanging of the radius of a graph’, Linear Algebra Appl.217 (1995), 67–82] rediscovered this result with a different proof and conjectured that the converse is true, that is, if r and d are positive integers satisfying $r\le d\le 2r-2,$ then there exists a radially maximal graph with radius r and diameter $d.$ We prove this conjecture and a little more.

The general position number of a connected graph is the cardinality of a largest set of vertices such that no three pairwise-distinct vertices from the set lie on a common shortest path. In this paper it is proved that the general position number is additive on the Cartesian product of two trees.

A well-known observation of Lovász is that if a hypergraph is not 2-colourable, then at least one pair of its edges intersect at a single vertex. In this short paper we consider the quantitative version of Lovász’s criterion. That is, we ask how many pairs of edges intersecting at a single vertex should belong to a non-2-colourable n-uniform hypergraph. Our main result is an exact answer to this question, which further characterizes all the extremal hypergraphs. The proof combines Bollobás’s two families theorem with Pluhar’s randomized colouring algorithm.

We consider a random graph model that was recently proposed as a model for complex networks by Krioukov et al. (2010). In this model, nodes are chosen randomly inside a disk in the hyperbolic plane and two nodes are connected if they are at most a certain hyperbolic distance from each other. It has previously been shown that this model has various properties associated with complex networks, including a power-law degree distribution and a strictly positive clustering coefficient. The model is specified using three parameters: the number of nodes N, which we think of as going to infinity, and $\alpha, \nu > 0$, which we think of as constant. Roughly speaking, $\alpha$ controls the power-law exponent of the degree sequence and $\nu$ the average degree. Earlier work of Kiwi and Mitsche (2015) has shown that, when $\alpha \lt 1$ (which corresponds to the exponent of the power law degree sequence being $\lt 3$), the diameter of the largest component is asymptotically almost surely (a.a.s.) at most polylogarithmic in N. Friedrich and Krohmer (2015) showed it was a.a.s. $\Omega(\log N)$ and improved the exponent of the polynomial in $\log N$ in the upper bound. Here we show the maximum diameter over all components is a.a.s. $O(\log N),$ thus giving a bound that is tight up to a multiplicative constant.

We investigate how the Minkowski sum of two polytopes affects their graph and, in particular, their diameter. We show that the diameter of the Minkowski sum is bounded below by the diameter of each summand and above by, roughly, the product between the diameter of one summand and the number of vertices of the other. We also prove that both bounds are sharp. In addition, we obtain a result on polytope decomposability. More precisely, given two polytopes $P$ and $Q$, we show that $P$ can be written as a Minkowski sum with a summand homothetic to $Q$ if and only if $P$ has the same number of vertices as its Minkowski sum with $Q$.

We propose two distance-based topological indices (level index and Gini index) as measures of disparity within a single tree and within tree classes. The level index and the Gini index of a single tree are measures of balance within the tree. On the other hand, the Gini index for a class of random trees can be used as a comparative measure of balance between tree classes. We establish a general expression for the level index of a tree. We compute the Gini index for two random classes of caterpillar trees and see that a random multinomial model of trees with finite height has a countable number of limits in [0, ⅓], whereas a model with independent level numbers fills the spectrum (0, ⅓].

All finite simple self 2-distance graphs with no square, diamond, or triangles with a common vertex as subgraph are determined. Utilizing these results, it is shown that there is no cubic self 2-distance graph.

Abstract. A subset $W$ of the vertex set of a graph $G$ is called a resolving set of $G$ if for every pair of distinct vertices $u,\,v$, of $G$, there is $w\,\in \,W$ such that the distance of $w$ and $u$ is different from the distance of $w$ and $v$. The cardinality of a smallest resolving set is called the metric dimension of $G$, denoted by $\dim\left( G \right)$. The circulant graph ${{C}_{n}}\left( 1,\,2,\,.\,.\,.\,,\,t \right)$ consists of the vertices ${{v}_{0}},\,{{v}_{1\,}},\,.\,.\,.\,,{{v}_{n\,-\,1}}$ and the edges ${{v}_{i}}{{v}_{i\,+\,j}}$, where $0\,\le \,i\,\le \,n\,-\,1,1\,\le \,j\,\le \,t\,\left( 2\,\le \,t\,\le \,\left\lfloor \frac{n}{2} \right\rfloor \right)$, the indices are taken modulo $n$. Grigorious, Manuel, Miller, Rajan, and Stephen proved that $\dim\left( {{C}_{n}}\left( 1,\,2,\,.\,.\,.\,,\,t \right) \right)\,\ge \,t\,+\,1$ for $t\,<\,\left\lfloor \frac{n}{2} \right\rfloor ,\,n\,\ge \,3$, and they presented a conjecture saying that $\dim\left( {{C}_{n}}\left( 1,\,2,\,.\,.\,.\,,\,t \right) \right)\,=\,t\,+\,p\,-\,1$ for $n\,=\,2tk\,+\,t\,+\,p$, where $3\,\le \,p\,\le \,t\,+\,1$. We disprove both statements. We show that if $t\,\ge \,4$ is even, there exists an infinite set of values of $n$ such that $\dim\left( {{C}_{n}}\left( 1,\,2,\,.\,.\,.\,,t \right) \right)\,=\,t$. We also prove that $\dim\left( {{C}_{n}}\left( 1,\,2,\,.\,.\,.\,,\,t \right) \right)\,\le \,t\,+\,\frac{p}{2}$ for $n\,=\,2tk\,+\,t\,+\,p$, where $t$ and $p$ are even, $t\,\ge \,4,\,2\,\le \,p\,\le \,t$, and $k\,\ge \,1$.

Let $G$ be a connected graph with vertex set $V\left( G \right)$.The degree Kirchhoff index of $G$ is defined as ${{S}^{\prime }}\left( G \right)\,=\,\sum{_{\left\{ u,v \right\}\,\subseteq \,V\left( G \right)}d\left( u \right)d\left( v \right)R\left( u,\,v \right)}$, where $d\left( u \right)$ is the degree of vertex $u$, and $R\left( u,\,v \right)$ denotes the resistance distance between vertices $u$ and $v$. In this paper, we characterize the graphs having maximum and minimum degree Kirchhoff index among all $n$-vertex bicyclic graphs with exactly two cycles.

Let $R$ be an associative ring with identity. First we prove some results about zero-divisor graphs of reversible rings. Then we study the zero-divisors of the skew power series ring $R\left[\!\left[ x;\,\alpha \right]\!\right]$, whenever $R$ is reversible $\alpha$-compatible. Moreover, we compare the diameter and girth of the zero-divisor graphs of $\Gamma \left( R \right),\,\Gamma \left( R[x;\,\alpha ,\,\delta ] \right)$, and $\Gamma \left( R\left[\!\left[ x;\,\alpha \right]\!\right] \right)$, when $R$ is reversible and $\left( \alpha ,\,\delta \right)$-compatible.

Motivated by the local theory of Banach spaces, we introduce a notion of finite representability for metric spaces. This allows us to develop a new technique for comparing the generalised roundness of metric spaces. We illustrate this technique by applying it to Banach spaces and metric trees. In the realm of Banach spaces we obtain results such as the following: (1) if ${\mathcal{U}}$ is any ultrafilter and $X$ is any Banach space, then the second dual $X^{\ast \ast }$ and the ultrapower $(X)_{{\mathcal{U}}}$ have the same generalised roundness as $X$, and (2) no Banach space of positive generalised roundness is uniformly homeomorphic to $c_{0}$ or $\ell _{p}$, $2<p<\infty$. For metric trees, we give the first examples of metric trees of generalised roundness one that have finite diameter. In addition, we show that metric trees of generalised roundness one possess special Euclidean embedding properties that distinguish them from all other metric trees.

The unitary Cayley graph of a ring $R$, denoted $\Gamma \left( R \right)$, is the simple graph defined on all elements of $R$, and where two vertices $x$ and $y$ are adjacent if and only if $x\,-\,y$ is a unit in $R$. The largest distance between all pairs of vertices of a graph $G$ is called the diameter of $G$ and is denoted by $\text{diam}\left( G \right)$. It is proved that for each integer $n\,\ge \,1$, there exists a ring $R$ such that $\text{diam}\left( \Gamma \left( R \right) \right)=n$. We also show that $\text{diam}\left( \Gamma \left( R \right) \right)\in \left\{ 1,2,3,\infty \right\}$ for a ring $R$ with ${R}/{J\left( R \right)}\;$ self-injective and classify all those rings with $\text{diam}\left( \Gamma \left( R \right) \right)\,=\,1,\,2,\,3$, and $\infty$, respectively.

In this paper we study random Apollonian networks (RANs) and evolving Apollonian networks (EANs), in d dimensions for any d≥2, i.e. dynamically evolving random d-dimensional simplices, looked at as graphs inside an initial d-dimensional simplex. We determine the limiting degree distribution in RANs and show that it follows a power-law tail with exponent τ=(2d-1)/(d-1). We further show that the degree distribution in EANs converges to the same degree distribution if the simplex-occupation parameter in the nth step of the dynamics tends to 0 but is not summable in n. This result gives a rigorous proof for the conjecture of Zhang et al. (2006) that EANs tend to exhibit similar behaviour as RANs once the occupation parameter tends to 0. We also determine the asymptotic behaviour of the shortest paths in RANs and EANs for any d≥2. For RANs we show that the shortest path between two vertices chosen u.a.r. (typical distance), the flooding time of a vertex chosen uniformly at random, and the diameter of the graph after n steps all scale as a constant multiplied by log n. We determine the constants for all three cases and prove a central limit theorem for the typical distances. We prove a similar central limit theorem for typical distances in EANs.

For a fixed $K\,\gg \,1$ and $n\,\in \,\mathbb{N}$, $n\,\gg \,1$ we study metric spaces which admit embeddings with distortion $\le \,K$ into each $n$-dimensional Banach space. Classical examples include spaces embeddable into log $n$-dimensional Euclidean spaces, and equilateral spaces.

We prove that good embeddability properties are preserved under the operation of metric composition of metric spaces. In particular, we prove that $n$-point ultrametrics can be embedded with uniformly bounded distortions into arbitrary Banach spaces of dimension $\log \,n$.

The main result of the paper is a new example of a family of finite metric spaces which are not metric compositions of classical examples and which do embed with uniformly bounded distortion into any Banach space of dimension $n$. This partially answers a question of G. Schechtman.