Algorithmic approach of cordial labeling on Cartesian product between balanced bipartite graph and path

Year 2019, Volume: 68 Issue: 2, 2064 - 2078, 01.08.2019

Sumonta Ghosh Anita Pal

https://doi.org/10.31801/cfsuasmas.586082

Abstract

Cordial labeling is one of the useful labeling in the realm of graph labeling. For the graph G=(V,E) vertex set V is label by {0,1}, where labeling of edge set E calculated by absolute difference between the end vertices labeling with the restriction that number of vertices label by 0 and number of vertices label by 1, their absolute difference not exceeding 1. If similar restriction will follow for edge also then the labeling technique is known as cordial labeling and the graph which admits cordial labeling is known as cordial graph. In this paper we want to apply cordial labeling on a complex graph structure which we obtained by Cartesian product between complete bipartite graph(Balanced bipartite graph) K_{n,n} and path P_{r}. We also propose three algorithm to label the above said graph by cordial labeling. We have analyse the time complexity of each algorithm and which is super-linear.

Keywords

Cordial labeling, graph labeling, Cartesian product of graphs

References

• Gallian, J.A., A dynamic survey of graph labeling, The Electronics Journal of Combinatorics, 17, (2010) 6. Hegde, S.M., On Multiplicative Labelings of a Graph. Labeling of Discrete Structures and applications. Narosa Publishing House. New Delhi. 83-96 2008.
• Beineke, L.W., Hegde, S.M., Strongly Multiplicative graphs. Discuss.Math. Graph Theory, 21, (2001) 63-75.
• Cahit, I., Cordial graphs a weaker version of graceful and harmonious graphs. Ars Combin. 23, (1987) 201-207.
• Cahit, I., On cordial and 3-equitable labellings of graphs. Util. Math. 37, (1990) 189-198.
• Cahit, I., Status of graceful tree conjecture in 1989, in Topics in Combinatorics and Graph Theory. R. Bodendiek and R. Henn (eds). Physica-Verlag. Heidelberg. 1990.
• Cahit, I., Recent results and open problems on cordial graphs. Contemporary Methods in Graph Theory. R. Bodendiek (ed.). Wissenschaftsverlag.Mannheim. 209-230, 1990.
• Cahit, I., Equitable tree labellings. Ars Combin. 40, 279-286 (1995).
• Cahit, I., On harmonious tree labellings. Ars Combin. 41, (1995) 311-317.
• Cahit, I., H-cordial graphs. Bull. Inst. Combin. Appl. 18, (1996) 87-101.
• Cahit, I., Some totally modular cordial graphs. Discuss. Math. Graph Theory. 22, (2002) 247-258.
• Cahit, I., Graceful labelings of rooted complete trees. personal communication.
• Cahit, I., A note on graceful directed trees. personal communication.
• Cahit, I., Yilmaz, R., E3-cordial graphs. Ars Combin. 54, (2000) 119-127.
• Graham, R.L., Sloane, N.J.A., On additive bases an harmonious graphs. SIAM J. Algebr. Disc. Meth. 1(4), (1980) 382-404.
• Rosa, A., On certain valuations of the vertices of a graph. Thery of graphs. International Symposium, (1967) 349-355.
• Babujee, J.B., Shobana, L., Cordial Languages and Cordial Numbers. Journal of Applied Computer Science and Mathematics, 13(6), (2012) 9-12.
• Ulaganathan, P.P., Selvam, B., Vijaya, K.P., Signed Product Cordial Labeling in duplicate graphs of Bistar, Double Star and Triangular Ladder Graph. International Journal of Mathematics Trends and Technology(IJMTT), 33(1), (2016) 19-24.
• Santhi, M., Some Star and Bistar Related Signed Product Cordial Graphs. International Journal of Mathematical Archive, 6(10), (2015) 232-236.
• Ho, Y.S., Lee, S.M., Shee, S.C., Cordial labelings of unicyclic graphs and generalized peterson graphs. Congr. Numer., 68, (1989) 109-122.