%0 Journal Article %1 bianchi13 %A Bianchi, Monica %A Cornaro, Alessandra %A Palacios, José Luis %A Torriero, Anna %D 2013 %J Journal of Mathematical Chemistry %K chemistry circuit effective.resistance eigenvalues graph.theory kirchhoff.index majorization matrix %N 2 %P 569--587 %R 10.1007/s10910-012-0103-x %T Bounds for the Kirchhoff index via majorization techniques %V 51 %X Using a majorization technique that identifies the maximal and minimal vectors of a variety of subsets of \$\$\\backslashmathbb\R\^\n\\\$\$ , we find upper and lower bounds for the Kirchhoff index K(G) of an arbitrary simple connected graph G that improve those existing in the literature. Specifically we show that \$\$K(G) \backslashgeq \backslashfrac\n\\d\_\1\\ \backslashleft \backslashfrac\1\\1+\backslashfrac\\backslashsigma\\\backslashsqrt\n-1\\\ + \backslashfrac\(n-2)^\2\\\n-1-\backslashfrac\\backslashsigma\\\backslashsqrt\n-1\\\\backslashright ,\$\$ where d 1 is the largest degree among all vertices in G, \$\$\backslashsigma ^\2\ = \backslashfrac\2\\n\ \backslashsum\_\(i, j) \backslashin E\ \backslashfrac\1\\d\_ı\d\_\j\\ = \backslashleft( \backslashfrac\2\\n\\backslashright) R\_\-1\(G),\$\$ and R −1(G) is the general Randić index of G for \$\$\\backslashalpha =-1\\$\$ . Also we show that \$\$K(G) \backslashleq \backslashfrac\n\\d\_\n\\\backslashleft( \backslashfrac\n-k-2\\1-\backslashlambda \_\2\\+\backslashfrac\k\\2\+\backslashfrac\1\\\backslashtheta\\backslashright) ,\$\$ where d n is the smallest degree, \$\$\\backslashlambda \_\2\\\$\$ is the second eigenvalue of the transition probability of the random walk on G, \$\$k = \backslashleft \backslashlfloor \backslashfrac\\backslashlambda \_\2\ \backslashleft( n-1\backslashright) +1\\\backslashlambda \_\2\+1\\backslashright\backslashrfloor \\backslashrm and\\backslashquad\backslashtheta = \backslashlambda \_\2\ \backslashleft( n-k-2\backslashright) -k+2.\$\$

@article{bianchi13, abstract = {Using a majorization technique that identifies the maximal and minimal vectors of a variety of subsets of {\$}{\$}{\{}{\backslash}mathbb{\{}R{\}}^{\{}n{\}}{\}}{\$}{\$} , we find upper and lower bounds for the Kirchhoff index K(G) of an arbitrary simple connected graph G that improve those existing in the literature. Specifically we show that {\$}{\$}K(G) {\backslash}geq {\backslash}frac{\{}n{\}}{\{}d{\_}{\{}1{\}}{\}} {\backslash}left[ {\backslash}frac{\{}1{\}}{\{}1+{\backslash}frac{\{}{\backslash}sigma{\}}{\{}{\backslash}sqrt{\{}n-1{\}}{\}}{\}} + {\backslash}frac{\{}(n-2)^{\{}2{\}}{\}}{\{}n-1-{\backslash}frac{\{}{\backslash}sigma{\}}{\{}{\backslash}sqrt{\{}n-1{\}}{\}}{\}}{\backslash}right] ,{\$}{\$} where d 1 is the largest degree among all vertices in G, {\$}{\$}{\backslash}sigma ^{\{}2{\}} = {\backslash}frac{\{}2{\}}{\{}n{\}} {\backslash}sum{\_}{\{}(i, j) {\backslash}in E{\}} {\backslash}frac{\{}1{\}}{\{}d{\_}{\{}i{\}}d{\_}{\{}j{\}}{\}} = {\backslash}left( {\backslash}frac{\{}2{\}}{\{}n{\}}{\backslash}right) R{\_}{\{}-1{\}}(G),{\$}{\$} and R −1(G) is the general Randi{\'{c}} index of G for {\$}{\$}{\{}{\backslash}alpha =-1{\}}{\$}{\$} . Also we show that {\$}{\$}K(G) {\backslash}leq {\backslash}frac{\{}n{\}}{\{}d{\_}{\{}n{\}}{\}}{\backslash}left( {\backslash}frac{\{}n-k-2{\}}{\{}1-{\backslash}lambda {\_}{\{}2{\}}{\}}+{\backslash}frac{\{}k{\}}{\{}2{\}}+{\backslash}frac{\{}1{\}}{\{}{\backslash}theta{\}}{\backslash}right) ,{\$}{\$} where d n is the smallest degree, {\$}{\$}{\{}{\backslash}lambda {\_}{\{}2{\}}{\}}{\$}{\$} is the second eigenvalue of the transition probability of the random walk on G, {\$}{\$}k = {\backslash}left {\backslash}lfloor {\backslash}frac{\{}{\backslash}lambda {\_}{\{}2{\}} {\backslash}left( n-1{\backslash}right) +1{\}}{\{}{\backslash}lambda {\_}{\{}2{\}}+1{\}}{\backslash}right{\backslash}rfloor {\{}{\backslash}rm and{\}}{\backslash}quad{\backslash}theta = {\backslash}lambda {\_}{\{}2{\}} {\backslash}left( n-k-2{\backslash}right) -k+2.{\$}{\$} }, added-at = {2017-02-15T11:45:57.000+0100}, author = {Bianchi, Monica and Cornaro, Alessandra and Palacios, Jos{\'e} Luis and Torriero, Anna}, biburl = {https://www.bibsonomy.org/bibtex/26a6987c1fe2286f2c2c52b4c488f9b79/ytyoun}, description = {Bounds for the Kirchhoff index via majorization techniques | SpringerLink}, doi = {10.1007/s10910-012-0103-x}, interhash = {e7b591179bc04e1090a49c27d5f98100}, intrahash = {6a6987c1fe2286f2c2c52b4c488f9b79}, issn = {1572-8897}, journal = {Journal of Mathematical Chemistry}, keywords = {chemistry circuit effective.resistance eigenvalues graph.theory kirchhoff.index majorization matrix}, number = 2, pages = {569--587}, timestamp = {2017-02-21T02:59:16.000+0100}, title = {Bounds for the Kirchhoff index via majorization techniques}, volume = 51, year = 2013 }