A -bipartite graph is a bipartite graph such that one bipartition has m vertices and the other bipartition has n vertices. The tree dumbbell consists of the path together with a independent vertices adjacent to one pendent vertex of and b independent vertices adjacent to the other pendent vertex of . In this paper, firstly, we show that, among -bipartite graphs , the complete bipartite graph has minimal Kirchhoff index and the tree dumbbell has maximal Kirchhoff index. Then, we show that, among all bipartite graphs of order , the complete bipartite graph has minimal Kirchhoff index and the path has maximal Kirchhoff index, respectively. Finally, bonds for the Kirchhoff index of -bipartite graphs and bipartite graphs of order are obtained by computing the Kirchhoff index of these extremal graphs.
As an analogy to the famous Wiener index, the Kirchhoff index is an important molecular structure descriptor , and thus it is well studied in both mathematical and chemical literatures. For more information on the Kirchhoff index, the readers are referred to recent papers [5–16] and references therein.
where the first equality holds if and only if is a complete graph and the second does if and only if is a cycle. Furthermore, tight bounds for the Kirchhoff index are also obtained for a special class of unicyclic graphs , bicyclic graphs [21, 22], and Cacti .
Bipartite graphs are perhaps the most basic of objects in graph theory, both from a theoretical and practical point of view. Let be a bipartite graph with bipartition and such that is the set of white vertices and is the set of black vertices. Suppose that and . Such graph is also known as -bipartite graph. Without loss of generality, we supposed that . The tree dumbbell consists of the path together with independent vertices adjacent to one pendent vertex of and independent vertices adjacent to the other pendent vertex of . For instance, is referred to Figure 1.
In the next section, we first obtain that has the minimal Kirchhoff index among all -bipartite graphs according to strictly increasing property of the Kirchhoff index. Then we prove that tree dumbbell has maximal Kirchhoff index among all -bipartite graphs. Therefore, tight bounds for the Kirchhoff index of -bipartite graphs are determined. In the last section, we discuss general bipartite graphs of order . We obtain that, among all bipartite graphs of order , complete bipartite graph and path have minimal and maximal Kirchhoff index, respectively. Thus bounds for the Kirchhoff index of bipartite graphs of order are also obtained.
Lemma 2.1 (see ). Let be a connected graph with vertices and a connected spanning subgraph of . Then, with equality if and only if .
By Lemma 2.1, the complete bipartite graph has minimal Kirchhoff index among all -bipartite graphs. Now, we compute the Kirchhoff index of .
In the following, we search for -bipartite graph with maximal Kirchhoff index. By Lemma 2.1, the graph possesses maximal Kirchhoff index must be a tree since otherwise any of its spanning tree has lager Kirchhoff index than it. It is well known that the Kirchhoff index and the Wiener index concise for trees. Hence, we only need to consider the Wiener index which has been extensively studied. Now, we introduce some well-known results on the Wiener index of trees.
Let and denote -vertex path and -vertex star, respectively. Then we have the following.
In the following, we let .
Theorem 2.5. has maximal Kirchhoff index among all -bipartite graphs.
Proof. Suppose that is the tree possessing maximal Wiener (Kirchhoff) index among all -bipartite graphs.
Case 1. or . In this case, is the path . By Lemma 2.3, the result holds.Case 2. . Let be a longest path in with end vertices and . Suppose that and are neighbors of and in , respectively.Claim 1. The inner vertices of all have degree 2 in except for and .
Suppose to the contrary that there exists an inner point of different from and has degree lager than 2 and is a neighbor of such that . Suppose that the size of the component of containing is . Suppose that and are edges in incident to . Let , , and denote the components of containing , , and , respectively. We choose from and the one containing less vertices, say . and must have one that belongs to the part containing , say . Let (see Figure 2). Now we show that by considering the contributions of edges. Obviously, . Let denote the edge set of , and let denote the path . For , . For , suppose that and are components of containing and , respectively. Then, and . Then, Hence, This contradicts the choice of .Claim 2. Both and belong to .
Suppose not. Then, we can distinguish the following two cases.Subcase 1. Both and belong to . By Claim 1, the inner vertices of all have degree 2 in ; hence, the vertices of all belong to , that is, , a contradiction.Subcase 2. and belong to different parts. Suppose that belongs to . By claim 1 and , we have . Let (see Figure 3). Now, we show that . Obviously, . Let denote the edge set of , and let denote the path . For , . Suppose that the edges of are such that is adjacent to for . It is easy to see that and for . What is left is to compare with . and . Then, since and with equality if and only if and are adjacent. Hence, . Thus, As before, this contradicts the choice of .Claim 3. The length of is .
By Claims 1 and 2, the vertices of are all contained in , the end vertices of are both contained in . Hence the length of is as claimed.Claim 4. . Suppose to the contrary that . Without less of generality, suppose that . Let . We can prove that by methods similar to the proof of Claim 2.
By Claims 1, 2, 3, and 4, we may conclude that , which implies Theorem 2.5.
Figure 2: (a) and (b) in the proof of Claim 1.
Figure 3: (a) and (b) in the proof of Subcase 2 of Claim 2.
Now, we compute the Kirchhoff (Wiener) index of . For convenience, in what follows, we denote by .
In sum, we have our main result.
Theorem 2.6. For -bipartite graph , we have The first equality holds if and only if , and the second does if and only if .
Hence, we have the following result.
Theorem 3.1. For bipartite graph of order , we have The first equality holds if and only if , and the second does if and only if .
This work is supported by NSFC (Grant no. 11126255).