Electronic Journal of Graph Theory and Applications 7 .
, 365Ae372 Harary index of bipartite graphs Hanyuan Denga .
Selvaraj Balachandranb,c .
Suresh Elumalaid .
Toufik Mansourd College of Mathematics and Statistics.
Hunan Normal University.
Changsha.
Hunan 410081.
China b Department of Mathematics and Applied Mathematics.
University of the Free State.
Bloemfontein.
South Africa c Department of Mathematics.
School of Arts.
Sciences and Humanities.
SASTRA Deemed University.
Thanjavur.
India d Department of Mathematics.
University of Haifa, 3498838 Haifa.
Israel hydeng@hunnu.
cn, bala maths@rediffmail.
com, sureshkako@gmail.
com, tmansour@univ.
Abstract The sum of reciprocals of distance between any two vertices in a graph G is called the Harary We determine the n-vertex extremal graphs with the maximum Harary index for all bipartite graphs, a given matching number, a given vertex-connectivity, and with a given edge-connectivity.
Keywords: Harary index, bipartite graph, matching number, vertex-connectivity, edge-connectivity Mathematics Subject Classification : 05C15, 05C07, 05C50 DOI: 10.
5614/ejgta.
Introduction Throughout the paper let G be a connected graph with vertex set V (G) and the edge set E(G).
We denote the degree of a vertex x in G by dG .
We denote the distance of the shortest path between x, y 2 V (G) by dG .
, .
A simple bipartite graph G = (V1 .
V2 .
E), is the union of disjoint vertex partitions V1 and V2 , such that none of the edges in G have both the end vertices in one partition.
For every chosen two vertices from different partition in a bipartite graph are adjacent, then G is complete, denoted by Ka,b , where a = |V1 | and b = |V2 |.
Received: 18 October 2018.
Revised: 12 May 2019.
Accepted: 14 June 2019.
Harary index of bipartite graphs Hanyuan Deng et al.
A graph G is called k-connected if removing any set of k vertices from G, the result is a disconnected graph.
In this context, the connectivity of G, denoted by (G).
Similarly, a graph G is called G k 0 -edge-connected if removing any k 0 edges from G, the result is a disconnected graph.
Here, the edge-connectivity of G, denoted by 0 (G).
Let Akn .
Cns and Dnt denote the set of all n vertex bipartite graph with matching number k .
ee belo.
, connectivity s and edge-connectivity t, respectively.
Since 1947, the distance-based graph invariant Wiener index is received a lot of attention, it is defined as W (G) = dG .
, .
ueV (G) In an analogous way.
Harary index .
, .
defined as H(G) = .
ueV (G) dG .
, .
Xu .
determined the extremal results of Harary indices on trees.
Xu and Das .
characterized the extremal bicyclic and unicyclic graphs for H(G).
Xu et al.
found the maximal H(G) for a fixed matching number on unicyclic graphs .
or other example, see .
, 2, 3, 6, 7, 9, 10, 11, 12, 13, 15, 18, 19, .
and references cited therei.
Motivated by work of Li and Song .
, we determine the extremal graphs on n vertices with the maximum Harary index for all bipartite graphs with a given matching number, a given vertexconnectivity, and with a given edge-connectivity.
Harary index of bipartite graphs with a given matching number We start by the following lemma, which holds immediately from the definitions.
Lemma 2.
Let G be a simple graph with |V (G)| = n with G 6N = Kn .
Then for every edge e 2 E(G), where G is the complement of G.
H(G) < H(G .
In the next result, we present the extremal graph having the maximum H(G) for all bipartite graphs, for a fixed matching number.
Theorem 2.
Let G represents a bipartite graph with n vertices and matching number k.
Then Kk,n k is the unique graph with the maximum Harary index.
UInN Proof.
By choosing G in Akn , such that its H(G) is very large.
, then using Lemma 2.
UInN we get.
Kb n c,d n e is maximum.
So, we only consider k < 2 .
Let G = (A.
E) with |B| |A| k and M is the maximal matching in G.
If |A| = k then we see that G = Kk,n k is the extremal graph in G.
By Lemma 2.
H(G) increases by adding edges in G.
So, we can assume that |A| > k.
Let AM .
BM be the vertex subsets of A.
B which are incident to M .
Then |AM | = k and |BM | = k.
It is noted that there is no edge in G between the set A AM of vertices and the set Harary index of bipartite graphs Hanyuan Deng et al.
B BM of vertices.
If so, then the edges may be together with M to increase the size of the matching greater than M , which violates the maximality of M .
By attaching all the possible edges to the vertices of AM and BM .
AM and B BM .
A AM and BM , we achieve a new graph G0 .
By Lemma 2.
H(G) H(G0 ).
Also.
G0 has the matching number at least k 1.
So.
G0 2 / Akn and G G0 .
Now, we construct an another new graph G00 based on G0 , by deleting all the edges between the set A AM of vertices and the set BM of vertices, and adding all the edges between A AM and AM in G0 .
It is easy to verify that G00 N = Kk,n k .
Let |A| = n1 , |B| = n2 , so n1 n2 = n and n2 n1 > k and using .
, we get Cn21 Cn22 .
1 n2 n22 n1 n2 2kn n 2k 2
= 1
C 2 Cn2 k n2 kn n k 2 H(G00 ) = k.
Therefore, by the fact that k < n1 n2 = n n1 < n k, we have H(G0 ) = k 2 k.
H(G0 ) n1 n2
H(G00 ) =
2 n1 n2
< 0,
as required.
Harary index of bipartite graphs with a given vertex / edge-connectivity In the current section, we determine the extremal graphs with the maximum Harary index among Cns and Dnt .
By Kp,0 , p 1, we mean pK1 .
isolated vertice.
Let Os _1 (Kn1 ,n2 [ Km1 ,m2 ) be the graph obtained by adding all vertices of the empty graph Os of order s .
to all vertices belonging to the part of cardinality n1 in the bipartition of Kn1 ,n2 and the part of cardinality m1 in the bipartition of Km1 ,m2 , respectively.
Lemma 3.
If s q > p then H(Os _1 (K1,0 [ Kp,q )) < H(Os _1 (K1,0 [ Kp 1,q 1 )).
Proof.
Let G = Os _1 (K1,0 [ Kp,q ) and G0 = Os _1 (K1,0 [ Kp 1,q 1 ).
By .
, we have p sq Cs2 Cp2 Cq2 q H(G) = s sp pq s2 p 2 q 2 sp pq H(G0 ) =s .
Cs2 Cp 1 Cq2 1 q 1 5s p 7q sq s p q sp pq Harary index of bipartite graphs Hanyuan Deng et al.
So, by s q > p, we have H(G) H(G0 ) = .
< 0,
as claimed.
Lemma 3.
If s q 1 < p then H(Os _1 (K1,0 [ Kp,q )) < H(Os _1 (K1,0 [ Kp 1,q 1 )).
Proof.
Let G = Os _1 (K1 [ Kp,q ) and G00 = Os _1 (K1 [ Kp 1,q 1 ).
By .
, we have p sq Cs2 Cp2 Cq2 q H(G) = s sp pq s2 p 2 q 2 sp pq 1 s.
Cs2 Cp2 1 Cq 1 H(G ) =s .
s 3p 5q sq s2 p2 q 2 2 sp pq Therefore, by s q 1 < p, we have H(G) H(G00 ) = < 0, as claimed.
Note that Ks,n s = Os _1 (K1,0 [ Kn s 1,0 ), by Lemma 3.
2, we have Corollary 3.
If 1 s n2 1 then H(Ks,n s ) < H(Os _1 (K1 [ Kn s 2,1 )).
Lemma 3.
Let G = (V1 .
V2 .
E) 2 Cns with a vertex-cut I = I1 [ I2 of order s such that G I has two components G1 = (A.
E1 ) and G2 = (C.
E2 ), where V1 = A [ I1 [ C and V2 = B [ I2 [ D.
If A.
I1 are non-empty sets, then G cannot be a graph with the maximum Harary index in Cns .
Proof.
Assume that G has the maximum H(G) in Cns .
By Lemma 2.
G contains all edges between V1 and V2 , except edges between A and D and between C and B.
Let |A| = m1 , |B| = m2 , |C| = n1 , |D| = n2 , |I1 | = k and |I2 | = t.
Then m1 1, n1 1, k 1 and k t = s.
So.
H(G) = m1 .
2 t n2 ) n1 .
n2 ) m1 k m1 n1 kn1 m2 n2 m2 t n2 t Cm Ck2 Cn21 Cm Cn22 Ct2 m1 n2 m2 n1 Harary index of bipartite graphs Hanyuan Deng et al.
Note that G (I2 [ D) is not connected, we have t n2 s = t k, and n2 k.
We partition D into D1 and D2 such that D = D1 [ D2 with |D1 | = k and |D2 | = n2 k.
Let u0 be any vertex of C, and G0 = G .
v 2 D2 } .
a 2 A, d 2 D} .
b 2 B, c 2 C .
0 }}.
Then G0 2 Cns with its bipartition (V1 .
V2 ) and a vertex-cut I2 [ D1 with s vertices.
In fact.
G0 contains all edges between V1 and V2 , except edges between u0 and B [ I2 , and H(G0 ) = .
1 k n1 .
2 t n2 ) .
Cm m2 n2 k 2 t n2 1 k n1 Thus.
H(G) H(G0 ) = .
) < 0, a contradiction.
Remark 3.
By the symmetry, if B.
I2 are non-empty sets .
ee Lemma 3.
, then G fails to be a maximum H(G) in Cns .
Let U and V any two vertex sets of G.
Denote by EG [U.
V ], edges of G with one of its end vertex in U and the other in V .
Lemma 3.
Let n > 4 and G = (V1 .
V2 .
E) 2 Cns with an edge-cut Et = E1 [ E2 of size t such that G Et has two components G1 = (A.
E 0 ) and G2 = (C.
E 00 ), where V1 = A [ C.
V2 = B [ D.
E1 = Et \ EG [A.
D] and E2 = Et \ EG [B.
C].
If A.
D are non-empty sets, then G cannot be a graph with the maximum H(G) in Dnt .
Proof.
Assume that G has the maximum H(G) in Dnt .
By Lemma 2.
G contains all edges between A and B, edges between C and D and edges in Et .
Let |A| = m1 , |B| = m2 , |C| = n1 , |D| = n2 , |E1 | = a and |E2 | = b.
Then a b = t and m1 n1 m2 n2 = n > 4.
Suppose, we assume m1 > 1 in the following.
Let S4 .
S3 .
S2 and S1 denote the end-vertices of the edges of Et in D.
B and A, respectively.
Let |A S1 | = a1 , |B S2 | = a2 , |C S3 | = a3 and |D S4 | = a4 .
Then G contains m1 m2 n1 n2 t = |E(G)| vertex pairs at distance 1, m1 n2 m2 n1 t vertex pairs at distance 3, and a1 a3 a2 a4 vertex pairs at distance 4.
Remaining Cn2 |EG | .
1 n1 m2 n2 .
1 a4 a2 a3 ) vertex pairs are at distance 2.
Therefore.
H(G) = |E(G)| .
1 n2 m2 n1 .
1 a3 a2 a4 ) (Cn |E(G)| .
1 n2 m2 n1 .
1 a3 a2 a4 )).
Let c0 be a vertex and dG .
0 ) = h |D| = h n2 , where h.
, m2 } h .
denotes the number of edges joining c0 to B.
It is easy to see that the set of edges incident to c0 is an edge-cut of G, we have h n2 t = a b and |D| = n2 We partition D into D1 and D2 such that D = D1 [ D2 with |D1 | = t h and |D2 | = n2 t h.
Let G0 = G .
v 2 D2 } .
a 2 A, d 2 D} .
b 2 B, c 2 C .
0 }}.
Then G0 2 Dnt Harary index of bipartite graphs Hanyuan Deng et al.
with its bipartition (V1 .
V2 ) and an edge-cut of edges joining c0 to the vertices in B [ D1 of size In fact.
G0 contains all edges between A [ C .
0 } and B [ D, edges between c0 and D1 and h edges joining c0 to B.
Then G0 contains .
1 n1 .
2 n2 ) t = |E(G0 )| vertex pairs at distance 1, .
|D2 | = m2 n2 t pairs of vertices at distance 3, and all the other Cn2 |E(G0 )| .
2 n2 .
vertex pairs are at the distance 2.
Therefore, |E(G0 )| Cn2
|E(G0 )|
2 n2 m2 n2 = H(G0 ).
Since A.
D are non-empty sets and m1 > 1, then H(G) H(G0 ) = .
1 a3 a2 a4 ) m2 .
1 n2 .
< 0, which is a contradiction.
Os q
Os q 1
Os q 1
H1N
H2N
H3N
Figure 1.
Graphs H1N .
H2N .
H3N in Theorems 3.
1 and 3.
Theorem 3.
If Cns has the graph G with the maximum H(G), where 1 s n2 .
Then G 2 {H1N .
H2N .
H3N }, where H1N .
H2N and H3N are depicted in Figure 1.
Proof.
Assume that.
G has the maximum H(G) in Cns .
Let I be a vertex-cut of G having s vertices, and G1 .
G2 .
A A A .
Gt are the components of G I, where t 2.
If one of its components has a minimum of two vertices, then using Lemma 2.
1 the component should be a complete bipartite .
If one of its components is a singleton i, then i must be adjacent to every vertex of I and the subgraph G[I] induced by I has no edges.
or else (G) < s.
Therefore.
I is contained in the same part of bipartition of G by Lemma 2.
Now, we consider the following cases:
A Case 1.
If every component of G I is a singleton, then G = Ks,n s .
So t N N by Corollary 3.
It is conventional to see that, for odd n.
Ks,n s = H1 and for even n.
Ks,n s 2 {H2N .
H3N }.
Harary index of bipartite graphs Hanyuan Deng et al.
A Case 2.
If one of its component G I has a minimum of two vertices.
Then G I has precisely two components.
otherwise, we can get a graph G0 2 Cns by adding some edges in G such that the subgraph induced by V (G1 [ G2 [ A A A [ Gt 1 ) is a complete bipartite graph, and H(G) < H(G0 ) by Lemma 2.
1, which is a contradiction.
If G I has two components G1 .
G2 , then by Lemma 3.
3 and Remark 3.
1, either G1 = K1 or G2 = K1 .
Let us assume that G2 = K1 = .
Then.
G1 N = Kp,q and u is joined to all vertices of I.
So.
I is contained in the same part of the bipartition of G, and each vertex of I is joined to all vertices in the same part of the bipartition of G1 by Lemma 2.
Hence.
G = Os _1 (K1,0 [ Kp,q ), where s = |I|.
And p s since p vertices in the same part of the bipartition of Kp,q is a vertex-cut of G.
Since G is a graph in Cns with the maximum Harary index, and by Lemmas 3.
1 and 2, we have s q 1 p s q 1 and G 2 {H1N .
H2N .
H3N }.
Using Lemma 3.
4 and utilizing proof of the previous theorem, we conclude the following result.
Theorem 3.
Let Dnt has the graph G with the maximum H(G) and 1 t n2 .
Then G 2 {H1N .
H2N .
H3N }, where H1N .
H2N and H3N are depicted in Figure 1.
Acknowledgement The authors are very grateful to the referees for their careful reading, valuable suggestions, comments and corrections which resulted in a great improvement of the original manuscript.
The Postdoctoral studies and research of the Suresh Elumalai is sustained by University of Haifa.
Israel and it is deeply acknowledged.
References