Download PDF - The Wiener number of Kneser graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

The Wiener number of Kneser graphs

Authors 1, 1

Affiliations

  1. Srinivasa Ramanujan Centre, SASTRA University, Kumbakonam-612 001, India

Abstract

The Wiener number of a graph G is defined as 1/2∑d(u,v), where u,v ∈ V(G), and d is the distance function on G. The Wiener number has important applications in chemistry. We determine the Wiener number of an important family of graphs, namely, the Kneser graphs.

Keywords

ENG
Wiener number, Kneser graph, odd graph

Bibliography

  1. R. Balakrishanan, N. Sridharan and K. Viswanathan, The Wiener index of odd graphs, Indian Inst. Sci. 86 (2006) 527-531.
  2. R. Balakrishanan, K. Viswanathan and K.T. Raghavendra, Wiener index of two special trees, MATCH Commun. Math. Comupt. Chem. 57 (2007) 385-392.
  3. R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory (Springer, New York, 2000).
  4. N.L. Biggs, Algebraic Graph Theory (Cambridge University Press, London, 1974).
  5. A.A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (2001) 211-249, doi: 10.1023/A:1010767517079.
  6. 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.
  7. P. Frankl and Z. Furedi, Extremal problems concerning Kneser graphs, J. Combin. Theory (B) 40 (1986) 270-284, doi: 10.1016/0095-8956(86)90084-5.
  8. I. Gutman and O. Polansky, Mathematical Concepts in Organic Chemistry (Springer-Verlag, Berlin, 1986).
  9. H. Hajabolhassan and X. Zhu, Circular chromatic number of Kneser graphs, J. Combin. Theory (B) 881 (2003) 299-303, doi: 10.1016/S0095-8956(03)00032-7.
  10. A. Johnson, F.C. Holroyd, and S. Stahl, Multichormatic numbers, star chromatic numbers and Kneser graphs, J. Graph Theory 26 (1997) 137-145, doi: 10.1002/(SICI)1097-0118(199711)26:3<137::AID-JGT4>3.0.CO;2-S
  11. K.W. Lih and D.F. Liu, Circular chromatic number of some reduced Kneser graphs, J. Graph Theory 41 (2002) 62-68, doi: 10.1002/jgt.10052.
  12. L. Lovasz, Kneser's conjecture, chromatic number and homotopy, J. Combin. Theory (A) 25 (1978) 319-324, doi: 10.1016/0097-3165(78)90022-5.
  13. M. Valencia-Pabon and J.-C. Vera, On the diameter of Kneser graphs, Discrete Math. 305 (2005) 383-385, doi: 10.1016/j.disc.2005.10.001.
  14. S.-P. Eu, B. Yang, and Y.-N Yeh, Generalised Wiener indices in hexagonal chains, Intl., J., Quantum Chem. 106 (2006) 426-435, doi: 10.1002/qua.20732.
  15. S. Stahl, n-tuple coloring and associated graphs, J. Combin. Theory (B) 20 (1976) 185-203, doi: 10.1016/0095-8956(76)90010-1.
  16. S. Stahl, The multichromatic number of some Kneser graphs, Discrete Math. 185 (1998) 287-291, doi: 10.1016/S0012-365X(97)00211-2.
  17. K. Tilakam, Personal communication.
  18. H. Wiener, Structural determination of Paraffin boiling points, J. Amer. Chem. Soc. 69 (1947) 17-20, doi: 10.1021/ja01193a005.
  19. L. Xu and X. Guo, Catacondensed hexagonal systems with large Wiener numbers, MATCH Commun. Math. Comput. Chem. 55 (2006) 137-158.
Discussiones Mathematicae Graph Theory
2008/28/2
Export to PBN, Opens in new tab
Pages:
219-228
Main language of publication
English
Received
2007-05-21
Accepted
2008-02-18
Published
2008

DOI: 10.7151/dmgt.1402

Exact and natural sciences