The Wiener number of Kneser graphs

• Autorzy: Rangaswami Balakrishnan , S. Francis Raj
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Wiener number; Kneser graph; odd graph

Kategorie tematyczne

• 05C12: Distance in graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2008
• Tom: 28
• Numer: 2
• Strony: 219-228

Daty

wydano

2008

otrzymano

2007-05-21

poprawiono

2008-02-18

zaakceptowano

2008-02-20

Twórcy

autor

Rangaswami Balakrishnan

• Srinivasa Ramanujan Centre, SASTRA University, Kumbakonam-612 001, India

autor

S. Francis Raj

• Srinivasa Ramanujan Centre, SASTRA University, Kumbakonam-612 001, India

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1402