Abstract
We introduce a natural notion of mean (or average) distance in the context of compact metric graphs, and study its relation to geometric properties of the graph. We show that it exhibits a striking number of parallels to the reciprocal of the spectral gap of the graph Laplacian with standard vertex conditions: it is maximised among all graphs of fixed length by the path graph (interval), or by the loop in the restricted class of doubly connected graphs, and it is minimised among all graphs of fixed length and number of edges by the equilateral flower graph. We also establish bounds for the correctly scaled product of the spectral gap and the square of the mean distance which depend only on combinatorial, and not metric, features of the graph. This raises the open question whether this product admits absolute upper and lower bounds valid on all compact metric graphs.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Our aim is to study the notion of mean, or average, distance on metric graphs. Metric graphs have been studied in mathematics for over 40 years, at least since [21]. They consist of collections of intervals whose endpoints are suitably identified to create a connected network structure, and display many features which mirror those of combinatorial, i.e., discrete, graphs; but at times they exhibit more complex behaviour reminiscent of (higher dimensional) Euclidean domains or manifolds, thanks to their continuous metric structure. In particular, it is possible to define differential operators such as Laplacians on metric graphs, see [2, 19, 27]; in the last decade or so, the interplay between the geometry of the graph and the Laplacian spectrum has received considerable attention, see, e.g., [4, 19] and the references therein.
At the same time, mean distance does not previously seem to have been considered on metric graphs. On combinatorial graphs a corresponding notion was already actively investigated in the late 20th Century; in fact, it seems difficult to determine a precise birthdate of the theory, as there the mean distance is, up to a normalising factor, simply the \(\ell ^1\)-norm of the distance matrix. According to [11], this and related quantities were first studied by Harary [16] and Ore [30] as graph-based sociometric quantities; while in [15] the authors trace the origin of this notion back to an even earlier study in quantum chemistry [34]. Subsequently, mean distance has grown to be an important quantity in combinatorial geometry ever since [9, 11, 31], and it has also played an important role in inverse combinatorial problems [7]. The interplay of the \(\ell ^1\)-norm of the distance matrix with the geometry and potential theory of graphs was investigated more recently, in [33]; in particular, a new notion of curvature is suggested that, in particular, agrees with the mean distance function whenever the latter is vertex-wise constant. As a further development that is closer to our main interest in this article, let us mention that one topic of interest since at least the 1970 s has been to study the relationship between the combinatorial mean distance and the eigenvalues of the discrete graph Laplacian, see, e.g., [15, 24], and see below.
Our goals here are essentially twofold. First, we will develop fundamental geometric bounds for the mean distance of a (compact) metric graph: on the one hand, it seems that the mean distance is another, and arguably quite fine, quantity that measures how well connected the graph is, just like the Cheeger constant and the vertex connectivity do (as our estimates will show). On the other, in practice it is somewhat difficult to compute, thus providing a need for such estimates. What we will show (see Theorem 3.2) is that the mean distance is maximised among all graphs of given total length when the graph is a path, i.e. interval (or a loop among doubly connected graphs); and maximised among all graphs of given total length and number of edges when the graph is a so-called equilateral flower graph.
These results have strong parallels with both the behaviour of mean distance on combinatorial graphs, and the spectral gap \(\mu _2\) of the standard Laplacian on metric graphs. On combinatorial graphs it has been known for decades that mean distance is minimised on complete graphs [11, Theorem 2.3] and maximised on path graphs [9, Corollary 1.3], or on cycles among doubly-connected graphs [31, Theorem 6]. This in turn mirrors inversely what is known regarding the spectral gap of the combinatorial Laplacian, that is, the algebraic connectivity: it is famously minimised by path graphs and maximised by complete graphs, see [12]. This strong inverse relationship in the discrete world has been studied: for example, in [24], quite sophisticated estimates on the lowest positive eigenvalue of the discrete Laplacian are derived in terms of the mean distance in combination with the size of the graph and its maximal degree (see also [25]); as a more recent contribution to this field we mention [32].
Regarding the spectral gap \(\mu _2\) of the standard Laplacian on metric graphs, it is known that \(\mu _2\) is minimised on the path graph [29, Théorème 3.1], or the cycle among doubly-connected graphs [1, Theorem 2.1], and maximised, under a constraint on the number of edges, among others by the equilateral flower graph [17, Theorem 4.2]. Thus, in particular, the strong correspondence in the discrete setting also seems to hold in the metric one.
Our second goal is thus to investigate precisely the relationship between the mean distance \(\rho \) and the spectral gap \(\mu _2\). We will provide several upper and lower bounds on the product \(\mu _2 \rho ^2\) (scaled in such a way as to be independent of the total length of the graph), see Theorem 3.5 and Corollaries 3.3 and 3.6, which depend only on the number of edges of the graph and/or its (first) Betti number (number of independent cycles); in the case of trees one can find an absolute constant as an upper bound, \(\pi ^2\). These bounds in general do not appear to be optimal, and the natural question arises as to whether the product \(\mu _2 \rho ^2\) admits absolute upper and lower bounds valid for any compact graph, which we leave as an open problem (Open Problem 3.4).
This paper is structured as follows. In Sect. 2 we will introduce our general framework and provide a definition of mean distance \(\rho \) on a metric graph. All our main results – geometric estimates for \(\rho \) as well as bounds linking \(\rho \) and the spectral gap of the standard Laplacian – are collected in Sect. 3. In addition to Theorem 3.2, we also include a statement on the relationship between \(\rho \) and the diameter of the graph, Theorem 3.1.
The proofs, which rely on various techniques, are spread throughout the remaining sections: first, we give several explicit examples in Sect. 4, namely star graphs (including intervals, see Example 4.1), a special type of “firework graph” which shows that mean distance can be arbitrarily close to diameter (Example 4.2), and flower graphs (including loops, Example 4.3), whose analysis is essential for one of the main geometric bounds in Theorem 3.2.
Then, in Sect. 5, we study surgery principles for mean distance, which will be used to prove Theorem 3.2. These principles are inspired by analogous ones developed in recent years for spectral and torsional quantities on metric graphs (see in particular [4]), but, curiously, such surgical methods also play a role in some of the early combinatorial works; we refer to [15, Sections 5.3 and 5.4] for an overview of results in this direction. However, while there are parallels to surgery for spectral quantities, in concrete terms and in the details our results and proofs are quite different as there is currently no known variational characterisation of mean distance (cf. Remark 7.2); instead, one needs to analyse more directly the effect of altering a graph on its distance function. There are also notable differences in some results; attaching a so-called pendant edge to a graph has an indeterminate effect on \(\rho \), despite always lowering \(\mu _2\) (see Proposition 5.3).
In Sect. 6 we will provide the proof that among doubly connected graphs of given length the mean distance is maximised on the loop, the last remaining part of Theorem 3.2. Here, somewhat surprisingly, it is natural to use a symmetrisation argument based on the coarea formula and inspired by the approach of Friedlander for minimising standard Laplacian eigenvalues [13]; however, here again, the actual technical nature of the proof is very different as mean distance is not characterised as a minimising quantity.
Finally, in Sect. 7, we give a proof of the lower bound in Theorem 3.5 on the product of \(\rho \) and the spectral gap using variational methods for the latter.
Before continuing, we mention the very recent paper [14], which we became aware of shortly before submitting the present paper: seemingly unaware of the theory of metric graphs, the authors of [14] introduce a notion of mean distance that agrees with ours and discuss the complexity of its computing.
We note that the notion of mean distance is in fact a natural one in any metric measure space of finite diameter and volume. In the spirit of [8], it would be natural to introduce the mean distance of further, possibly more general metric measure spaces: an interesting estimate on the lowest positive eigenvalue of the Laplace–Beltrami operator of a compact Riemannian manifold was already announced, but not proved, in [23]. More modestly, one could try and extend the scope of our results to metric graphs of finite total length but an infinite number of edges. Since many of our methods are most natural in the compact case of finitely many edges, and tailored to graphs, to reduce technical complications and keep the work self-contained we will restrict to this case and not consider such possible generalisations here.
2 Notation and Assumptions
Throughout, we consider metric graphs \(\mathcal {G}:=(\textsf{V},\textsf{E},\ell )\) consisting of a finite number \(V:=\#\textsf{V}\) of vertices and \(E:=\#\textsf{E}\) of edges; we denote by \(\beta = E - V + 1\) the (first) Betti number of \(\mathcal {G}\), the number of independent cycles it contains.
Unlike in the case of combinatorial graphs, we create a metric structure by associating each edge e with a real interval \((0,\ell _e)\) of length \(\ell _e>0\), which we may regard as a parametrisation of the edge. While this parametrisation implies an orientation of each edge, all quantities considered will be independent of these orientations. In particular, the total length \(|\mathcal {G}|\) of \(\mathcal {G}\) is, by definition
A distance on \(\mathcal {G}\) is introduced by first considering the Euclidean distance on each metric edge and then extending it to a (pseudo-)metric \({{\,\textrm{dist}\,}}\) on \(\mathcal {G}\) by the usual shortest-path construction (we will also sometimes write \({{\,\textrm{dist}\,}}_\mathcal {G}\) in those cases where it becomes necessary to specify the graph).
To avoid trivialities, we will always assume without further comment that the metric graph is connected. A metric graph then canonically becomes a metric measure space \((\mathcal {G},{{\,\textrm{dist}\,}},{\mathrm d}x)\) upon endowing each metric edge with the 1-dimensional Lebesgue measure \({\mathrm d}x\). This metric measure structure immediately induces the spaces \(C(\mathcal {G})\) and \(L^2(\mathcal {G})\) of continuous and square integrable functions over \(\mathcal {G}\), respectively. We will also need the Sobolev space
As is well known, all these spaces are, up to a canonical identification, independent of the choice of parametrisation of the edges, and in particular of the corresponding orientation.
Our assumptions, namely that there are only finitely many edges each of finite length, imply that as a metric space \(\mathcal {G}\) is compact and in particular has finite diameter. In this case, as is standard, we will refer to \(\mathcal {G}\) as a compact metric graph. (We refer to [2, 26] for a more detailed introduction to the notion of metric graphs.)
Our compactness assumption on \(\mathcal {G}\) implies that the following natural notion of mean distance is well defined.
Definition 2.1
The mean distance function on \(\mathcal {G}\) is the function \(\rho _\mathcal {G}: \mathcal {G}\rightarrow \mathbb {R}\) defined by
we will call \(\rho _\mathcal {G}(x)\) the mean distance from x on \(\mathcal {G}\). The mean distance on \(\mathcal {G}\) is then defined as the mean value of \(\rho _\mathcal {G}\),
(As mentioned in the introduction, this concept has been studied for decades in graph theory, where it is commonly referred to as either “mean distance” or “average distance” in the literature; we will always use the former.)
It would be possible to extend this definition to graphs of finite total length but an infinite number of edges; however, as many of our techniques are naturally adapted to the compact case, and to keep the exposition more simple, we will not do so.
Beyond estimates on the mean distance of a graph \(\mathcal {G}\) in terms of quantities such as the total length, the number of edges and the Betti number of the graph, we will be particularly interested in the interplay between the mean distance and the spectrum of the corresponding Laplacian \(-\Delta _\mathcal {G}\) with standard vertex conditions, in particular as regards its spectral gap (see, e.g., [2, 4]). For our purposes the following characterisation will suffice.
Definition 2.2
The spectral gap of \(\mathcal {G}\) is
This quantity is known to be strictly positive since \(\mathcal {G}\) is compact and connected.
3 Main Results
We start with a simple observation on the relationship between \(\rho (\mathcal {G})\) and the diameter \({{\,\textrm{diam}\,}}(\mathcal {G})\); completely analogous results have been known to hold for discrete graphs since the 1970 s (see [9]). While the (strict) inequality is rather obvious, the key point is that the inequality is sharp nonetheless.
Theorem 3.1
Let \(\mathcal {G}\) be a compact metric graph of diameter \({{\,\textrm{diam}\,}}(\mathcal {G}) > 0\). Then
Moreover, there exists a sequence of graphs \(\mathcal {G}_n\) for which \(\frac{\rho (\mathcal {G}_n)}{{{\,\textrm{diam}\,}}(\mathcal {G}_n)} \rightarrow 1\) as \(n \rightarrow \infty \).
Proof
For (3.1), by definition of \(\rho \) and Cauchy–Schwarz,
the strict inequality being due to the linear independence of \({{\,\textrm{dist}\,}}\) and \({\textbf{1}}\). For a sequence of graphs \(\mathcal {G}_n\) for which \(\frac{\rho (\mathcal {G}_n)}{{{\,\textrm{diam}\,}}(\mathcal {G}_n)} \rightarrow 1\) we will consider “firework” graphs similar to the (discrete) ones used in [9] to prove a corresponding assertion for the discrete mean distance; these will be given in Example 4.2 below. \(\square \)
We now turn to our first main result, which consists of fundamental upper and lower bounds on \(\rho \) in terms only of the length, and the length and number of edges, of the graph \(\mathcal {G}\), respectively. As discussed in the introduction, these closely mirror those for the (inverse of the) first nontrivial standard Laplacian eigenvalue \(\mu _2(\mathcal {G})\): this eigenvalue admits a lower bound depending only on length [29, Théorème 3.1], with equality for path graphs (i.e. intervals); there is an improved lower bound for doubly connected graphs depending only on length and with equality for loops [1, Theorem 2.1]. There is a corresponding upper bound based only on length and number of edges, with equality for equilateral flower graphs, among others [17, Theorem 4.2]. Our result is:
Theorem 3.2
Let \(\mathcal {G}\) be a compact metric graph with total length \(|\mathcal {G}|=L>0\) and E edges. Then
with equality in the lower bound if and only if \(\mathcal {G}\) is an equilateral flower graph, and equality in the upper bound if and only if \(\mathcal {G}\) is a path graph (i.e., interval). If \(\mathcal {G}\) is doubly connected, then the upper bound may be improved to
with equality if and only if \(\mathcal {G}\) is a loop.
For (3.3) we will use surgery methods, which are the subject of Sect. 5; the proof of (3.3) is given at the end of that section. To prove (3.4) we will use a symmetrisation-type argument based on the coarea formula (which, curiously, does not seem to work in the base case), see Sect. 6.
Since \(\rho \) and \(\mu _2\) satisfy compatible bounds, we can also find two-sided bounds for the scale invariant quantity \(\mu _2(\mathcal {G}) \rho (\mathcal {G})^2\):
Corollary 3.3
Let \(\mathcal {G}\) be a compact metric graph with E edges and first Betti number \(\beta \ge 0\). Then
The fact that the respective minimisers and maximisers are in perfect correspondence, and more generally that the two quantities behave so analogously, suggests that there may actually be absolute upper and lower bounds, i.e., absolute constants independent of every graph which control \(\mu _2(\mathcal {G}) \rho (\mathcal {G})^2\) from above and below. At least for trees, (3.5) gives an absolute upper bound on this quantity (namely \(\min \{\frac{\pi ^2 E^2}{9}, \pi ^2 \}\)), which is sharp for path graphs I, where \(\mu _2(I)\rho (I)^2 = \frac{\pi ^2}{9}\). However, a direct computation using the values obtained in Sect. 4 shows that both for equilateral flowers and stars the product \(\mu _2\rho ^2\) is monotonically increasing and approaches \(\frac{\pi ^2}{4}\) as \(E\rightarrow \infty \).
We note that there is a certain parallel between the mean distance of a metric graph and (upon imposing a Dirichlet condition on at least one vertex) its torsional rigidity, as the latter is known, too, to be maximised precisely by path graphs and minimised precisely by equilateral flowers, see [28, Section 4]: this behaviour is precisely opposite to that of the lowest positive Laplacian eigenvalue, so it seems natural to pose the following, once appropriate scaling is accounted for.
Open Problem 3.4 Do there exist absolute constants \(C,c>0\) such that
for all compact graphs \(\mathcal {G}\)?
Indeed, the conjectured lower bound recalls the celebrated Kohler-Jobin inequality, which asserts that, in \(\mathbb {R}^d\), the normalised quantity \(\lambda _1(\Omega ) \tau (\Omega )^\frac{2}{d+2}\) (with \(\lambda _1\) the first Dirichlet Laplacian eigenvalue and \(\tau \) the torsional rigidity of \(\Omega \)) is minimised when \(\Omega \) is a ball (see [18] or, e.g., [5, 6] for more recent results in the area, as well as [28, Theorem 5.8] for the metric graph case). This, as well as our examples in Sect. 4, provide some weak evidence suggesting that the path graph might actually minimise \(\mu _2\rho ^2\), which, if true, would result in an optimal value of \(c=\frac{\pi ^2}{9}\).
Proof of Corollary 3.3
For the lower bound combine the lower bound in (3.3) with Nicaise’ inequality [29, Théorème 3.1]. For the first upper bound use the upper bound in (3.3) and [17, Theorem 4.2], for the second combine \(\rho (\mathcal {G}) \le {{\,\textrm{diam}\,}}(\mathcal {G})\) (cf. Theorem 3.1) with [10, Theorem 5.2]. \(\square \)
We can give an alternative lower bound on \(\rho \) involving the total length and \(\mu _2\), which in combination with the lower bound in Theorem 3.2 leads to an alternative to the lower bound in Corollary 3.3:
Theorem 3.5
Let \(\mathcal {G}\) be a compact metric graph with total length \(|\mathcal {G}| = L>0\). Then
Corollary 3.6
Let \(\mathcal {G}\) be a compact metric graph. Then
While still unlikely to be optimal, this is generally better than the lower bound in Corollary 3.3; as \(E \rightarrow \infty \) it behaves like \(\frac{1}{2E}\) rather than \(\frac{\pi ^2}{4E^2}\). In fact, the lower bound in Corollary 3.6 is seen to be larger whenever \(\frac{\pi ^2}{4E^2}(2E-1) < 1\), that is, \(4E^2 - 2\pi ^2 E + \pi ^2 > 0\), which holds for all \(E \ge 5\).
The proof of Theorem 3.5 is based on a suitable eigenvalue comparison argument, which involves linking the first eigenvalue of an auxiliary problem with a Dirichlet condition at a well-chosen vertex on the one hand, and a related distance function on the other, and is given in Sect. 7.
4 Examples
Here we will collect some examples where one can determine \(\rho \) explicitly: equilateral star graphs (including path graphs, i.e. intervals, as a special case), the “firework graphs” that will be used to complete the proof of Theorem 3.1, and equilateral flowers (including on one edge, i.e. loops). For purposes of legibility, we will generally use m and n to denote the number of edges and vertices, respectively, of our example graphs.
Example 4.1
(Star graph) For a given \(m \ge 1\) and \(L > 0\), consider \(S_m\) an equilateral star graph, that is, a graph with m edges of equal length \(\ell := \frac{L}{m}\) (and thus total length L) and \(m+1\) vertices, one of degree m (the “central vertex”) and all others of degree 1. To calculate \(\rho \), we identify each of the m identical edges with an interval of the form \([0,\frac{L}{m}]\), where 0 corresponds to the central vertex. Then, for any \(x \in S_m\),
note that this includes the special case of an interval I (\(m=1\), with the interval parametrised as [0, L]), where
Integrating \(\rho _{S_m}\) over all \(x \in [0,\frac{L}{m}]\) (and using the symmetry of the graph) yields
Let us consider the behaviour of the formula as a function of m. If \(m=1\) or \(m=2\), then \(\rho (S_m)=\frac{L}{3}\), which is exactly the value of \(\rho \) on an interval (note that stars on one and two edges are both path graphs).
Now fix L, then since the function \(x \mapsto \frac{L}{x^2}(x-\frac{2}{3})\), \(x > 0\), attains its maximum at \(x=\frac{4}{3}\) (and the same value at \(x=1\) and \(x=2\)), and is monotonically decreasing for \(x > \frac{4}{3}\), the maximum in m is attained at \(m=1,2\), and \(\rho (S_m)\) is a decreasing function of \(m \ge 1\). We observe that \(\rho (S_m) \rightarrow 0\) as \(m \rightarrow \infty \).
If instead we fix the length of each edge \(\ell =\frac{L}{m}\) (and vary m), then
as \(m \rightarrow \infty \).
We next consider a class of graphs built around stars, which include the sequence \(\mathcal {G}_n\) referred to in Theorem 3.1, for which \(\frac{\rho (\mathcal {G}_n)}{{{\,\textrm{diam}\,}}(\mathcal {G}_n)} \rightarrow 1\).
Example 4.2
(Firework graph) Here we will construct a four-parameter family of graphs, which for simplicity we will simply call \(\mathcal {G}\), as follows. We start with an equilateral star on \(m \ge 1\) edges, each of length \(J>0\), and then attach, at each of the m degree one vertices, a copy of another star \(*\) with n edges of equal length j; see Fig. 1. In particular, \(|\mathcal {G}|=mJ+mnj\), and \({{\,\textrm{diam}\,}}(\mathcal {G}) = 2J + 2j\).
We will show that, for the correct choice of m, n, J, j, \(\rho (\mathcal {G})\) can be made arbitrarily close to \({{\,\textrm{diam}\,}}(\mathcal {G})\) in the sense of Theorem 3.1; for this we merely need to estimate \(\rho (\mathcal {G})\) from below.
First, it is obvious that, for any \(x \in \mathcal {G}\) in any copy of \(*\),
Indeed, we may estimate \({{\,\textrm{dist}\,}}(x,y)\) from below by 2J for each y in each of the other \(m-1\) copies of \(*\); this can then be integrated over all such copies, each of which has total length nj. This then leads to
and thus (cf. (3.1))
Fixing m and J, we consider any sequence of such graphs for which \(j \rightarrow 0\) but simultaneously \(nj \rightarrow \infty \), then \(\frac{n^2j^2}{(J + nj)^2} \rightarrow 1\) and \({{\,\textrm{diam}\,}}(\mathcal {G}) \rightarrow 2J\). We can thus, given any \(\varepsilon >0\), find such a firework graph \(\mathcal {G}_{m,\varepsilon }\) for which \(2J< {{\,\textrm{diam}\,}}(\mathcal {G}_{m,\varepsilon }) < 2J + \varepsilon \) and
From this we can extract a sequence of graphs satisfying the conclusion of Theorem 3.1.
For our third example we consider the flower graphs which will play a role in the lower bound in Theorem 3.2. We will calculate mean distance only in the case of equilateral flowers, but Lemma 4.4 below gives a comparison with the non-equilateral case.
Example 4.3
(Flower graph) Given \(m \ge 1\) and \(L > 0\), take \(F_m\) to be the flower graph consisting of m edges of length \(\ell = \frac{L}{m}\) each, all glued at both ends at a common central vertex; that is, \(F_m\) has exactly one vertex, of degree 2m.
We start by noting the following formula for the integral of the distance function \({{\,\textrm{dist}\,}}(x,y)\) over a circle \(\mathcal {C}\) (of length \(\frac{L}{m}\)), i.e., when both x and y are taken from the same petal, which can be obtained by a direct calculation: parametrising the loop by \([-\frac{L}{2m},\frac{L}{2m}]\), with \(x \simeq 0\) and the points \(\frac{L}{2\,m}\) and \(-\frac{L}{2\,m}\), identified in \(\mathcal {C}\), representing the antipodal point to x, we have
This is, in particular, independent of x and y; and thus, for all \(x \in {\mathcal {C}}\)
We now return to the flower. For convenience, for the rest of the example we will parametrise the edges as follows: we consider each loop (or petal) of the flower at having a dummy vertex at the far point from the central vertex, and identify the loop with \([-\frac{L}{2m},\frac{L}{2m}]\), where 0 corresponds to the central vertex, and the points \(-\frac{L}{2\,m}\) and \(\frac{L}{2\,m}\) are identified at the dummy vertex.
We can now calculate \(\rho _{F_m}(x)\) for a given \(x \in F_m\). With the above parametrisation of the edges,
Integrating over \(x \in [-\frac{L}{2m},\frac{L}{2m}]\) and using the symmetry of the graph finally yields
Let us consider how \(\rho \) behaves as a function of \(m \ge 1\). If the total length L is fixed, then, since \(x \mapsto \frac{L}{4x}(\frac{2x-1}{x})\) attains a global maximum for \(x>0\) between 0 and 1, then decreasing to 0 as \(x \rightarrow \infty \), it follows that \(\rho (F_m)\) attains its maximum at \(m=1\), is strictly monotonically decreasing in \(m \ge 1\), and \(\rho (F_m) \rightarrow 0\) as \(m \rightarrow \infty \).
If instead we fix the length of each edge \(\ell = \frac{L}{m}\), we have
as \(m \rightarrow \infty \).
We finish this section with an optimisation result for flower graphs, which will be needed in the proof of the lower bound in (3.3) in Sect. 5. While elementary, its proof is necessarily somewhat technical.
Lemma 4.4
For any flower graph F of total length L, on m edges, we have
with equality if and only if F is an equilateral flower on m edges of length L/m each.
Proof
Fix a flower graph F with edge lengths \(\ell _1,\ldots ,\ell _m\), so that \(\sum _{i=1}^m \ell _i = L\), and denote by 0 the central vertex. We start by recalling from (4.2) that, if \(\mathcal {C}\) is a loop of length \(\ell > 0\), then \(\rho _{\mathcal {C}} (x) = \frac{\ell }{4}\) for all \(x \in \mathcal {C}\), and so
as well. Now a similar calculation to the one for the equilateral flower graph yields that, for any given \(x \in F\), supposing that \(x \in e_i\) and \(|e_i| = \ell _i\),
where \({{\,\textrm{dist}\,}}(x,0)\) represents the distance between x and the central vertex 0. Integrating over the corresponding edge \(e_i\) gives
whence
We will now examine what happens if we perturb the lengths of two petals of F, without loss of generality \(e_1\) and \(e_2\), in such a way that the overall length remains constant: we will, in effect, consider \(\frac{\partial \rho }{\partial \ell _1}\) under the assumption that \(\ell _3,\ldots ,\ell _m\) are constant, and \(\ell _2 = L - \ell _1 - \sum _{i=3}^m \ell _i\). To this end we first multiply out the constant term \(4L^2\) and isolate the parts of (4.3) that depend on \(\ell _1\) and \(\ell _2\):
where since the latter sum does not depend on \(\ell _1\) or \(\ell _2\), we may treat it as a constant d and subtract it from the total; we will thus work with the quantity \(D:=4L^2\rho (F)-d\), which we will attempt to minimise in function of \(\ell _1\). To simplify the calculation, we will set \(B:=\sum _{i=3}^m \ell _i\) and \(C:=\ell _1+\ell _2\), which we recall we are treating as constant; we also recall that \(L=\sum _{i=1}^m \ell _i\), and in particular \(L = B + C\). We may then calculate
Writing \(\ell _2 = L - B - \ell _1\), we may simplify this to
since \(L-B\) does not depend on \(\ell _1\), under our assumptions we may rewrite D as
which is quadratic in \(\ell _1\). In particular, \(\frac{\partial D}{\partial \ell _1}\) (itself equal to \(4\,L^2\frac{\partial \rho }{\partial \ell _1}\)) is zero if and only if
moreover, this represents the unique global minimum of D (and thus of \(\rho \)) for \(\ell _1 \in [0,C]\).
Summarising, among all flowers on m petals of given total length L and fixed edge lengths \(\ell _3,\ldots ,\ell _m\), \(\rho \) is minimised exactly when \(\ell _1 = \ell _2\); moreover, holding all other lengths fixed, any flower graph for which \(\ell _1 \ne \ell _2\) will have strictly greater \(\rho \) than the one for which there is equality.
Hence, starting from any given non-equilateral flower F on m edges and iteratively applying this argument to pairs of its petals, we obtain a sequence of flower graphs with strictly decreasing \(\rho \), whose edge lengths will converge in the limit to those of the equilateral flower. Since for fixed \(L>0\) and \(m\ge 1\), \(\rho \) is obviously continuous with respect to the m edge lengths (being a polynomial, see 4.3), which are drawn from a compact subset of \([0,L]^m\), it is immediate that \(\rho \) must attain its unique global minimum among all flowers of length \(L>0\) on m edges, at the equilateral flower. \(\square \)
5 Surgery Principles
In this section we list and prove two basic surgery principles for \(\rho \), which we then use to prove our main bounds (3.3) (including the characterisation of equality). These principles, which give sufficient conditions under which making a “local” change to a graph \(\mathcal {G}\) to create a new graph \({\widetilde{\mathcal {G}}}\) (e.g. cutting through a vertex, lengthening an edge, attaching or removing a pendant graph) will raise or lower \(\rho \); they are generally inspired by, and similar to, such surgery principles for eigenvalues of the Laplacian with standard vertex conditions (see [4]). There will certainly be many more such principles beyond these two, but these are the two needed to prove (3.3).
The first, cutting through vertices, has a long history in the context of Laplacian eigenvalues (going back at least to [20, Theorem 1] but implicit in the proof of [29, Théorème 3.1]). However, since we will not be working with a variational characterisation of \(\rho \), the proof is completely different, and relies on comparing the respective mean distance functions \(\rho _\mathcal {G}\) and \(\rho _{{\widetilde{\mathcal {G}}}}\) in a suitable way (but cf. Remark 7.2). The second, the key to the upper bound in (3.3), is a somewhat generalised version of the principle of “unfolding pendant edges”, see [4, Theorem 3.18(4)], but with rather different hypotheses on the pendant graph being “unfolded” (see also Fig. 2).
Theorem 5.1
(Surgery principles for mean distance) Let \(\mathcal {G}\) be a compact metric graph.
-
(1)
Suppose \({\widetilde{\mathcal {G}}}\) is formed from \(\mathcal {G}\) by cutting through a vertex (see [4, Section 3.1]). Then \(\rho ({\widetilde{\mathcal {G}}}) > \rho (\mathcal {G})\) unless \({\widetilde{\mathcal {G}}} = \mathcal {G}\) (i.e., the cut is the trivial cut, where the cut vertex is unchanged).
-
(2)
Suppose \(\mathcal {H}\) is a pendant subgraph of \(\mathcal {G}\), that is, \(\mathcal {H}\subset \mathcal {G}\) and there exists \(\textsf{v}\in \textsf{V}(\mathcal {G})\) such that \(\partial \mathcal {H}:= \mathcal {H}\cap \overline{\mathcal {G}\setminus \mathcal {H}} = \{\textsf{v}\}\). Suppose \({\widetilde{\mathcal {G}}}\) is formed from \(\mathcal {G}\) by replacing \(\mathcal {H}\) with another graph \({\widetilde{\mathcal {H}}}\) in such a way that \({\widetilde{\mathcal {G}}} \setminus {\widetilde{\mathcal {H}}} = \mathcal {G}\setminus \mathcal {H}\). If the graphs \(\mathcal {H}\) and \({\widetilde{\mathcal {H}}}\) satisfy, cumulatively,
-
(a)
\(|\mathcal {H}| = |{\widetilde{\mathcal {H}}}|\),
-
(b)
\(\rho _{{\widetilde{\mathcal {H}}}}(\textsf{v}) \ge \rho _\mathcal {H}(\textsf{v})\), and
-
(c)
\(\rho ({\widetilde{\mathcal {H}}}) \ge \rho (\mathcal {H})\),
then \(\rho ({\widetilde{\mathcal {G}}}) \ge \rho (\mathcal {G})\). The inequality is strict if \(\rho _{{\widetilde{\mathcal {H}}}} (\textsf{v}) > \rho _\mathcal {H}(\textsf{v})\), or if \(\rho ({\widetilde{\mathcal {H}}}) > \rho (\mathcal {H})\).
-
(a)
Example 5.2
Suppose \(\mathcal {H}= {\widetilde{\mathcal {H}}} = e_1 \cup e_2\), but the point of attachment to \(\mathcal {G}{\setminus } \mathcal {H}= {\widetilde{\mathcal {G}}} {\setminus } {\widetilde{\mathcal {H}}}\) is changed, as depicted in Fig. 2:
Then both subgraphs may be identified with some interval \([0,\ell ]\), \(\ell >0\), with \(\rho _\mathcal {H}(x)=\rho _{\widetilde{\mathcal {H}}}=\frac{x^2}{\ell }-x+\frac{\ell }{2}\) (see (4.1)). In particular, since \(\frac{\ell }{2} > \frac{x^2}{\ell }-x+\frac{\ell }{2}\) for any \(x \in (0,\ell )\), and since in \(\widetilde{\mathcal {H}}\) we are taking the point of attachment as \(\textsf{v}\simeq 0\) (whereas in \(\mathcal {H}\) the point of attachment will be somewhere in \((0,\ell )\)), it follows that \(\rho _{\widetilde{\mathcal {H}}}(\textsf{v}) = \frac{\ell }{2} > \rho _\mathcal {H}(\textsf{v})\) as long as \(|e_1|, |e_2| \ne 0\). We conclude from Theorem 5.1(2) that in this case \(\rho (\widetilde{\mathcal {G}})>\rho (\mathcal {G})\).
More difficult is the issue of lengthening an edge, that is, if \({\widetilde{\mathcal {G}}}\) is formed from \(\mathcal {G}\) by increasing the length of a given edge e (and thus, equally, the total length of the graph), holding the graph topology and all other edge lengths constant, do we have \(\rho ({\widetilde{\mathcal {G}}}) \ge \rho (\mathcal {G})\)? A corresponding statement holds for the standard Laplacian eigenvalues (see [4, Corollary 3.12(1)]). In the related case of attaching a pendant graph at a vertex (see [4, Definition 3.9]), if one attaches a sufficiently short pendant edge at a vertex \(\textsf{v}\), then \(\rho \) will actually decrease as long as \(\rho _\mathcal {G}(\textsf{v}) < \rho (\mathcal {G})\). This also provides an example whereby lengthening a (very short) edge will lower \(\rho \) (our thanks go to Noah Kravitz for pointing out this principle to us).
Proposition 5.3
Suppose the family of graphs \(\mathcal {G}_\ell \) is formed from \(\mathcal {G}\) by attaching a pendant edge of length \(\ell \) to \(\mathcal {G}\) at a vertex \(\textsf{v}\). Then the function \(\ell \mapsto \rho (\mathcal {G}_\ell )\) is a \(C^1\)-function of \(\ell \ge 0\), and
Note that this result immediately applies, mutatis mutandis, if we lengthen any already existing pendant edge of \(\mathcal {G}\): we obtain a “Hadamard-type” formula for the derivative at \(\ell = \ell _0\) given by
where \(\textsf{v}_0\) is the degree-one vertex at the end of the edge. This can be obtained as an immediate consequence of Proposition 5.3 by attaching a short edge to \(\textsf{v}_0\) (turning the latter into a dummy vertex), or else by making a trivial adaptation of the proof of the proposition.
Proof of Theorem 5.1
In this proof it will be important to distinguish the distance functions on different graphs; thus we will write \({{\,\textrm{dist}\,}}_{\mathcal {G}}\) for the distance function on \(\mathcal {G}\), and so on.
(1) Fix any two \(x,y \in {\widetilde{\mathcal {G}}}\) which are not in the image of the cut vertex in \(\mathcal {G}\), and recall that by definition \({{\,\textrm{dist}\,}}_{{\widetilde{\mathcal {G}}}}(x,y)\) is the infimum of the lengths of all paths between x and y in \({\widetilde{\mathcal {G}}}\). Canonically identifying x and y with points in \(\mathcal {G}\), we see that the set of paths between x and y in \(\mathcal {G}\) can only be larger than its counterpart in \({\widetilde{\mathcal {G}}}\); thus the infimum is lower,
Since this holds for all x, y outside a finite set, the desired inequality for \(\rho \) follows from the definition.
For the strict inequality, suppose \(\textsf{v}\in \mathcal {G}\) is the vertex being cut, and \(\textsf{v}_1,\textsf{v}_2 \in {\widetilde{\mathcal {G}}}\) are two distinct vertices obtained from the cut. Take \(\varepsilon >0\) to be less than a third of the minimum edge length in \(\mathcal {G}\) (and thus in \({\widetilde{\mathcal {G}}}\) as well). There will necessarily exist edges \(e_1 \sim \textsf{v}_1\) and \(e_2 \sim \textsf{v}_2\) in \({\widetilde{\mathcal {G}}}\), which are adjacent at \(\textsf{v}\) in \(\mathcal {G}\), but not at \(\textsf{v}_1 \ne \textsf{v}_2\) in \({\widetilde{\mathcal {G}}}\). Then, in \(\mathcal {G}\), for all \(x \in e_1 \cap B_\varepsilon (\textsf{v})\) and \(y \in e_2 \cap B_\varepsilon (\textsf{v})\), \({{\,\textrm{dist}\,}}_\mathcal {G}(x,y) \le 2\varepsilon \).
Now consider the shortest path from x to y in \({\widetilde{\mathcal {G}}}\). There are two possibilities: either it runs through an entire edge of \({\widetilde{\mathcal {G}}}\), in which case it must have length at least \(3\varepsilon \), or it is entirely contained in the union of \(e_1\) and \(e_2\). Since \(e_1\) and \(e_2\) are not adjacent at \(\textsf{v}_1 \ne \textsf{v}_2\), in this case they must be adjacent at their respective other endpoints, say at the common vertex \(w \in {\widetilde{\mathcal {G}}}\). Since \(|e_1|,|e_2| \ge 3\varepsilon \) and \({{\,\textrm{dist}\,}}_{{\widetilde{\mathcal {G}}}}(x,\textsf{v}_1) < \varepsilon \), \({{\,\textrm{dist}\,}}_{{\widetilde{\mathcal {G}}}}(y,\textsf{v}_2) < \varepsilon \), it follows that \({{\,\textrm{dist}\,}}_{\widetilde{\mathcal {G}}}(x,w), {{\,\textrm{dist}\,}}_{\widetilde{\mathcal {G}}}(y,w) \ge 2\varepsilon \), and thus \({{\,\textrm{dist}\,}}_{\widetilde{\mathcal {G}}} (x,y) \ge 4\varepsilon \) in this case.
At any rate, we obtain that \({{\,\textrm{dist}\,}}_{\mathcal {G}} (x,y) < 2\varepsilon \), while \({{\,\textrm{dist}\,}}_{\widetilde{\mathcal {G}}} \ge 3\varepsilon \), for all such x, y. Integrating over all \(x \in e_1 \cap B_\varepsilon (\textsf{v})\) and \(y \in e_2 \cap B_\varepsilon (\textsf{v})\) (which each form a set of measure \(\varepsilon \)) leads to the strict inequality
and thus \(\rho (\mathcal {G}) < \rho ({\widetilde{\mathcal {G}}})\).
(2) Note that \(|\mathcal {G}|=|\widetilde{\mathcal {G}}|\), so it suffices to prove that
We divide the former integral into three parts, each of which will be analysed separately:
(i) For the first integral, since for all \(x,y \in \widetilde{\mathcal {G}} {\setminus } \widetilde{\mathcal {H}} \simeq \mathcal {G}{\setminus } \mathcal {H}\), the shortest path connecting x, y does not run through the pendant \(\widetilde{\mathcal {H}}\) (or \(\mathcal {H}\), respectively), with the possible exception of \(\textsf{v}\),
for all \(x,y \in \widetilde{\mathcal {G}} {\setminus } \widetilde{\mathcal {H}} \simeq \mathcal {G}{\setminus } \mathcal {H}\), whence
(ii) For the second term, we are considering points of the form \(x \in \widetilde{\mathcal {G}} {\setminus } \widetilde{\mathcal {H}}\), \(y \in \widetilde{\mathcal {H}}\); since \(\widetilde{\mathcal {H}}\) is a pendant attached at \(\textsf{v}\), in this case
(and similarly for \(\mathcal {H}\)). Noting that the distance functions in \(\mathcal {G}{\setminus } \mathcal {H}\) and \({\widetilde{\mathcal {G}}} {\setminus } {\widetilde{\mathcal {H}}}\) coincide, we deduce that
Using the assumption (a), we may rewrite I as
while for J we have, by (a) and (b),
Putting these two estimates together, we obtain
(iii) Since by (c) we have \(\rho (\widetilde{\mathcal {H}})\ge \rho (\mathcal {H})\), by (a), \(|\mathcal {H}|=|\widetilde{\mathcal {H}}|\,(\ge 0)\), and by assumption on \(\widetilde{\mathcal {H}}\) and \(\mathcal {H}\) as pendants, \({{\,\textrm{dist}\,}}_{\widetilde{\mathcal {G}}}(x,y) = {{\,\textrm{dist}\,}}_{\widetilde{\mathcal {H}}} (x,y)\) for all \(x,y \in \widetilde{\mathcal {H}}\) and \({{\,\textrm{dist}\,}}_{\mathcal {G}} (x,y) = {{\,\textrm{dist}\,}}_{\mathcal {H}} (x,y)\) for all \(x,y, \in \mathcal {H}\), it is immediate that
Finally, putting (i), (ii) and (iii) together yields
For the strict inequality, we note that if \(\rho _{\widetilde{\mathcal {H}}}(\textsf{v}) > \rho _\mathcal {H}(\textsf{v})\), then the inequality in (ii) is strict, while if \(\rho (\widetilde{\mathcal {H}}) > \rho (\mathcal {H})\), then the inequality in (iii) is strict. In either case, we then have \(\rho (\widetilde{\mathcal {G}}) > \rho (\mathcal {G})\). \(\square \)
We can now prove the bounds (3.3), including the statements about equality.
Proof of (3.3)
For the lower bound, given a graph \(\mathcal {G}\) which is not already a flower, by Theorem 5.1(1) there exists a flower F with the same number of edges, obtained by gluing all vertices of \(\mathcal {G}\) together, such that \(\rho (\mathcal {G}) > \rho (F)\). The claim now follows immediately from Lemma 4.4.
For the upper bound, if \(\mathcal {G}\) is not already a tree, then by Theorem 5.1(1) there exists a tree T having the same total length such that \(\rho (T) > \rho (\mathcal {G})\). If T is not already a path graph, we successively apply Example 5.2 to pairs of adjacent pendant edges \(e_1\), \(e_2\), that is, edges \(e_1\) and \(e_2\) in T sharing a common vertex \(\textsf{v}\), such that their other vertex is a leaf. After a finite number of steps T is transformed into an interval I of the same total length as T and hence as \(\mathcal {G}\), with \(\rho (I) > \rho (T)\).
To conclude, suppose \(\mathcal {G}\) is any graph which is not a path graph. If it is not a tree, then we are in the first case, and \(\rho (\mathcal {G}) < \rho (T) \le \rho (I)\). If it is a tree, then we are in the second case, and \(\rho (\mathcal {G}) < \rho (I)\) still. This shows both the inequality, and the sharpness of the inequality at the same time. \(\square \)
We finish with the proof that the effect of attaching a pendant edge at a vertex \(\textsf{v}\) depends on the relation between \(\rho _\mathcal {G}(\textsf{v})\) and \(\rho (\mathcal {G})\).
Proof of Proposition 5.3
We will show that the function
is a \(C^1\)-function of \(\ell \ge 0\), with derivative at \(\ell = 0\) given by \(2|\mathcal {G}|\rho _\mathcal {G}(\textsf{v})\); the other assertions of the proposition then follow directly upon applying the quotient rule to the function
(and noting that \(\ell \mapsto |\mathcal {G}_\ell |\) is a smooth function, with \(\frac{{\mathrm d}}{{\mathrm d}\ell } |\mathcal {G}_\ell | = 1\) for all \(\ell \ge 0\)). Now, for fixed \(\ell > 0\), denoting by \(e = e(\ell )\) the pendant edge of length \(\ell \) attached to \(\textsf{v}\), we have
Using the fact that e is a pendant (and, as a subgraph, identifiable with an interval), we obtain
(see Example 4.1, and in particular (4.1)), as well as
since the mean distance from an arbitrarily chosen \(x \in e\) to \(\textsf{v}\) will be \(\frac{\ell }{2}\), the mean distance from \(\textsf{v}\) to an arbitrary \(y \in \mathcal {G}\) is, by definition, \(\rho _\mathcal {G}(\textsf{v})\), and this mean over \(\mathcal {G}\) needs to be integrated over the edge e of length \(\ell \) to obtain the total integral value. Putting these together, it follows that for any \(\ell \ge 0\) the derivative of the function (5.1) exists and at zero is given by
as claimed. The statement of the proposition now follows. \(\square \)
6 Symmetrisation and Doubly Connected Graphs
In this section we will prove the sharpened upper bound (3.4) for doubly connected graphs, including the characterisation of equality. We recall that a graph \(\mathcal {G}\) is said to be doubly (path) connected if, for any \(x,y \in \mathcal {G}\), there exist two edgewise disjoint paths \(P_1\) and \(P_2\) in \(\mathcal {G}\) connecting x and y (although we allow the paths to intersect at a finite number of vertices); equivalently, no edge of \(\mathcal {G}\) is a bridge whose removal would disconnect \(\mathcal {G}\).
Unlike for (3.3), in this case there is a natural proof via symmetrisation using the same basic tool, the coarea formula, as Friedlander’s symmetrisation-based proof of Nicaise’ inequality [13] (see also [1, 3], and Remark 6.3). We recall that the coarea formula states that
valid for an integrable nonnegative function \(\varphi \) on some domain \(\Omega \) (which can be a metric graph) and an absolutely continuous, integrable nonnegative function \(\psi \) (for metric graphs, see, e.g., [22] or [10, Lemma 4.6]).
Lemma 6.1
For any compact graph \(\mathcal {G}\) of total length \(L>0\) and any \(x \in \mathcal {G}\), we have
Proof
We apply the coarea formula (6.1) to the Lipschitz continuous function \(\varphi = \psi = {{\,\textrm{dist}\,}}(x,\cdot )\). Since its gradient has absolute value 1 almost everywhere, this yields
as claimed. \(\square \)
We recall (Example 4.3) that for the loop (or circle) \(\mathcal {C}\) of length L,
large classes of examples and some intuition suggest that loops should be the only graphs \(\mathcal {G}\) with the property that \(\rho _{\mathcal {G}}(x)\) is constant independent of x, although we will not attempt to prove that here. Curiously, precisely this independence will play a central role in the symmetrisation argument.
Lemma 6.2
Let \(\mathcal {G}\) be a compact, doubly connected graph of length \(L>0\). For each \(x \in \mathcal {G}\),
The inequality is strict for at least one \(x_0 \in \mathcal {G}\) (and thus all x in a small neighbourhood of \(x_0\)) if \(\mathcal {G}\) is not a loop.
Proof
Fix \(x,y\in \mathcal {G}\). Since \(\mathcal {G}\) is doubly connected, there exist at least two paths \(P_1\), \(P_2\) in \(\mathcal {G}\) from x to y, which can intersect at at most a finite set of points. It follows that \(|P_1|+|P_2| \le L\) and hence at least one path has length at most \(\frac{L}{2}\).
If \(M(x)=\frac{L}{2}\) for all \(x \in \mathcal {G}\), then for any \(x \in \mathcal {G}\) there exists \(y \in \mathcal {G}\) such that there are exactly two edgewise disjoint paths \(P_1\) and \(P_2\) from x to y, each of length exactly \(\frac{L}{2}\), whose union exhausts \(\mathcal {G}\). The only possibility is that \(\mathcal {G}\) is a loop. \(\square \)
Proof of (3.4)
We will show that, for any \(x \in \mathcal {G}\), we have
that is, the pointwise value of \(\rho _\mathcal {G}\) is always below the constant value of \(\rho _{\mathcal {C}}\) on \(\mathcal {C}\). The inequality will follow immediately from (6.2).
Fix \(x \in \mathcal {G}\) and write
for the size of the level set of the corresponding distance function, for any \(0 \le t \le M:= M(x) \le \frac{L}{2}\). We extend \(\xi (t)\) by zero to a function on \([0,\frac{L}{2}]\); then, by the coarea formula (6.1),
We claim that
To see this, note that, obviously,
and so
note that the first integral is necessarily nonnegative since the nonnegative functions \(\xi \) and 2 have the same \(L^1\)-norm on \([0,\frac{L}{2}]\), while \(\xi \) is supported only on \([0,M] \subset [0,\frac{L}{2}]\). (The first integral is seen to be zero if and only if \(M=\frac{L}{2}\)). It follows directly that
Rearranging yields (6.3) and thus the pointwise comparison between \(\rho _{\mathcal {G}}\) and \(\rho _{\mathcal C}\). The inequality statement in the theorem now follows immediately from Lemma 6.1, since
which establishes (6.2) for arbitrary \(x \in \mathcal {G}\).
Finally, if \(\mathcal {G}\) is not a loop, then there exists some \(x_0 \in \mathcal {G}\) for which \(M(x_0) < \frac{L}{2}\). By a continuity argument, we can find \(\delta ,\varepsilon > 0\) such that \(M(x) \le \frac{L}{2} - \varepsilon \) for all x in a \(\delta \)-neighbourhood of \(x_0\). For such x, we have
Since
we can thus sharpen (6.3) to
and thus obtain
for all x in a \(\delta \)-neighbourhood of some \(x_0 \in \mathcal {G}\); in particular, the total measure of all such \(x \in \mathcal {G}\) is at least \(2\delta \). It follows that the inequality \(\rho (\mathcal {G}) \le \frac{L}{4}\) must be strict. \(\square \)
Remark 6.3
Curiously, it is not clear how this symmetrisation idea could be adapted to simply connected graphs and the interval: on the loop the mean distance function is constant, so we obtain a pointwise comparison between \(\rho _\mathcal {G}(x)\) and the constant value \(\rho _{\mathcal {C}}(x)=\frac{L}{4}\). To use such an argument compare an arbitrary graph with an interval (path graph) I, where \(\rho _I(x)\) is not constant (see (4.1)), we would first need to find a way of associating, for each \(x \in \mathcal {G}\), some unique \(y_x \in I\) such that then \(\rho _\mathcal {G}(x) \le \rho _{I}(y_x)\). It is not at all clear how this should work.
7 A Variational Comparison Method
This short section is devoted to the proof of Theorem 3.5. We first fix any point, without loss of generality a vertex, \(\textsf{v}\in \mathcal {G}\) such that
whose existence follows directly from the continuity of the function \(\rho _\mathcal {G}\) and the definition of \(\rho (\mathcal {G})\) as mean value of \(\rho _\mathcal {G}\).
We define
to be the first eigenvalue of the Laplacian on \(\mathcal {G}\) with a Dirichlet condition at \(\textsf{v}\) and standard conditions elsewhere (we allow that \(\mathcal {G}\setminus \{\textsf{v}\}\) be disconnected; in this case the corresponding eigenfunctions may be supported on a proper subset of \(\mathcal {G}\)). Fix any \(f \in H^1(\mathcal {G})\) such that \(f(\textsf{v})=0\). For \(x \in \mathcal {G}\) we denote by \(P(\textsf{v},x)\) any shortest path in \(\mathcal {G}\) from \(\textsf{v}\) to x, then from
and the Cauchy–Schwarz inequality it follows that
Replacing \(P(\textsf{v},x)\) with \(\mathcal {G}\), taking squares, integrating over \(x \in \mathcal {G}\) and infimising over f yields
Theorem 3.5 now follows from the following eigenvalue comparison result.
Lemma 7.1
Let \(\mathcal {G}\) be a compact metric graph, let \(\textsf{v}\in \mathcal {G}\) be arbitrary, and let \(\lambda _1 (\mathcal {G},\textsf{v})\) be the first eigenvalue of the Laplacian on \(\mathcal {G}\) with a Dirichlet condition at \(\textsf{v}\) and standard conditions elsewhere, as defined by (7.1). Then
Proof
Denote by \(\psi \in H^1(\mathcal {G})\) any eigenfunction associated with \(\mu _2(\mathcal {G})\), and denote by \(\mathcal {G}_+\) and \(\mathcal {G}_-\) any two (disjoint) nodal domains of \(\psi \), i.e., connected subsets of \(\{x \in \mathcal {G}: \psi (x) \ne 0\}\); then a standard variational argument (cf. [3, Proof of Theorem 3.4]) shows that \(\mu _2(\mathcal {G}) = \lambda _1 (\mathcal {G}_+,\partial \mathcal {G}_+) = \lambda _1 (\mathcal {G}_-,\partial \mathcal {G}_-)\) where \(\lambda _1 (\mathcal {G}_\pm ,\partial \mathcal {G}_\pm )\) is the first eigenvalue of \(\mathcal {G}_\pm \) with Dirichlet conditions at every point in \(\partial \mathcal {G}_\pm \) (and standard conditions at all interior vertices).
Now necessarily \(\textsf{v}\in \mathcal {G}\setminus \mathcal {G}_+\) or \(\textsf{v}\in \mathcal {G}{\setminus } \mathcal {G}_-\), without loss of generality \(\mathcal {G}{\setminus } \mathcal {G}_+\). Then domain monotonicity for Dirichlet eigenvalues implies that
as claimed. \(\square \)
Remark 7.2
We finish with some open-ended comments related to the observation that there is no obvious variational characterisation of \(\rho \); it would be very interesting if one could be obtained as this would open up the use of more variational techniques to studying it, and would potentially offer insights into the parallels with the variational quantity \(\mu _2\). We note that, as is easy to see, for any given \(x \in \mathcal {G}\) (with \(\mathcal {G}\) a compact metric graph), the mean distance from x can be characterised as
This principle can be used to rephrase slightly some of the arguments presented above, at least those which involve comparing two graphs \(\mathcal {G}\) and \({\widetilde{\mathcal {G}}}\) for which there is some kind of natural pointwise correspondence between them. For example, to prove Theorem 5.1(1) one can use that there is a canonical identification \(\mathcal {G}\rightarrow {\widetilde{\mathcal {G}}}\) such that, under this identification, \(C(\mathcal {G}) \subset C({\widetilde{\mathcal {G}}})\), with preservation of all function norms, and for almost every x, due to the weakened continuity requirement in \({\widetilde{\mathcal {G}}}\),
whence \(\rho _{\mathcal {G}} (x) \le \rho _{{\widetilde{\mathcal {G}}}} (x)\) for a.e. x. Integrating over x and using that \(|\mathcal {G}| = |{\widetilde{\mathcal {G}}}|\) yields the result. This argument mirrors more closely the corresponding argument for \(\mu _2\).
Data Availability
No new data were created or analyzed in this study.
References
Band, R., Lévy, G.: Quantum graphs which optimize the spectral gap. Ann. Henri Poincaré 18, 3269–3323 (2017)
Berkolaiko, G., Kuchment, P.: Introduction to Quantum Graphs. Math. Surveys and Monographs, vol. 186. Amer. Math. Soc., Providence, RI (2013)
Berkolaiko, G., Kennedy, J.B., Kurasov, P., Mugnolo, D.: Edge connectivity and the spectral gap of combinatorial and quantum graphs. J. Phys. A 50, 365201 (2017)
Berkolaiko, G., Kennedy, J.B., Kurasov, P., Mugnolo, D.: Surgery principles for the spectral analysis of quantum graphs. Trans. Amer. Math. Soc. 372, 5153–5197 (2019)
Brasco, L.: On torsional rigidity and principal frequencies: an invitation to the Kohler-Jobin rearrangement technique. ESAIM Control Optim. Calc. Var. 20, 315–338 (2014)
Briani, L., Buttazzo, G., Prinari, F.: Inequalities between torsional rigidity and principal eigenvalue of the \(p\)-Laplacian. Calc. Var. Partial Differ. Eqs. 61, 78 (2022)
Chung, F.R.K.: The average distance and the independence number. J. Graph Theory 12, 229–235 (1988)
Dankelmann, P.: Average distance in weighted graphs. Discrete Math. 312, 12–20 (2012)
Doyle, J.K., Graver, J.E.: Mean distance in a graph. Discrete Math. 17, 147–154 (1977)
Düfel, M., Kennedy, J.B., Mugnolo, D., Plümer, M., Täufer M.: Boundary conditions matter: On the spectrum of infinite quantum graphs. arXiv:2207.04024
Entringer, R.C., Jackson, D.E., Snyder, D.A.: Distance in graphs. Czech. Math. J. 26, 283–296 (1976)
Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23, 298–305 (1973)
Friedlander, L.: Extremal properties of eigenvalues for a metric graph. Ann. Inst. Fourier 55, 199–212 (2005)
Garijo, D., Márquez, A., Silveira, R.I.: Continuous mean distance of a weighted graph. Results Math. 78, 139 (2023)
Goddard, W., Oellermann, O.R.: Distance in graphs. In: Dehmer, M. (ed.) Structural Analysis of Complex Networks, pp. 49–72. Birkhäuser, Boston (2011)
Harary, F.: Status and contrastatus. Sociometry 22, 23–43 (1959)
Kennedy, J.B., Kurasov, P., Malenové, G., Mugnolo, D.: On the spectral gap of a quantum graph. Ann. Henri Poincaré 17, 2439–2473 (2016)
Kohler-Jobin, M.-T.: Une méthode de comparaison isopérimétrique de fonctionnelles de domaines de la physique mathématique. I. Une démonstration de la conjecture isopérimétrique \(P\lambda ^{2}\ge \pi j^{4}_{0}/2\) de Pólya et Szegő. Z. Angew. Math. Phys. 29, 757–766 (1978)
Kurasov, P.: Spectral Geometry of Graphs. Operator Theory: Advances and Applications, vol. 298. Birkhäuser, Cham (2023)
Kurasov, P., Malenová, G., Naboko, S.: Spectral gap for quantum graphs and their connectivity. J. Phys. A 46, 275309 (2013)
Lumer, G.: Connecting of local operators and evolution equations on networks. In: Hirsch, F. (ed.) Potential Theory (Proc. Copenhagen 1979), pp. 230–243. Springer-Verlag, Berlin (1980)
Mazón, J.M.: The total variation flow in metric graphs. Math. Eng. 5, 1–38 (2023)
Mohar, B.: The diameter and the mean distance of a Riemannian manifold. Bull. Amer. Math. Soc. 21, 261–263 (1989)
Mohar, B.: Eigenvalues, diameter, and mean distance in graphs. Graphs Combin. 7, 53–64 (1991)
Mohar, B.: The Laplacian Spectrum of Graphs. In: Avali, Y., et al. (eds.) Graph Theory, Combinatorics, and Applications, vol. 2, pp. 871–898. Wiley, New York (1991)
Mugnolo, D.: What is actually a metric graph? arXiv:1912.07549
Mugnolo, D.: Semigroup Methods for Evolution Equations on Networks. Underst. Compl. Syst. Springer-Verlag, Berlin (2014)
Mugnolo, D., Plümer, M.: On torsional rigidity and ground-state energy of compact quantum graphs. Calc. Var. Partial Differ. Eqs. 62, 27 (2023)
Nicaise, S.: Spectre des réseaux topologiques finis. Bull. Sci. Math., II. Sér. 111, 401–413 (1987)
Ore, O.: Theory of Graphs. Amer, vol. 38. Math. Soc. Colloquium Publications. Amer. Math. Soc, Providence, RI (1962)
Plesník, J.: On the sum of all distances in a graph or digraph. J. Graph Theory 8, 1–21 (1984)
Sivasubramanian, S.: Average distance in graphs and eigenvalues. Disc. Math. 309, 3458–3462 (2009)
Steinerberger, S.: Curvature on graphs via equilibrium measures. J. Graph Theory 103, 415–436 (2023)
Wiener, H.: Structural determination of paraffin boiling points. J. Amer. Chem. Soc. 69, 17–20 (1947)
Funding
Open Access funding enabled and organized by Projekt DEAL.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
L.N.B. and J.B.K. were supported by the Fundação para a Ciência e a Tecnologia, Portugal, reference PTDC/MAT-PUR/1788/2020 (J.B.K.) and UIDB/00208/2020 (both authors). D.M. was partially supported by the Deutsche Forschungsgemeinschaft (Grant 397230547). This article is based upon work from COST Action 18232 MAT-DYN-NET, supported by COST (European Cooperation in Science and Technology), www.cost.eu. The authors are very grateful to Pavel Kurasov (Stockholm) for participating in the early discussions from which this article developed, and to Noah Kravitz (Princeton) for a number of very helpful observations and suggestions, including the idea behind Proposition 5.3.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Baptista, L.N., Kennedy, J.B. & Mugnolo, D. Mean Distance on Metric Graphs. J Geom Anal 34, 137 (2024). https://doi.org/10.1007/s12220-024-01574-0
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s12220-024-01574-0