PDF

Discussiones Mathematicae Graph Theory 28(2) (2008) 219.228
DOI: https://doi.org/10.7151/dmgt.1402

THE WIENER NUMBER OF KNESER GRAPHS

Rangaswami Balakrishnan  and  S. Francis Raj

Srinivasa Ramanujan Centre, SASTRA University
Kumbakonam-612 001, India
e-mail: mathbala@satyam.net.in
e-mail: francisraj_s@yahoo.com

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: Wiener number, Kneser graph, odd graph.

2000 Mathematics Subject Classification: 05C12.

References

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

Received 21 May 2007
Revised 18 February 2008
Accepted 20 February 2008