Geodesic
The Wiener number of powers of the Mycielskian
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 3, pp. 489-498.

Voir la notice de l'article provenant de la source Library of Science

The Wiener number of a graph G is defined as 1/2 ∑_u,v ∈ V(G) d(u,v), d the distance function on G. The Wiener number has important applications in chemistry. We determine a formula for the Wiener number of an important graph family, namely, the Mycielskians μ(G) of graphs G. Using this, we show that for k ≥ 1, W(μ(Sₙ^k)) ≤ W(μ(Tₙ^k)) ≤ W(μ(Pₙ^k)), where Sₙ, Tₙ and Pₙ denote a star, a general tree and a path on n vertices respectively. We also obtain Nordhaus-Gaddum type inequality for the Wiener number of μ(G^k).
Keywords: Wiener number, Mycielskian, powers of a graph 
@article{DMGT_2010_30_3_a10,
     author = {Balakrishnan, Rangaswami and Raj, S.},
     title = {The {Wiener} number of powers of the {Mycielskian}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {489--498},
     publisher = {mathdoc},
     volume = {30},
     number = {3},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a10/}
}
TY  - JOUR
AU  - Balakrishnan, Rangaswami
AU  - Raj, S.
TI  - The Wiener number of powers of the Mycielskian
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 489
EP  - 498
VL  - 30
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a10/
LA  - en
ID  - DMGT_2010_30_3_a10
ER  - 
%0 Journal Article
%A Balakrishnan, Rangaswami
%A Raj, S.
%T The Wiener number of powers of the Mycielskian
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 489-498
%V 30
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a10/
%G en
%F DMGT_2010_30_3_a10
Balakrishnan, Rangaswami; Raj, S. The Wiener number of powers of the Mycielskian. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 3, pp. 489-498. http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a10/

[1] X. An and B. Wu, The Wiener index of the kth power of a graph, Appl. Math. Lett. 21 (2007) 436-440, doi: 10.1016/j.aml.2007.03.025.

[2] R. Balakrishanan and S.F. Raj, The Wiener number of Kneser graphs, Discuss. Math. Graph Theory 28 (2008) 219-228, doi: 10.7151/dmgt.1402.

[3] R. Balakrishanan, N. Sridharan and K.V. Iyer, Wiener index of graphs with more than one cut vertex, Appl. Math. Lett. 21 (2008) 922-927, doi: 10.1016/j.aml.2007.10.003.

[4] R. Balakrishanan, N. Sridharan and K.V. Iyer, A sharp lower bound for the Wiener Index of a graph, to appear in Ars Combinatoria.

[5] R. Balakrishanan, K. Viswanathan and K.T. Raghavendra, Wiener Index of Two Special Trees, MATCH Commun. Math. Comput. Chem. 57 (2007) 385-392.

[6] G.J. Chang, L. Huang and X. Zhu, Circular Chromatic Number of Mycielski's graphs, Discrete Math. 205 (1999) 23-37, doi: 10.1016/S0012-365X(99)00033-3.

[7] A.A. Dobrynin, I. Gutman, S. Klavžar and P. Zigert, Wiener Index of Hexagonal Systems, Acta Appl. Math. 72 (2002) 247-294, doi: 10.1023/A:1016290123303.

[8] H. Hajibolhassan and X. Zhu, The Circular Chromatic Number and Mycielski construction, J. Graph Theory 44 (2003) 106-115, doi: 10.1002/jgt.10128.

[9] D. Liu, Circular Chromatic Number for iterated Mycielski graphs, Discrete Math. 285 (2004) 335-340, doi: 10.1016/j.disc.2004.01.020.

[10] Liu Hongmei, Circular Chromatic Number and Mycielski graphs, Acta Mathematica Scientia 26B (2006) 314-320.

[11] J. Mycielski, Sur le colouriage des graphes, Colloq. Math. 3 (1955) 161-162.

[12] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956) 175-177, doi: 10.2307/2306658.

[13] H. Wiener, Structural Determination of Paraffin Boiling Points, J. Amer. Chem. Soc. 69 (1947) 17-20, doi: 10.1021/ja01193a005.

[14] L. Xu and X. Guo, Catacondensed Hexagonal Systems with Large Wiener Numbers, MATCH Commun. Math. Comput. Chem. 55 (2006) 137-158.

[15] L. Zhang and B. Wu, The Nordhaus-Gaddum-type inequalities for some chemical indices, MATCH Commun. Math. Comput. Chem. 54 (2005) 189-194.