Nordhaus-Gaddum Type Results for the Harary Index of Graphs

Document Type : Research Paper

Authors

1 Beijing Normal Unviersity

2 Qinghai Normal Unviersity

3 Qinghai Normal University

Abstract

The \emph{Harary index} $H(G)$ of a connected graph $G$ is defined as $H(G)=\sum_{u,v\in V(G)}\frac{1}{d_G(u,v)}$ where $d_G(u,v)$ is the distance between vertices $u$ and $v$ of $G$. The Steiner distance in a graph, introduced by Chartrand et al. in 1989, is a natural generalization of the concept of classical graph distance. For a connected graph $G$ of order at least $2$ and $S\subseteq V(G)$, the \emph{Steiner distance} $d_G(S)$ of the vertices of $S$ is the minimum size of a connected subgraph whose vertex set contains $S$. Recently, Furtula, Gutman, and Katani'{c} introduced the concept of Steiner Harary index and gave its chemical applications. The \emph{$k$-center Steiner Harary index} $SH_k(G)$ of $G$ is defined by $SH_k(G)=\sum_{S\subseteq V(G),|S|=k}\frac{1}{d_G(S)}$. In this paper, we get the sharp upper and lower bounds for $SH_k(G)+SH_k(\overline{G})$ and $SH_k(G)\cdot SH_k(\overline{G})$, valid for any connected graph $G$ whose complement $\overline {G}$ is also connected.

Keywords

Main Subjects

References

  1. J. Akiyama, F. Harary, A graph and its complement with specified properties, Int. J. Math. Math. Sci. 2 (1979) 223–228.
  2.  M. Aouchiche, P. Hansen, A survey of Nordhaus–Gaddum type relations, Discrete Appl. Math. 161 (2013) 466–546.
  3.  P. Ali, P. Dankelmann, S. Mukwembi, Upper bounds on the Steiner diameter of a graph, Discrete Appl. Math. 160 (2012) 1845–1850.
  4.  A. T. Balaban, The Harary index of a graph, MATCH Commun. Math. Comput. Chem. 75 (2016) 243–245.
  5.  J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, 2008.
  6.  F. Buckley, F. Harary, Distance in Graphs, Addison–Wesley, Redwood, 1990.
  7.  J. Cáceresa, A. Márquezb, M. L. Puertasa, Steiner distance and convexity in graphs, Eur. J. Combin. 29 (2008) 726–736.
  8.  G. Chartrand, O. R. Oellermann, S. Tian, H. B. Zou, Steiner distance in graphs, Časopis Pest. Mat. 114 (1989) 399–410.
  9.  P. Dankelmann, O. R. Oellermann, H. C. Swart, The average Steiner distance of a graph, J. Graph Theory 22 (1996) 15–22.
  10.  P. Dankelmann, H. C. Swart, O. R. Oellermann, On the average Steiner distance of graphs with prescribed properties, Discrete Appl. Math. 79 (1997) 91–103.
  11.  P. Dankelmann, R. Entringer, Average distance, minimum degree, and spanning trees, J. Graph Theory 33 (2000) 1–13.
  12.  P. Dankelmann, O. R. Oellermann, H. C. Swart, The average Steiner distance of a graph, J. Graph Theory 22 (1996) 15–22.
  13.  A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: theory and application, Acta Appl. Math. 66 (2001) 211–249.
  14.  R. C. Entringer, D. E. Jackson, D. A. Snyder, Distance in graphs, Czech. Math. J. 26 (1976), 283–296.
  15.  B. Furtula, I. Gutman, V. Katanić, Three-center Harary index and its applications, Iranian J. Math. Chem. 7 (1) (2016) 61–68.
  16.  M. R. Garey, D. S. Johnson, Computers and Intractability – A Guide to the Theory of NP−Completeness, Freeman, San Francisco, 1979, pp. 208–209.
  17.  W. Goddard, O. R. Oellermann, Distance in graphs, in: M. Dehmer (Ed.), Structural Analysis of Complex Networks, Birkhäuser, Dordrecht, 2011, pp. 49–72.
  18.  I. Gutman, B. Furtula, X. Li, Multicenter Wiener indices and their applications, J. Serb. Chem. Soc. 80 (2015) 1009–1017.
  19.  I. Gutman, S. Klavžar, B. Mohar (Eds.), Fifty years of the Wiener index, MATCH Commun. Math. Comput. Chem. 35 (1997) 1–159.
  20.  I. Gutman, O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer, Berlin, 1986.
  21.  X. Li, Y. Fan, The connectivity and the Harary index of a graph, Discrete Appl. Math. 181 (2015) 167–173.
  22.  X. Li, Y. Mao, I. Gutman, The Steiner Wiener index of a graph, Discuss. Math. Graph Theory 36 (2) (2016) 455–465.
  23.  X. Li, Y. Mao, I. Gutman, Inverse problem on the Steiner Wiener index, Discuss. Math. Graph Theory, in press.
  24.  B. Lučić, A. Miličević, S. Nikolić, N. Trinajstić, Harary index-twelve years later, Croat. Chem. Acta 75 (2002) 847–868.
  25.  Y. Mao, The Steiner diameter of a graph, Bull. Iranian Math. Soc. 43 (2) (2017) 439−454.
  26.  Y. Mao, Steiner Harary index, Kragujevac J. Math. 42 (1) (2018) 29−39.
  27.  Y. Mao, Z. Wang, I. Gutman, Steiner Wiener index of graph products, Trans. Combin. 5 (3) (2016) 39–50.
  28. Y. Mao, Z. Wang, I. Gutman, H. Li, Nordhaus-Gaddum-type results for the Steiner Wiener index of graphs, Discrete Appl. Math. 219 (2017) 167−175.
  29. O. R. Oellermann, S. Tian, Steiner centers in graphs, J. Graph Theory 14 (1990) 585–597.
  30.  D. H. Rouvray, Harry in the limelight: The life and times of Harry Wiener, in: D. H. Rouvray, R. B. King (Eds.), Topology in Chemistry — Discrete Mathematics of Molecules, Horwood, Chichester, 2002, pp. 1–15.
  31.  D. H. Rouvray, The rich legacy of half century of the Wiener index, in: D. H. Rouvray, R. B. King (Eds.), Topology in Chemistry — Discrete Mathematics of Molecules, Horwood, Chichester, 2002, pp. 16–37.
  32.  H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17–20.
  33.  K. Xu, K. C. Das, N. Trinajstić, The Harary Index of a Graph, Springer, Heidelberg, 2015.
  34.  K. Xu, M. Liu, K. C. Das, I. Gutman, B. Furtula, A survey on graphs extremal with respect to distance–based topological indices, MATCH Commun. Math. Comput. Chem.71 (2014) 461–508.
Iranian Journal of Mathematical Chemistry
Volume 8, Issue 2
Special Issue of IJMC on Chemometrics
June 2017
Pages 181-198

Files

Share

How to cite

Statistics