The Wiener number of powers of the Mycielskian

Rangaswami Balakrishnan; S. Francis Raj

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 3, page 489-498
  • ISSN: 2083-5892

Abstract

top
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 ) .

How to cite

top

Rangaswami Balakrishnan, and S. Francis Raj. "The Wiener number of powers of the Mycielskian." Discussiones Mathematicae Graph Theory 30.3 (2010): 489-498. <http://eudml.org/doc/270981>.

@article{RangaswamiBalakrishnan2010,
abstract = {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)$.},
author = {Rangaswami Balakrishnan, S. Francis Raj},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Wiener number; Mycielskian; powers of a graph},
language = {eng},
number = {3},
pages = {489-498},
title = {The Wiener number of powers of the Mycielskian},
url = {http://eudml.org/doc/270981},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Rangaswami Balakrishnan
AU - S. Francis Raj
TI - The Wiener number of powers of the Mycielskian
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 3
SP - 489
EP - 498
AB - 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)$.
LA - eng
KW - Wiener number; Mycielskian; powers of a graph
UR - http://eudml.org/doc/270981
ER -

References

top
  1. [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. Zbl1138.05321
  2. [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. Zbl1156.05016
  3. [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. Zbl1152.05322
  4. [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. [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. [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. Zbl0941.05026
  7. [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. Zbl0993.05059
  8. [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. Zbl1030.05047
  9. [9] D. Liu, Circular Chromatic Number for iterated Mycielski graphs, Discrete Math. 285 (2004) 335-340, doi: 10.1016/j.disc.2004.01.020. Zbl1050.05054
  10. [10] Liu Hongmei, Circular Chromatic Number and Mycielski graphs, Acta Mathematica Scientia 26B (2006) 314-320. Zbl1096.05022
  11. [11] J. Mycielski, Sur le colouriage des graphes, Colloq. Math. 3 (1955) 161-162. 
  12. [12] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956) 175-177, doi: 10.2307/2306658. Zbl0070.18503
  13. [13] H. Wiener, Structural Determination of Paraffin Boiling Points, J. Amer. Chem. Soc. 69 (1947) 17-20, doi: 10.1021/ja01193a005. 
  14. [14] L. Xu and X. Guo, Catacondensed Hexagonal Systems with Large Wiener Numbers, MATCH Commun. Math. Comput. Chem. 55 (2006) 137-158. Zbl1088.05071
  15. [15] L. Zhang and B. Wu, The Nordhaus-Gaddum-type inequalities for some chemical indices, MATCH Commun. Math. Comput. Chem. 54 (2005) 189-194. Zbl1084.05072

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.