On Star Decomposition and Star Number of Some Graph Classes

J.K. Sebastian¹ , J.V. Kureethara² , S.Naduvath ³ , C. Dominic⁴

Section:Research Paper, Product Type: Isroset-Journal
Vol.5 , Issue.6 , pp.81-85, Dec-2018

CrossRef-DOI:   https://doi.org/10.26438/ijsrmss/v5i6.8185

Online published on Dec 31, 2018

Copyright © J.K. Sebastian, J.V. Kureethara, S.Naduvath, C. Dominic . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

795 Views    727 Downloads    218 Downloads

Abstract :
Graph decomposition is a partition of graph into its subgraphs. Star decomposition is the decomposition of the graph into stars. In this paper we define a parameter, the star number of graphs, as the minimum number of end vertices of stars in a star decomposition of a graph. We determine this parameter for certain fundamental graph classes.

Key-Words / Index Term :
Decomposition, star decomposition, pendant number, star number

References :
[1] T. Ae, S. Yamamoto, N Yoshida, “Line-disjoint Decomposition of Complete Graph into Stars”, Journal of Combinatorial Theory Series B. (to appear),1970.
[2] P. Cain, “Decomposition of Complete Graphs into Stars”, Bulletin of the Australian Mathematical Society, Vol. 10,No.1, pp.23-30, 1974.
[3] G. Chartrand, P. Zhang, “Introduction to Graph Theory”, Tata McGraw-Hill Publishing Limited, India, 2006.
[4] L.T. Cherin Monish Femila and S. Asha, "Hamiltonian Decomposition of Special Class of Ladder Graphs", International Journal of Scientific Research in Mathematical and Statistical Sciences, Vol.5, No.5, pp.114-120, 2018.
[5] J. A. Gallian, “A Dynamic Survey of Graph Labeling”, ElectronicJournal of Combinatorics, Vol.16, No.6, pp.1-219, 2009.
[6] F. Harary, “Graph Theory”, Addison-Wesley, Reading, MA, 1969.
[7] F. Harary, A. J. Schwenk, “The number of Caterpillars”,Discrete Mathematics, Vol.6, No.4, pp.359-365, 1973.
[8] P. C. Hogarth, “Decomposition of Complete Graphs into 6-stars and into 10-stars”, Combinatorial Mathematics III, pp.136-142, 1975.
[9] T. A. Mangam, and J. V. Kureethara, “Diametral Paths in Total Graphs of Complete Graphs, Complete Bipartite Graphs and Wheels”, International Journal of Civil Engineering & Technology, Vol.8, No.5, pp.1212-1219, 2017.
[10] B. Neggazi, M. Haddad, H. Kheddouci “A new self-stabilizing algorithm for maximal p-star decomposition of general graphs”, Information Processing Letters, Vol.115, No.11, pp.892-898, 2015.
[11] J.K. Sebastian, J.V. Kureethara, “A Note on d-decomposition of Smaller Graphs”,communicated, 2018.
[12] J. K. Sebastian, J. V. Kureethara,“Pendant Number of Graphs”, International Journal of Applied Mathematics,Vol.31, No.5, pp.679-689, 2018.
[13] J. K. Sebastian, J. V. Kureethara, N.K. Sudev, C. Dominic, “A study on Pendant Number of Graphs”, communicated, 2018.
[14] J. K. Sebastian, J. V. Kureethara, N. K. Sudev, C. Dominic, “On the Pendant Number of Some Graphs”, communicated, 2018.
[15] J.K. Sebastian, J.V. Kureethara, N.K. Sudev, C. Dominic, “Some Properties of Pendant Number of Graphs”, communicated, 2018.
[16] B.S. Sunoj, T.K. Mathew Varkey, "One Raised Product Prime Labeling of Some Star Related Graphs", International Journal of Scientific Research in Mathematical and Statistical Sciences, Vol.5, No.3, pp.18-23, 2018.
[17] M. Tarsi, “On the Decomposition of a Graph into Stars”, Discrete Mathematics, Vol.36, No.3, pp.299-304, 1981.
[18] J. Varghese, A. Antonysamy, “On double continuous monotonic decomposition of graphs”, Journal of Computer and Mathematical Sciences Vol.1, No.2, pp.103-273, 2010.
[19] J. Varghese and A. Antonysamy, “On modified continuous monotonic decomposition of tensor product of graphs”, Int. J. Contemp. Math. Sciences, Vol.5, No.33, pp.1609-1614, 2010.
[20] X. Zhang, H. Zhang, “Some Graphs Determined by Their Spectra”, Linear Algebra and its Applications,Vol.431,No.9,pp.1443-1454, 2009.
[21] Y. Zhao, B. Wu, “Star Decomposition of Graphs”, Discrete Mathematics, Algorithms and Applications,Vol. 7, No.2, pp.1-9, 2015.