Abstract
Let G be a connected graph and let L(G) be its Laplacian matrix. We show that given a graph G with a point of articulation u, and a spanning tree T , there is a way to give weights to the edges of G, so that u is the characteristic vertex and the monotonicity property holds on T . A restricted graph is a graph with a restriction that each block can have at most two points of articulation. We supply the structure of a restricted graph G whose algebraic connectivity is extremized among all restricted graphs with the same blocks as those of G. Further results are supplied when each block of G is complete. A path bundle is a graph that consists of internally vertex disjoint paths of the same length with common end vertices. Results pertaining to extremizing the algebraic connectivity of restricted graphs whose blocks are path bundles are supplied. As an application, a comparison of the algebraic connectivities of the sunflower graphs is provided.
Introduction
Let G = (V (G), E(G)), in short G, denote a simple graph and unless specified otherwise, V (G) = {1, . . . , n}. An edge between vertices u and v is denoted by uv. We write u ∼ v to mean that uv ∈ E(G). The adjacency matrix A(G) = [a ij ] of G is a matrix with a ij = 1 if i ∼ j a decreasing, or a zero sequence along P according to whether y(k) > 0, y(k) < 0 or y(k) = 0; in the last case P is a zero path.
Introduction
Case B: No block of G contains both positive and negative vertices. In this case, there exists a unique characteristic vertex z. This vertex z is a point of articulation. Each block (with the exception of z) is either a positive block, or a negative block, or a zero block. Let P be a pure path which starts at z. Then the valuations at the points of articulation (with the exception of z) either increase and remain positive, or decrease and remain negative, or are zero; in the last case P is a zero path. Every path containing both positive and negative vertices passes through z. A natural question is the following: Can we have 'monotonicity along the path' instead of 'monotonicity along the points of articulation on the path' ? The answer to this is 'No, not for every path.' For example, the pure path shown in the top graph of Figure 2 does not have monotonicity. In view of Proposition 2.2, C(G, y) is either a singleton vertex or is contained in a unique block of G. This block is called the characteristic block of G. Let C * (y) denote the characteristic set if Case B of Proposition 2.2 holds and the characteristic block if Case A of Proposition 2.2 holds. Let v be any positive vertex outside C * (y). Then there is a pure path from a vertex of C * (y) to v. As observed in the top picture in Figure 2 , there may not be monotonicity along this path, though by Proposition 2.2, there is monotonicity along the points of articulation on this path. So a natural question is does there exist a path from a vertex of C * (y) to v along which monotonicity holds? For example, the bottom picture in Figure 2 gives one such path. We are interested in a path along which strict monotonicity holds.
Introduction
Let W be a nonempty subset of V (G). A branch at W is a connected component of G − W . Note that answers to the following questions are already known (see for example [1] Lemma 2.3 Let y be a Fiedler vector of a connected graph G and let k ∈ C * (y). Suppose B is a branch at k not containing any vertex of C * (y) and u is a positive vertex in B. Then there exists a path
Introduction
Proof. A proof follows by repeated application of Corollary 3.10 of [7] .
Introduction
Theorem 2.4 Let y be a Fiedler vector of a connected graph G. Then there is a spanning subgraph H of G containing C * (y) such that H − C * (y) is a forest. Furthermore, each path P in H which starts from a vertex k ∈ C * (y) and does not contain any other vertex of C * (y) satisfies exactly one of the following properties.
Introduction
(a) The valuation along P is strictly increasing.
Introduction
(b) The valuation along P is strictly decreasing.
Introduction
(c) The valuation along P is identically zero.
Introduction
Proof. The proof is based on creating the subgraph H. Start with H = C * (y). Let k ∈ C * (y) and let B be a branch of G at k not containing any vertex of C * (y).
Introduction
Suppose B is a positive branch and u ∈ B. Then by Lemma 2.3, there is a strictly decreasing path from u to k. We add this path to H. If there is a vertex w ∈ B − H, then again by Lemma 2.3, there is a strictly decreasing path P from w to k. While traversing from w, select the part of P from w to the first vertex of H. We add this part to H. We repeat the process till each vertex of B is in H.
Introduction
A similar argument holds if B is either a negative branch or a zero branch. We apply this technique at other branches to obtain a spanning subgraph H. Note that H has the desired property at any stage of the construction.
Introduction
Remark 2.5 Note that G has the following property: if u is a positive (negative or zero) vertex outside C * (y), then there is at least one strictly decreasing (strictly increasing or zero) path from u to a vertex of C * (y) in the graph. The graph H in Theorem 2.4 may also be constructed by deleting sequentially a few edges of G that are outside C * (y), ensuring that the resulting graph at each stage has the specified property.
Introduction
Let G be the graph in Figure 3 . The valuations with respect to a Fiedler vector (obtained using the mathematical package MATLAB) are written near each vertex. By deleting the 'dashed edges' we get a graph H satisfying Theorem 2.4. 
Remark 2.6
In general, there may be many subgraphs H satisfying Theorem 2.4. So it is natural to seek a family of graphs for which there is exactly one such subgraph. Note that the graph in Figure 1 on page 3 is an example that has essentially one subgraph H, in the sense that all other choices of H are isomorphic copies. Two special properties of that graph are the following.
Remark 2.6
(a) Each of its blocks has at most two points of articulation, thus generalizing a tree. A graph with this restriction on the blocks will be called a restricted graph.
Remark 2.6
(b) Each of its blocks is made up of internally vertex disjoint paths of the same length with common end vertices. Such blocks will be called path bundles. 
Remark 2.6
and w ij is the weight of the edge ij in G.
Remark 2.6
Let W be a nonempty subset of V (G) and let B be a branch of G at W . The principal submatrix of L(G) corresponding to B is denotedL(B). It is well known (see [9] ) thatL(B) −1 is entrywise positive and by the Perron-Frobenius theory, the spectral radius, denoted ρ(L(B) −1 ), is a simple eigenvalue and it is afforded by an entrywise positive eigenvector. We call ρ(L(B) −1 ) the Perron value of the branch B.
Remark 2.6
It is known (see [1, Lemma 6] ) that if W = {u}, then a Perron branch B at u is nothing but a branch of maximum Perron value.
Remark 2.6
Theorem 2.8 Let k be a point of articulation of a connected graph G and let T be a spanning tree of G. Then there is an assignment of weights to the edges of G such that k is the characteristic vertex of G and T is the spanning tree as mentioned in Theorem 2.4.
Remark 2.6
Proof. First assume that B 1 and B 2 are the only branches of G at k. LetG be obtained from G by assigning a weight α (value of α shall be specified later) to each edge in E(G) \ E(T ). LetB 1 andB 2 be the corresponding branches ofG at
Remark 2.6
). Now multiply each edge of the induced subgraph ofG on the vertices V (B 2 ) ∪ {k} by β.
Remark 2.6
Let G ′ be the new weighted graph. Let B ′ 1 and B ′ 2 be the corresponding branches of
Remark 2.6
). Thus, it follows that (see for example [11] ) the vertex k is still the characteristic vertex of G ′ and a(G ′ ) is simple. Let y be a Fiedler vector of G ′ . In view of −y, let B ′ 1 be the positive branch. Let r ∈ B 1 and consider the path P = [r, s, . . . , k] in T . We shall show that y(s) < y(r). Note that T − rs has two components, say T r and T s , containing r and s, respectively. Define the vector x by x(i) = 1 if i ∈ T r and x(i) = 0, otherwise. Then, the entries of x T L(G ′ ) are given as follows:
Remark 2.6
Considering only those edges that have one end in T s and the other in T r , we have
Remark 2.6
as no vertex of B ′ 2 is adjacent to a vertex of T r and vertices in B ′ 1 are nonnegative. As the left hand side term is positive, one has y(s) < y(r) if there is a choice of α satisfying nα < a(G ′ ). Towards this, let T 1 , . . . , T p be the branches of T at k which are contained in
Remark 2.6
where T is the weighted subgraph of G ′ . Now imagine removing the non-tree edges from B ′ 1 . In this process, the smallest eigenvalue
Remark 2.6
where τ (L(T 1 )) is independent of α and β as α was assigned to each edge of E(G) \ E(T ) and β was multiplied to the weight of each edge in the induced subgraph V (B 2 ) ∪ {k} ofG. Hence our selection of α is possible. Now to see that the monotonicity holds in B ′ 2 , multiply the whole matrix by
Remark 2.6
2 has a weight 1 for the tree-edges and a weight α for the non-tree edges.
Remark 2.6
The argument for the general case when there are more than two branches at k can be handled with a slight modification and hence is omitted.
Minimizing algebraic connectivity
It is well known that among all trees on n vertices the path has the minimum algebraic connectivity. In this section, we shall supply a similar result for a more general case, namely for the connected restricted graphs. Let G be a connected restricted graph with blocks B 1 , . . . , B k . Replace the block B i by a path P i = [u i , v i ] on two vertices such that 'B i , B j have a common vertex if and only if P i , P j have a common vertex'. The resulting graph is a tree which we call the block structure of G (see Figure 5 for a restricted graph and its block structure). Thus the block structure of a tree is itself. In the subsequent part of this section, we address the following question: suppose one is not allowed to change the blocks but is allowed to change the structure, keeping in mind that each block still has at most two points of articulation. Can one say that the algebraic connectivity will be minimized for a graph whose block structure is a path?
Minimizing algebraic connectivity
The answer is affirmative. Let us recall some known results. We denote the all ones matrix by J. 
Minimizing algebraic connectivity
Remark 3.2 We can add one more line to the replacement lemma whose verification is similar. "Form a new graphG by replacing C with a graphC at v.
Minimizing algebraic connectivity
." This holds as the Perron branches at v which were not contained in C will remain as Perron branches at v forC and we apply the replacement lemma toG.
Minimizing algebraic connectivity
We use A(:, i) to mean the ith column and A(i, :) to mean the ith row of A. Also, A ≪ B means that B − A is a nonnegative matrix with at least one positive entry. 
Minimizing algebraic connectivity
Lemma 3.5 (Shifting) Let G 0 , G 1 , G 2 and F be connected graphs on vertices 0, 1, . . . , n; n, n + 1, . . . , k; k, k + 1, . . . , r; and n, r + 1, r + 2, . . . , s, respectively. Let F * be the graph obtained from F by renaming the vertex n to k (see Figure 6 ). Then Proof. By Proposition 3.3, one needs to compare the entries corresponding to u ∈ F − n. Put
Minimizing algebraic connectivity
Then using Proposition 3.3, we obtain the following inequalities.
Minimizing algebraic connectivity
•
Minimizing algebraic connectivity
Thus, using the above inequalities, the proof of the lemma is over.
Minimizing algebraic connectivity
Remark 3.6 Lemma 3.5 is also valid when we move the branch from 0 to n or from k to r. The proof is similar in nature. Roughly the shifting lemma says that if we move a block away from the root (vertex 0), the Perron value of the branch increases.
Minimizing algebraic connectivity
We now give our main result of this section.
Minimizing algebraic connectivity
Theorem 3.7 Let G be a connected restricted graph. Then there is a restricted graph H having the same blocks as that of G and whose block structure is a path such that a(H) ≤ a(G).
Minimizing algebraic connectivity
Proof. If G has at most two blocks, then the block structure is a path and there is noting to prove. Assume that the block structure of G is not a path. That is, G has at least three blocks. Suppose that Case A of Proposition 2.2 holds. Let C be the characteristic block and v be a point of articulation of C. Let B 1 , . . . , B j be the branches at v which do not contain any vertex of C. Applying shifting lemma repeatedly, all these branches can be replaced by a single branch B with the same blocks such that the block structure is a path. AsL(B) −1 ≥L(∪B i ) −1 , using the replacement lemma, it follows that the resulting graph F satisfies a(F ) ≤ a(G). Consider G again. If C does not have another point of articulation our proof is over. Assume that C has one more point of articulation, say u. By using Proposition 1.4 of [5] (see also [9] ), the branch at u which contains other elements of C is the Perron branch. Therefore, the branch at u of F that contains other elements of C is also the Perron branch. Let D 1 , . . . , D k be the branches at u of F which do not contain any vertex of C. We replace these branches by a single branch D with the same blocks such that the block structure is a path. Let the resulting graph be H. By shifting lemma,L(D) −1 ≥L(∪D i ) −1 . Thus, by replacement lemma, a(H) ≤ a(F ). This completes the proof of the theorem for Case A.
Minimizing algebraic connectivity
The argument for Case B of Proposition 2.2 is similar and omitted.
Minimizing algebraic connectivity
Next, we consider maximization of algebraic connectivity. Using repeatedly Remark 3.2 on page 8, we get the following result.
Minimizing algebraic connectivity
Theorem 3.8 Let G be a connected restricted graph with the block structure a tree of diameter at least four. Then there is a graph H having the same blocks as that of G and with the block structure a tree of diameter three such that a(H) ≥ a(G).
Block graphs
Recall that a block graph is a graph each of whose blocks is complete. Let G be a block graph. Consider all restricted graphs whose blocks are precisely the blocks of G. By Theorem 3.7, the algebraic connectivity will be minimized by a graph H whose block structure is a path. In this section we provide some further information about H. We require the following easily verifiable observations.
Block graphs
Let G 1 , G 2 , . . . , G k be complete graphs with vertex sets {0, . . . , n 1 }, {n 1 , n 1 + 1, . . . , n 2 }, . . ., {n k−1 , n k−1 + 1, . . . , n k }, respectively. Take a connected graph H on vertices n k , n k + 1, . . . , n and put 
Proposition 4.3 Let s
Proof. Rename the vertices of G s 1 ,s 2 ,H and G s 2 ,s 1 ,H so that they look as shown in Figure 8 . Also, let us write Then by Propositions 3.3 and 4.1, the matrix M is given by
Proposition 4.3 Let s
As s 2 > s 1 , the following statements can be easily verified.
Proposition 4.3 Let s
• Let 1
Proposition 4.3 Let s
• If i = s 1 − 1 and
Proposition 4.3 Let s
• Now suppose that
Proposition 4.3 Let s
• Finally, if s 1 + s 2 − 2 ≤ i and j ≥ i then m ij = n ij .
Proposition 4.3 Let s
Hence, the proof is completed by noting that M and N are symmetric.
Proposition 4.3 Let s
Theorem 4.4 Let k > 2 and fix positive integers s 1 , . . . , s k . Let G be a connected restricted graph with blocks K s 1 , . . . , K s k . Then among all such graphs the algebraic connectivity is minimized for a graph H whose block structure is a path. Furthermore, the sizes of the blocks in H increase as we move away from the characteristic set. The maximum algebraic connectivity among all such graphs is 1 and it is attained by the graphs whose block structure is a star.
Proposition 4.3 Let s
Proof. First let G be a graph whose block structure is a star. Now suppose that v is the point of articulation of G and let B be any branch at v. ThenL(B) = I + L(B). So τ (L(B)) = 1. As there are k > 2 branches, by interlacing, we see that a(G) = 1 with multiplicity at least k − 1. In fact we can say a little more. Using Proposition 4.2, it can be easily checked that the eigenvalues of G are as follows. Eigenvalues:
Proposition 4.3 Let s
Now, the proof of the minimization part is considered. In view of Theorem 3.7, let H = G p 1 ,...,p k , where p 1 , . . . , p k is an arrangement of s 1 , . . . , s k . We claim that an end block of H cannot be the characteristic block. To see this, let n 1 be the point of articulation of K p 1 and K p 2 and let B 1 and B 2 be the branches at n 1 containing points from K p 1 and K p 2 , respectively. As τ (L(B 1 )) = 1 and τ (L(B 2 )) < 1, B 2 is the only Perron branch at n 1 . So, by Corollary 1.1 of [9] , the characteristic block of H cannot be K p 1 . Similarly, K p k cannot be the characteristic block of H. Now, suppose that Case B of Proposition 2.2 holds and let v be the characteristic vertex of H. Then H − v has two components, say B (see Figure 9 , where the positive integers m 1 , m 2 , . . . , m r ∈ {s 1 , s 2 , . . . , s k }) and C. Apply Proposition 4.3 repeatedly to replace B by a branch B ′ with the same blocks such that the block structure remains a path and the block sizes increase as we move away from v. AsL(B) −1 ≤L(B ′ ) −1 , by Lemma 3.1, the resulting graph H ′ satisfies a(H ′ ) ≤ a(H). It follows that B ′ is a Perron branch of H ′ at v. We again apply Proposition 4.3 repeatedly to replace C by a branch C ′ with the same blocks such that the block structure remains a path and the block sizes increase as we move away from v. AsL(C) −1 ≤L(C ′ ) −1 , by Lemma 3.1, the graph H ′′ obtained by replacing C by C ′ in H ′ satisfies a(H ′′ ) ≤ a(H). This completes the proof for Case B.
Proposition 4.3 Let s
The proof for Case A of Proposition 2.2 being similar is omitted.
Restricted graphs whose blocks are path bundles
Consider the graphs G 1 and G 2 in Figure 10 on page 12. Here all the circles are of even girth and points of articulation are diametrically opposite points. The central dots are not part of the graphs. Let us ask the following question: which of the two graphs in Figure 10 has a smaller connectivity? Imagine rotating the graphs about their centers. We feel that the graph G 1 will break sooner than the graph G 2 . This is appropriately captured by their algebraic connectivities. In this section, we prove that a(G 1 ) ≤ a(G 2 ). Throughout this section, by P l,k we understand a graph made of k internally vertex disjoint paths of length l with the same end vertices. We keep the understanding that k = 1 if and only if l = 1. Thus P 3,3 is the graph in Figure 11 . Let G = G l 1 ,k 1 ;l 2 ,k 2 ;··· ;ls,ks denote the restricted graph with the properties a)-c) given below.
Restricted graphs whose blocks are path bundles
a) The block structure of G is a path. Note that the end vertex of B 1 (is always labeled with 0) and the end vertex of B s are not points of articulation. A path between them is called a top path in G. Thus the graph G = G 3,2;1,1;3,3;1,1 in Figure 12 has P = [0, 1, 2, . . . , 7, 8] as a top path. In the following, the labeling shown in Figure 12 will be used. Figure 10 . Imagine that the smaller cycles have girth 4, the medium sized cycles have girth 6 and the large ones have girth 8. Then G 1 has 4 copies of G 2,2;3,2;4,2 attached to the central cycle at vertices, say v 1 , v 2 , v 3 , v 4 . The graph G 2 is obtained from G 1 by replacing each copy of G 2,2;3,2;4,2 with G 4,2;3,2;2,2 . The fact that the central cycle is the characteristic block follows easily by noticing that the only Perron component of G 1 (resp. G 2 ) at v 1 is the one which contains more copies of G 2,2;3,2;4,2 (resp. G 4,2;3,2;2,2 ). So the task of comparing the algebraic connectivities of G 1 and G 2 reduces to comparing the Perron values of the bottleneck matricesL(G 2,2;3,2;4,2 − 0) −1 andL(G 4,2;3,2;2,2 − 0) −1 .
Restricted graphs whose blocks are path bundles
Then there is no permutation matrix P such that one of matrices A and P T BP entrywise dominates the other.
Restricted graphs whose blocks are path bundles
Proof. Using Proposition 3.4, a 11 = 1 − 1 2l 1 < b ii for each i. So, the only possibility can be A ≪ P T BP for some permutation matrix P .
Restricted graphs whose blocks are path bundles
To proceed further, let us say 'the vertex i of G dominates the vertex j of H' if a ii ≥ b jj . Put m = a l 1 l 1 and let k be a vertex in H farthest from 0 such that b kk ≤ m (see Figure 13) .
Restricted graphs whose blocks are path bundles
Note that |S| = 2l 1 − 1 and |T | is even. By Proposition 3.3, each vertex in T is strictly dominated by every vertex in S c (of G). Hence, the vertices in T can only dominate the vertices in S. Thus, |T | ≥ |S|. But as |T | is even and |S| is odd, we see that |T | ≥ |S| + 1. That is, if we consider the complements, then the number of vertices i in H with b ii > m is less than the number of vertices i in G with a ii > m. Hence, A cannot be dominated by P T BP as P T BP corresponds to a renaming of the vertices of H. 12 . Then L 12 x = τ 12 x. As the Perron value is simple, the symmetry in the path bundles implies that τ 12 is an eigenvalue of the compressed tridiagonal matrix A 12 that appears on Page 15. Indeed, taking y to be the subvector of x corresponding to the entries 1, . . . , l i , we have A 12 y = τ 12 y.
Restricted graphs whose blocks are path bundles
T is the Fiedler vector of the graph G obtained by merging two copies of G l 1 ,k 1 ;...,ls,ks at the vertex 0. Hence by Lemma 2.3, y(1) < y(2) < · · · < y( l i ).
Restricted graphs whose blocks are path bundles
Note that if l 1 = 1, then A 12 is the matrix shown in the dotted box. Put E p := e p + e p+1 + . . . + e n , where e i is the vector with ith entry 1 and 0, otherwise. Thus E 1 = 1 1.
Restricted graphs whose blocks are path bundles
12 , where B(:, 1) = E 1 and for p > 1
Restricted graphs whose blocks are path bundles
Proof b) ρ l 1 ,k 1 ;l 2 ,k 2 ;l 3 ,k 3 ;...;ls,ks ≥ ρ l 1 ,k 2 ;l 2 ,k 1 ;l 3 ,k 3 ;...;ls,ks if l 1 = l 2 and k 1 < k 2 .
Proof. Part a) Put
...;ls,ks . Note that for i < l 1 , C(:, i) = 0. Put 
Proof. Part a) Put
...;ls,ks − ρ l 1 +1,k 1 ;l 2 −1,k 2 ;l 3 ,k 3 ;...;ls,ks ]z T y.
Proof. Part a) Put
Thus, the proof of the first part is completed using the fact that z T y > 0.
Proof. Part a) Put
...;ls,ks . Note that for i < l 1 , C(:, i) = 0. Also
Proof. Part a) Put
Hence, C(:, l 1 + l 2 + i) ≥ 0, for all i. Thus, by Perron-Frobenius theory, we get the required result.
Proof. Part a) Put
Example 5.6 This is an application of Theorem 5.5 (a). Consider the graphs G and H in Figure 14 . By Theorem 5.5 (a), ρ(L(G − 0)) ≤ ρ(L (H − 0) ). Thus G * has larger algebraic connectivity than H * . 
The sunflowers
In this section, we answer the question asked at the beginning of Section 5. Fix a cycle C and vertices v 1 , . . . , v i on C, i ≥ 2. To each v l attach n l ≥ 1 copies of G = G l 1 ,2;...;ls,2 by identifying vertex 0 of each copy with v l . Let us call the resulting graph a sunflower S[C; v 1 , n 1 ; . . . ; v i , n i ; G]. We allow an exception when instead of a cycle C we take a single vertex u and attach k ≥ 2 copies of G to it. We also call it a sunflower S[u; k; G]. Kirkland and Neumann [10, Corollary 1] did some investigation on the location of the characteristic set. A more general investigation is stated below. Proposition 6.2 Let G and H be connected graphs on vertices g 1 , g 2 , . . . , g n and h 1 , h 2 , . . . , h m , respectively. Form a graph G * by attaching copies of H at g i 1 , g i 2 , . . . , g i k , k > 1, by identifying them with h 1 . Then the characteristic set of G * (with respect to any Fiedler vector) is always located in G.
The sunflowers
Proof. If G has only one vertex then G * has a characteristic vertex, namely g 1 . So assume that G has at least two vertices. Let G 1 be a branch of G * at g 1 isomorphic to H − h 1 and G 2 be another branch at g 1 which contains at least one vertex of G and the other copies of H. Then L(G 1 ) −1 is dominated by a principal submatrix ofL(G 2 ) −1 . Hence ρ(L(G 1 ) −1 ) ≤ ρ(L(G 2 ) −1 ). Using Corollary 15 of [1] , G 1 neither contains a characteristic vertex nor an end vertex of a characteristic edge.
The sunflowers
The following is an immediate consequence. Note that both the graphs shown in Example 6.1 are sunflowers. Assume that we are not to change the block sizes of G. We can still generate many sunflowers by choosing different arrangements of l 1 , . . . , l s . By Theorem 5.5 the sunflower for which l 1 ≤ l 2 ≤ · · · ≤ l s has the smallest algebraic connectivity and the sunflower for which l 1 ≥ l 2 ≥ · · · ≥ l s has the largest algebraic connectivity among all these sunflowers. In particular, in Figure 10 , the graph G 1 has smaller algebraic connectivity than that of G 2 .

{'paper_id': '18275008', 'title': 'On algebraic connectivity of graphs with at most two points of articulation in each block', 's2_url': 'https://api.semanticscholar.org/CorpusID:18275008', 'source': 'S2ORC'}