The Wiener number of powers of the Mycielskian
Rangaswami Balakrishnan ; S. Francis Raj
Discussiones Mathematicae Graph Theory, Tome 30 (2010), p. 489-498 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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 μ(Gk).

Publié le : 2010-01-01
EUDML-ID : urn:eudml:doc:270981 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1509,
     author = {Rangaswami Balakrishnan and S. Francis Raj},
     title = {The Wiener number of powers of the Mycielskian},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {30},
     year = {2010},
     pages = {489-498},
     zbl = {1217.05079},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1509}
}

Rangaswami Balakrishnan; S. Francis Raj. The Wiener number of powers of the Mycielskian. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 489-498. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1509/

[000] [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. | Zbl 1138.05321

[001] [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. | Zbl 1156.05016

[002] [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. | Zbl 1152.05322

[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.

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

[005] [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. | Zbl 0941.05026

[006] [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. | Zbl 0993.05059

[007] [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. | Zbl 1030.05047

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

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

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

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

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

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

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