Discussiones Mathematicae Graph Theory 32(1) (2012) 121-127
doi: 10.7151/dmgt.1590

[BIBTex] [PDF] [PS]

p-Wiener Intervals and p-Wiener Free Intervals

Kumarappan Kathiresan

Center for Research and Post Graduate Studies in Mathematics
Ayya Nadar Janaki Ammal College
Sivakasi - 626 124,Tamil Nadu, INDIA

S. Arockiaraj

Department of Mathematics
Dr. Sivanthi Aditanar College of Engineering
Tiruchendur-628 215,Tamil Nadu, INDIA

Abstract

A positive integer n is said to be Wiener graphical, if there exists a graph G with Wiener index n. In this paper, we prove that any positive integer n(≠ 2,5) is Wiener graphical. For any positive integer p, an interval [a,b] is said to be a p-Wiener interval if for each positive integer n ∈ [a,b] there exists a graph G on p vertices such that W(G) = n. For any positive integer p, an interval [a,b] is said to be p-Wiener free interval (p-hyper-Wiener free interval) if there exist no graph G on p vertices with a ≤ W(G) ≤ b (a ≤ WW(G) ≤ b). In this paper, we determine some p-Wiener intervals and p-Wiener free intervals for some fixed positive integer p.

Keywords: Wiener index of a graph, Wiener graphical, p-Wiener interval, p-Wiener free interval, hyper-Wiener index of a graph, radius, diameter

2010 Mathematics Subject Classification: 05C12.

References

[1]F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley Reading, 1990).
[2]P.G. Doyle and J.L. Snell, Random Walks and Electric Networks (Math. Assoc., Washington, 1984).
[3]R.C. Entringer, D.E. Jackson and D.A. Snyder, Distance in graphs, Czechoslovak Math. J. 26 (101) 1976.
[4]D. Goldman, S. Istrail, G. Lancia and A. Picolboni, Algorithmic strategies in Combinatorial Chemistry, in: 11th ACM-SIAM Symposium, Discrete Algorithms (2000) 275--284.
[5]I. Gutman, Y.N. Yeh, S.L. Lee and J.C. Chen, Wiener number of dendrimers, Comm. Math. Chem., 30 (1994) 103--115.
[6]I. Gutman, Relation between hyper-Wiener and Wiener index, Chem. Phys. Lett. 364 (2002) 352--356, doi: 10.1016/S0009-2614(02)01343-X.
[7]KM. Kathiresan and S. Arockiaraj, Wiener indices of generalized complementary prisms, Bull. Inst. Combin. Appl. 59 (2010) 31--45.
[8]S. Klavžar, P. Zigert and I. Gutman, An algorithm for the calculation of the hyper-Wiener index of benzenoid hydrocarbons, Comput. Chem. 24 (2000) 229--233, doi: 10.1016/S0097-8485(99)00062-5.
[9]Liu Mu-huo and Xuezhong Tan, The first to (k+1)-th smallest Wiener (Hyper -Wiener) indices of connected graphs, Kragujevac J. Math. 32 (2009) 109--115.
[10]S. Nikolić, N. Trinajstić and Z. Mihalić, The Wiener index: Development and applications, Croat. Chem. Acta. 68 (1995) 105--129.
[11]H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947) 17--20, doi: 10.1021/ja01193a005.

Received 8 July 2010
Revised 15 February 2011
Accepted 15 February 2011