Cordial Labeling of Cartesian Product between two Balanced Bipartite Graphs

Sumonta Ghosh, Surjeet Mohanty, Anita Pal

Abstract


Cordial Labeling finds its application in Automated Routing algorithms, Communications relevant Adhoc Networks and many others. These networks and routing paths are best represented by a set of vertices and edges which forms a complex graph. In this paper an Algorithmic approach is devised in order to cordially label some of such complex graphs formed by the Cartesian product of two Balanced Bipartite Graphs. There is an absence of a universal algorithm that could label the entire family of \(K_{n,n} \times K_{n,n}\) graphs, which is primarily because of the complexity of these graphs. We have attempted to redefine the \(K_{n,n}\) graph so that on carrying out the Cartesian product we obtain a symmetrical graph. Subsequently we design an efficient and effective algorithm for cordially labeling \(G= K_{n,n} \times K_{n,n}\). We also proof that the algorithm is running with polynomial time complexity.  The results can be used to study and design algorithms for signed product cordial, total signed product cordial, prime cordial labeling etc. of the family of \(K_{n,n} \times K_{n,n}\) graphs.


Keywords


Cordial labeling; Cartesian product; Balanced bipartite graphs; Algorithm; Time complexity

Full Text:

PDF

References


J. B. Babujee and L. Shobana, Cordial languages and Cordial numbers, Journal of Applied Computer Science & Mathematics 6(13) (2012), 9 – 12.

L. W. Beineke and S. M. Hegde, Strongly multiplicative graphs, Discussiones Mathematicae Graph Theory 21 (1)(2001), 63 – 75, DOI: 10.7151/dmgt.1133.

I. Cahit, Cordial graphs – a weaker version of graceful and harmonious graphs, Ars Combinatoria 23 (1987), 201–207.

I. Cahit, On cordial and 3-equitable labellings of graphs, Util. Math. 37 (1990), 189 – 198.

J. A. Gallian, A dynamic survey of graph labeling, The Electronic Journal Of Combinatorics 16 (6) (2009), 1 – 219.

S. Ghosh and A. Pal, L(3,1)-Labeling of some simple graphs, Advanced Modeling and Optimization 18(2) (2016), 243–248.

R. L. Graham and N. J. A. Sloane, On additive bases and harmonious graphs, SIAM Journal on Algebraic Discrete Methods 1(4) (1980), 382–404, DOI: 10.1137/0601045.

S. M. Hegde, On multiplicative labelings of a graph, Journal Of Combinatorial Mathematics And Combinatorial Computing 65 (2008), 181.

A. Rosa, On certain valuations of the vertices of a graph, in Theory of Graphs (Internat. Symposium, Rome), 349 – 355 (1966).

S. Sumonta, S. Paul and A. Pal, L(2,1)-Labeling of cartesian product of complete bipartite graph and path, Journal of Informatics and Mathematical Sciences 9(3) (2017), 685 – 698, DOI: 10.26713/jims.v9i3.817

S. K. Vaidya and N. H. Shah, 3-Equitable labeling for some star and Bistar Related graphs, Internat. J. Math. & Sci. Comput. 2(1) (2012), 3 – 8.

S. K. Vaidya and N. H. Shah, Some star and bistar related divisor cordial graphs, Annals of Pure and Applied Mathematics 3(1) (2013), 67–77.

S. Vaidya and N. Shah, Cordial labeling for some bistar related graphs, International Journal of Mathematics and Soft Computing 4(2) (2014), 33 – 39, DOI: 10.26708/IJMSC.2014.2.4.04.

V. Yegnanarayanan, Some interesting applications of graph labellings, Journal of Mathematical and Computational Science 2(5) (2012), 1522.




DOI: http://dx.doi.org/10.26713%2Fjims.v11i2.1132

eISSN 0975-5748; pISSN 0974-875X