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.