| Paper title: |
Embedding and NP-complete Problems for Some Equitable Labelings |
| Published in: | Issue 3, (Vol. 8) / 2014 |
| Publishing date: | 2014-10-30 |
| Pages: | 38-42 |
| Author(s): | VAIDYA K. Samir , BARASARA Chirag M. |
| Abstract. | cordial labeling or an equitable labeling is a weaker version of Graceful and Harmonious labelings. At present many variants of equitable labeling are available. We discuss embedding and NP-complete problems in the context of some variants of equitable labeling such as E-cordial labeling, product cordial labeling, edge product cordial labeling, total product cordial labeling and prime cordial labeling. This work also rules out any possibility of forbidden subgraph characterizations for such labelings. |
| Keywords: | Graph Labeling; Equitable Labeling; Embedding Of Graphs; NP-complete Problems. |
| References: | 1. B. D. Acharya, Embedding Graphs in Graceful Graphs, Report, Mehta Research Institute, Allahabad, 1980. 2. B. D. Acharya, S. B. Rao and S. Arumugam, Embeddings and NP-Complete problems for Graceful Graphs in: B. D. Acharya, S. Arumugam and A. Rosa (Eds.), Labeling of Discrete Structures and Applications, Narosa Publishing House, New Delhi, pp. 57-62, 2008. 3. R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory, 2/e, Springer, New York, 2012. 4. I. Cahit, Cordial Graphs: A weaker version of graceful and harmonious graphs, Ars Combinatoria, vol. 23, pp. 201-207, 1987. 5. J. A. Gallian, A Dynamic Survey of Graph Labeling, The electronic journal of combinatorics, vol. 19, #DS6, 2012. 6. M. R. Garey and D. S. Johnson, Computers and Intractability - A guide to the theory of NP - Completeness, W. H. Freeman and Company, 1979. 7. S. W. Golomb, How to number a graph in: R. C. Read(ed.), Graph theory and Computing, Academic Press, New York, pp. 23-37, 1972. 8. R. L. Graham and N. J. A.Sloane, On additive bases and harmonious graphs, SIAM Journal on Algebraic and Discrete Methods, vol. 1(4), pp. 382-404, 1980. 9. K. L. Princy, Some Studies on Set Valuations of Graphs - Embedding and NP-Completeness, Ph.D. thesis, Kannur University, Kerala, 2007. 10. G. Ringel, Problem 25 in: Theory of graphs and its applications (Proceedings of Symposium Smolenice 1963, Prague), pp. 162, 1964. 11. A. Rosa, On certain valuations of the vertices of a graph, Theory of graphs, International Symposium, Rome, July (1966), Gordon and Breach, New York and Dunod Paris, pp. 349-355, 1967. 12. M. Sundaram, R. Ponraj and S. Somasundaram, Product cordial labeling of graphs, Bulletin of Pure and Applied Sciences (Mathematics & Statistics), vol. 23E, pp. 155-163, 2004. 13. M. Sundaram, R. Ponraj, and S. Somasundaram, Prime cordial labeling of graphs, J. Indian Acad. Math., vol. 27, pp. 373-390, 2005. 14. M. Sundaram, R. Ponraj, and S. Somasundaram, Total product cordial labeling of graphs, Bulletin Pure and Applied Sciences (Mathematics & Statistics), vol. 25E, pp. 199-203, 2006. 15. S. K. Vaidya and P. L. Vihol, Embedding and NP-Complete Problems for 3-Equitable Graphs, International Journal of Contemporary Advanced Mathematics, vol. 2(1), pp. 1-7, 2011. 16. S. K. Vaidya and C. M. Barasara, Edge Product Cordial Labeling of Graphs, Journal of Mathematical and Computational Science, vol. 2(5), pp. 1436 – 1450, 2012. 17. R. Yilmaz and I. Cahit, E-cordial graphs, Ars Combinatoria, vol. 46, pp. 251-266, 1997. |
| Back to the journal content | |
