HUB-INTEGRITY POLYNOMIAL OF GRAPHS

Abstract

Graph polynomials are polynomials assigned to graphs. Interestingly, they also arise in many areas outside graph theory as well. Many properties of graph polynomials have been widely studied. In this paper, we introduce a new graph polynomial. The hub-integrity polynomial of G is the polynomial HIs G, x = Xp i=h hi G, i x i , such that hi G, i is the number of HI-sets of G of size i, and h is the hub number of G. Some properties of HIs G, x and its coefficients are obtained. Also, the hub-integrity polynomial of some specific graphs is computed.

Keywords

• Integrity,Hub set,Hub-integrity,HI-set of a graph G,HIs-polynomials

References

1. Akbari, S., Alikhani, S. and Peng, Y. H., (2010), Characterization of graphs using domination poly- nomial, European J., 31, pp. 1714-1724.
2. Bagga, K. S., Beineke, L. W., Goddard, W., Lipman, M. J. and Pippert, R. E., (1992), A survey of integrity, Discrete Appl. Math., 37/38, pp. 13-28.
3. Barefoot, C. A., Entringer, R. and Swart, H., (1987), Vulnerability in graphs - A comparative survey
4. J. Combin. Math. Combin. Comput., 1 , pp. 13-22. Barefoot, C. A., Entringer, R. and Swart, H., (1987), Integrity of trees and powers of cycles, Congr. Numer., 58, pp. 103-114.
5. Birkhoff, G. D. and Lewis, D. C., (1946), Chromatic polynomials, Trans. Amer. Math. Soc., 60 , pp. 451.
6. Farrell, E. J., (1997), A note on the clique polynomial and its relation to other graph polynomials, J.
7. Math. Sci., (Calcutta) 8, pp. 97-102. Goddard, W. and Swart, H. C., (1990), Integrity in graphs: bounds and basics, J. Combin. Math. Combin. Comput., 7, pp. 139-151.
8. Harary, F., (1969), Graph Theory. Addison Wesley, Reading Mass.

9. Li, J. X., Guo, J. M. and Shiu, W. C., (2013), On the second largest laplacian eigenvalues, Linear algebra appl., 438, pp. 2438-2446.
10. Mahde, S. S., Mathad, V. and Sahal, A. M., (2015), Hub-integrity of graphs, Bull. Int. Math. Virtual Inst., 5, pp. 57-64.
11. Mahde, S. S. and Mathad, V., (2015), Some operations in hub-integrity of graphs, Asia Pac. J. Math., , pp. 108-123.
12. Mahde, S. S. and Mathad, V., (2016), Hub-integrity of splitting graph and duplication of graph element, TWMS J. App. Eng. Math., 6, pp. 289-297.
13. Mahde, S. S. and Mathad, V., (2017), On the weak hub-integrity of graphs, Gulf J. Math, 5 (2), pp. 86.
14. Mahde, S. S. and Mathad, V., (2018), Hub-integrity of line graph, Electron. J. Math. Anal. Appl., 6, pp. 255-265.
15. Mahde, S. S. and Mathad, V., Hub-integrity graph of graphs, Submitted. Mowshowitz, A., (1972), The characteristic polynomial of a graph, J. Combin. Theory Ser., B 12, pp. 177-193.
16. Newport, K. T. and Varshney, P. K., (1991), Design of survivable communication networks under performance constraints, IEEE Transactions on Reliability, 40, pp. 433-440.
17. Singh, G. S., (2010), Graph Theory. PHI Learning Private Limited, New Delhi.
18. Tutte, W. T., (1954), A contribution to the theory of chromatic polynomials, Canad. J. Math., 6, pp. 80-91.
19. Walsh, M., (2006), The hub number of graphs, Int. J. Math. Comput. Sci., 1, pp. 117-124.