Zoran Stanic´
Faculty of Mathematics, University of Belgrade, Studentski trg 16, 11 000 Belgrade, Serbia zstanic@math.bg.ac.rs
The second smallest eigenvalue of the Laplacian matrix of a graph G is called the algebraic connectivity and denoted by a(G). We prove that
\[a(G) > \frac{\pi^2}{3} \left( p \frac{12\overline{g}(n_1, n_2, \dots, n_p)^2 - \pi^2}{4\overline{g}(n_1, n_2, \dots, n_p)^4} + 4(q - p) \frac{3\overline{g}(n_{p+1}, n_{p+2}, \dots, n_q)^2 - \pi^2}{\overline{g}(n_{p+1}, n_{p+2}, \dots, n_q)^4} \right),\]
holds for every non-trivial graph G which contains edge-disjoint spanning subgraphs G1, G2, . . . , Gq such that, for 1 ≤ i ≤ p, a(Gi) ≥ a(Pni ), with ni ≥ 2, and, for p+ 1 ≤ i ≤ q, a(Gi) ≥ a(Cni ), where Pni and Cni denote the path and the cycle of the corresponding order, respectively, and g denotes the geometric mean of given arguments. Among certain consequences, we emphasize the following lower bound
\[a(G) > \pi^2 \frac{12(4q - 3p)n^2 - (16q - 15p)\pi^2}{12n^4},\]
referring to G which has n (n ≥ 2) vertices and contains p Hamiltonian paths and q−p Hamiltonian cycles, such that all of them are edge-disjoint. We also discuss the quality of the obtained lower bounds.
Keywords: edge-disjoint subgraphs, Laplacian matrix, algebraic connectivity, geometric mean, Hamiltonian cycle Mathematics Subject Classification : 05C50
DOI: 10.5614/ejgta.2021.9.2.2
Received: 8 January 2020, Revised: 12 February 2021, Accepted: 22 March 2021.
1. Introduction
The Laplacian of a graph G is the positive semidefinite matrix L(G) = D(G) - A(G), where D(G) is the diagonal matrix of vertex degrees and A(G) is the standard adjacency matrix. Among all eigenvalues of the Laplacian of a graph, one of the most popular is the second smallest called, by Fiedler [5], the algebraic connectivity of a graph. The algebraic connectivity is usually denoted by a(G). Its significance is due to the fact that it measures (to a certain extent) how well a graph is connected. For example, a graph G is connected if and only if a(G) > 0.
The number of vertices (also known as the order) and the number of edges of a graph G are denoted by n and m (or m(G)), respectively. We also use d for the diameter of a graph. A path and a cycle of order n are denoted by \(P_n\) and \(C_n\), respectively. A graph is Hamiltonian if it contains a spanning subgraph which is a cycle, while every such cycle is referred to as a Hamiltonian cycle. Similarly, every spanning path is referred to as a Hamiltonian path.
There is a significantly large number of bounds for the algebraic connectivity expressed in terms of other graph invariants. One of them is a classical result of Mohar [8] stating that
\[a(G) \ge \frac{4}{dn},\tag{1}\]
where, as said above, d is the diameter of G. Some others can be found in [1, 4, 10]. In this study we obtain a lower bound for a(G) which relies on the assumption that G contains edge-disjoint spanning subgraphs such that the algebraic connectivity of each of them is not less than the algebraic connectivity of either a fixed path or a fixed cycle. This result yields the lower bound for a(G) expressed in terms of orders of the longest paths or cycles contained in the corresponding spanning subgraphs. In particular, we establish a lower bound when G contains the set of edge-disjoint Hamiltonian paths and cycles.
Our contribution is reported in the forthcoming sections. Precisely, theoretical results are given in Section 2, a concluding discussion is given in Section 3, while in the Appendix we observe the existence of an upper bound for the algebraic connectivity (which is implicitly proved in [2]).
2. Results
We use the following lemma referred to Fiedler.
Lemma 2.1. [5] Let \(G_1, G_2, \ldots, G_k\) be edge-disjoint spanning subgraphs of a non-trivial signed graph G such that \(m(G) = \sum_{i=1}^k m(G_i)\). Then
\[a(G) \ge \sum_{i=1}^{k} a(G_i).\]
We also use the following limit point without reference:
\[\lim_{x \to 0} \left( \frac{\sum_{i=1}^{k} t_i^x}{k} \right)^{\frac{1}{x}} = \left( \prod_{i=1}^{k} t_i \right)^{\frac{1}{k}}, \tag{2}\]
for positive \(t_1, t_2, \ldots, t_k\).
Theorem 2.1. Assume that a graph G with n (\(n \ge 2\)) vertices contains edge-disjoint spanning subgraphs \(G_1, G_2, \ldots, G_q\) such that for \(1 \le i \le p\) it holds \(a(G_i) \ge a(P_{n_i})\) with \(n_i \ge 2\) and for \(p+1 \le i \le q\) it holds \(a(G_i) \ge a(C_{n_i})\). Then
\[a(G) > \frac{\pi^2}{3} \left( p \frac{12\overline{g}(n_1, n_2, \dots, n_p)^2 - \pi^2}{4\overline{g}(n_1, n_2, \dots, n_p)^4} + 4(q - p) \frac{3\overline{g}(n_{p+1}, n_{p+2}, \dots, n_q)^2 - \pi^2}{\overline{g}(n_{p+1}, n_{p+2}, \dots, n_q)^4} \right), \quad (3)\]
where \(\overline{q}\) denotes the geometric mean of given arguments.
Proof. By Lemma 2.1, \(a(G) \ge \sum_{i=1}^q a(G_i)\), i.e., \(a(G) \ge \sum_{i=1}^p a(P_{n_i}) + \sum_{i=p+1}^q a(C_{n_i})\). It holds \(a(P_{n_i}) = 2(1 - \cos(\frac{\pi}{n_i}))\) and \(a(C_{n_i}) = 2(1 - \cos(\frac{2\pi}{n_i}))\); see, for example, [1].
Using the Taylor series, we get
\[a(P_{n_i}) > 2\left(1 - 1 + \frac{\pi^2}{2n_i^2} - \frac{\pi^4}{24n_i^4}\right) = \frac{\pi^2}{12n_i^4}(12n_i^2 - \pi^2)\]
and
\[a(C_{n_i}) > 2\left(1 - 1 + \frac{4\pi^2}{2n_i^2} - \frac{16\pi^4}{24n_i^4}\right) = \frac{4\pi^2}{3n_i^4}(3n_i^2 - \pi^2)\]
that gives
\[a(G) > \frac{\pi^2}{3} \left( \frac{1}{4} \sum_{i=1}^p \frac{12n_i^2 - \pi^2}{n_i^4} + 4 \sum_{i=p+1}^q \frac{3n_i^2 - \pi^2}{n_i^4} \right). \tag{4}\]
We consider the first sum of (4). For \(\alpha \geq 2\), we define the function
\[f_{\alpha}(x) = \frac{12x^{\alpha} - \pi^2}{x^{2\alpha}}.\]
It holds \(f_{\alpha}''(x) = \frac{2a}{x^{2(\alpha+1)}} (6(\alpha+1)x^{\alpha} - \pi^2(2\alpha+1))\), and so, for \(x \geq 2\), \(f_{\alpha}\) is convex. Using the Jensen's inequality, we get
\[\sum_{i=1}^{p} \frac{12n_i^2 - \pi^2}{n_i^4} \ge p f_{\alpha} \left( \frac{\sum_{i=1}^{p} n_i^{2/\alpha}}{p} \right) = p \frac{12 \left( \frac{\sum_{i=1}^{p} n_i^{2/\alpha}}{p} \right)^{\alpha} - \pi^2}{\left( \frac{\sum_{i=1}^{p} n_i^{2/\alpha}}{p} \right)^{2\alpha}}.\]
If \(\alpha \to \infty\), by (2), we have
\[\sum_{i=1}^{p} \frac{12n_i^2 - \pi^2}{n_i^4} \ge p \frac{12\overline{g}(n_1, n_2, \dots, n_p)^2 - \pi^2}{\overline{g}(n_1, n_2, \dots, n_p)^4}.\] (5)
The second sum of (4) is considered in a similar way. For \(\alpha \geq 3\), we define the function
\[h_{\alpha}(x) = \frac{3x^{\alpha} - \pi^2}{x^{2\alpha}},\]
which is convex for \(x \geq 3\) (as \(h''_{\alpha}(x) = \frac{a}{x^{2(\alpha+1)}} \left(3(\alpha+1)x^{\alpha} - 2\pi^2(2\alpha+1)\right)\)). This leads to
\[\sum_{i=p+1}^{q} \frac{3n_i^2 - \pi^2}{n_i^4} \ge (q-p)h_{\alpha}\left(\frac{\sum_{i=p+1}^{q} n_i^{2/\alpha}}{q-p}\right) = (q-p)\frac{3\left(\frac{\sum_{i=p+1}^{q} n_i^{2/\alpha}}{(q-p)}\right)^{\alpha} - \pi^2}{\left(\frac{\sum_{i=p+1}^{q} n_i^{2/\alpha}}{q-p}\right)^{2\alpha}}.\]
Letting \(\alpha \to \infty\), we get
\[\sum_{i=p+1}^{q} \frac{3n_i^2 - \pi^2}{n_i^4} \ge (q-p) \frac{3\overline{g}(n_{p+1}, n_{p+2}, \dots, n_q)^2 - \pi^2}{\overline{g}(n_{p+1}, n_{p+2}, \dots, n_q)^4}.\] (6)
The inequality (4), in conjunction with (5) and (6), gives (3).
Here are some consequences.
Corollary 2.1. Under the assumptions of Theorem 2.1, we have
\[a(G) > \frac{\pi^2}{3} \left( p \frac{12\overline{a}(n_1, n_2, \dots, n_p)^2 - \pi^2}{4\overline{a}(n_1, n_2, \dots, n_p)^4} + 4(q - p) \frac{3\overline{a}(n_{p+1}, n_{p+2}, \dots, n_q)^2 - \pi^2}{\overline{a}(n_{p+1}, n_{p+2}, \dots, n_q)^4} \right), \quad (7)\]
where \(\overline{a}\) denotes the arithmetic mean of given arguments.
Proof. The function \(\frac{12x^2-\pi^2}{4x^2}\) decreases for \(x \geq 2\), and so
\[\frac{12\overline{g}(n_1, n_2, \dots, n_p)^2 - \pi^2}{4\overline{g}(n_1, n_2, \dots, n_p)^4} \ge \frac{12\overline{a}(n_1, n_2, \dots, n_p)^2 - \pi^2}{4\overline{a}(n_1, n_2, \dots, n_p)^4}.\]
Similarly, as \(\frac{3x^2-\pi^2}{x^2}\) decreases for \(x \geq 3\), we have
\[\frac{3\overline{g}(n_{p+1}, n_{p+2}, \dots, n_q)^2 - \pi^2}{\overline{g}(n_{p+1}, n_{p+2}, \dots, n_q)^4} \ge \frac{3\overline{a}(n_{p+1}, n_{p+2}, \dots, n_q)^2 - \pi^2}{\overline{a}(n_{p+1}, n_{p+2}, \dots, n_q)^4},\]
and the proof follows.
Corollary 2.2. Under the assumptions of Theorem 2.1, we have
\[a(G) > q\pi^2 \frac{12\overline{g}(n_1, n_2, \dots, n_q)^2 - \pi^2}{12\overline{g}(n_1, n_2, \dots, n_q)^4} \ge q\pi^2 \frac{12\overline{a}(n_1, n_2, \dots, n_q)^2 - \pi^2}{12\overline{a}(n_1, n_2, \dots, n_q)^4},\] (8)
where \(\overline{g}\) and \(\overline{a}\) denote the geometric mean and the arithmetic mean of given arguments, respectively.
Proof. In the notation of Theorem 2.1, since \(a(C_{n_i}) > a(P_{n_i})\), we have \(a(G_i) \geq a(P_{n_i})\), for \(1 \leq i \leq q\). The first inequality follows by setting p = q in (3), and then the second follows by the previous corollary.
We proceed with the following particular result.
Theorem 2.2. If a non-trivial graph G contains p Hamiltonian paths and q-p Hamiltonian cycles, such that all of them are edge disjoint, then
\[a(G) > \pi^2 \frac{12(4q - 3p)n^2 - (16q - 15p)\pi^2}{12n^4}.\] (9)
Proof. Obviously, G contains edge-disjoint spanning subgraphs \(G_1, G_2, \ldots, G_q\) such that the first p of them contain a Hamiltonian path and the remaining ones contain a Hamiltonian cycle. By Lemma 2.1, the algebraic connectivity of \(G_i\) is at least the algebraic connectivity of its spanning subgraph, i.e., all the assumptions of Theorem 2.1 are satisfied (with \(n_i = n\), for \(1 \le i \le q\)). By (3), we compute
\[a(G) > \frac{\pi^2}{3} \left( p \frac{12n^2 - \pi^2}{4n^4} + 4(q - p) \frac{3n^2 - \pi^2}{n^4} \right),\]
giving the desired inequality.
Since, for a connected graph G, we have \(a(G) \geq 2\epsilon(1-\cos\frac{\pi}{n})\) (see [5]), where \(\epsilon\) denotes the edge connectivity of G, it follows that Theorem 2.1 can be applied to any connected non-trivial graph with itself in the role of the unique spanning subgraph. Here is another criterion concerning graphs with small diameter.
Theorem 2.3. If a connected graph G with n \((n \ge 2)\) vertices and diameter d contains a path \(P_k\) (resp. a cycle \(C_k\)) such that \(4k^2 \ge dn\pi^2\) (resp. \(k^2 \ge dn\pi^2\)), then \(a(G) > a(P_k)\) (resp. \(a(G) > a(C_k)\)).
Proof. We use the inequality (1). Considering the existence of a path \(P_k\), we get
\[a(G) \ge \frac{4}{dn} \ge \frac{4}{\frac{4k^2}{\pi^2}} = \frac{\pi^2}{k^2} = 2\left(1 - 1 + \frac{\pi^2}{2k^2}\right) > 2\left(1 - \cos\frac{\pi}{k}\right).\]
The existence of a cycle satisfying the assumption of the theorem is considered in the same way. \(\Box\)
3. Remarks
The bound (3) and its consequences (7)–(9) are always non-trivial, in the sense that they are never negative. An easy consequence of (9) is the following lower bound
\[a(G) > 4q\pi^2 \frac{3n^2 - \pi^2}{3n^4},\tag{10}\]
where q stands for the number of edge-disjoint Hamiltonian cycles. In general, the bound (10) is incomparable with (1), but it gives a better estimate whenever
\[q \ge \frac{3n^3}{d\pi^2(n^2 - \pi^2)}. (11)\]
In particular, this occurs for every Hamiltonian graph with \(d \ge \frac{3n^3}{\pi^2(3n^2-\pi^2)}\), as then the right hand side of (11) is at most 1; this lower bound for d is asymptotically \(n/\pi^2\).
Example 1. Consider the graph G obtained by inserting an edge between every pair of vertices at distance 2 of a cycle \(C_{2k+1}\), for \(k \ge 2\). Obviously, G has exactly 2 edge-disjoint Hamiltonian cycles, and thus due to (10) we have \(a(G) > 8\pi^2 \frac{3(2k+1)^2 - \pi^2}{3(2k+1)^4}\). Say, for k = 4, we get \(2.12 \approx a(G) > 0.94\).
As the right hand side of (10) increases with the number of edge-disjoint Hamiltonian cycles, it would be natural to consider it in conjunction with a lower bound for the number of such cycles. In this context, we recall that Nash-Williams proved that the assumptions of the well-known Dirac's theorem guarantee the existence of many edge-disjoint Hamiltonian cycles. Precisely, every graph with n vertices and minimum vertex degree at least n/2 contains at least \(\lfloor 5n/224 \rfloor\) edge-disjoint Hamiltonian cycles [9]. It is conjectured in the same reference that every r-regular graph with at most 2r vertices contains r/2 Hamiltonian cycles. This conjecture is still open; an approximate version stating that every r-regular graph with n (\(14 \le n \le 2r+1\)) vertices contains \(\lfloor (3r-n+1)/6 \rfloor\) edge-disjoint Hamiltonian cycles is proved by Jackson [7]. For some asymptotic results, we refer to Christofides, Kühn and Osthus [3]. Particular constructions of arbitrarily large graphs with a specified number of Hamiltonian cycles can be found in Haythorpe's [6].
Acknowledgements
Research is partially supported by the Serbian Ministry of Education, Science and Technological Development via the University of Belgrade.
References
- [1] N.M.M. de Abreu, Old and new results on algebraic connectivity of graphs, Linear Algebra Appl., 423 (2007), 53–73.
- [2] B. Bollobás and V. Nikiforov, Graphs and Hermitian matrices: eigenvalue interlacing. Discrete Math. 289 (2004), 119–127.
- [3] D. Christofides, D. Kühn and D. Osthus, Edge-disjoint Hamilton cycles in graphs, J. Combin. Theory B, 102 (2012), 1035–1060.
- [4] K.Ch. Das, Proof of conjectures involving algebraic connectivity of graphs, Linear Algebra Appl., 438 (2013), 3291–3302.
- [5] M. Fiedler, Algebraic connectivity of graphs, Czech. Math. J., 23 (1973), 298–305.
- [6] M. Haythorpe, Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles, Electron. J. Graph Theory Appl., 4 (1) (2016), 18–25.
- [7] B. Jackson, Edge-disjoint Hamilton cycles in regular graphs of large degree, J. London Math. Soc., 19 (1979), 13–16.
- [8] B. Mohar, Eigenvalues, diameter, and mean distance in graphs, Graph Combinator., 7 (1991), 53–64.
- [9] C.St.J.A. Nash-Williams, Edge-disjoint Hamiltonian circuits in graphs with vertices of large valency, in: L. Mirsky (Ed.), Studies in Pure Mathematics, Academic Press, 1971, pp. 157– 183.
- [10] A.A. Rad, M. Jalili, and M. Hasler, A lower bound for algebraic connectivity based on the connection-graph-stability method, Linear Algebra Appl., 435 (2011), 186–192.
Appendix
We recall an interesting upper bound, obtained by Bollobas and Nikiforov [2], for the sum of ´ the k − 1 least eigenvalues of a Hermitian matrix. Namely, if N1 t N2 · · · t Nk is a partition of a Hermitian matrix M = (mij ) with eigenvalues ν1 ≥ ν2 ≥ · · · ≥ νn, then
\[\sum_{p=n-k+2}^{n} \nu_p \le \sum_{p=1}^{k} \frac{1}{|N_p|} \sum_{(i,j): i,j \in N_p} m_{ij} - \frac{1}{n} \operatorname{sum}(M), \tag{12}\]
where sum(M) denotes the sum of the entries of M.
By considering the Laplacian matrix of a graph in the role of M and inserting k = 3 in (12), we get
\[a(G) \le \sum_{p=1}^{3} \frac{c(N_p)}{|N_p|},\] (13)
where, clearly N1 t N2 t N3 is a vertex set partition, while c(Np) denotes the cut of Np, i.e., the number of edges with exactly one end in Np. Indeed, if L = (lij ) is the Laplacian matrix, then P (i,j) :i,j∈Np lij = c(Np) and sum(L) = 0, so we get (13). This upper bound can be used to estimate the algebraic connectivity of graphs with given tripartition of a vertex set. For example, if G contains at least two cut-edges, then we have
\[a(G) \le \frac{1}{|N_1|} + \frac{2}{|N_2|} + \frac{1}{|N_3|},\]
where cut-edges are located between N1 and N2, and N2 and N3.