# Cordial Labeling of Cartesian Product between two Balanced Bipartite Graphs

## DOI:

https://doi.org/10.26713/jims.v11i2.1132## Keywords:

Cordial labeling, Cartesian product, Balanced bipartite graphs, Algorithm, Time complexity## 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.

### Downloads

## 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.

## Downloads

## Published

## How to Cite

*Journal of Informatics and Mathematical Sciences*,

*11*(2), 179–193. https://doi.org/10.26713/jims.v11i2.1132

## Issue

## Section

## License

Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.