Home > CSC-OpenAccess Library > Manuscript Information

This is an Open Access publication published under CSC-OpenAccess Policy.

Embedding and np-Complete Problems
for 3-Equitable Graphs

S. K. Vaidya, P. L. Vihol

Pages - 1 - 7 | Revised - 01-05-2011 | Published - 31-05-2011

MORE INFORMATION

KEYWORDS

Embedding, NP-Complete, 3-Equitable Graph

ABSTRACT

We present here some important results in connection with 3-equitable graphs. We prove that any graph G can be embedded as an induced subgraph of a 3-equitable graph. We have also discussed some properties which are invariant under embedding. This work rules out any possibility of obtaining a forbidden subgraph
characterization for 3-equitable graphs.

1 | ï»¿VAIDYA, S. K., & BARASARA, C. M. (2014). Embedding and NP-complete Problems for Some Equitable Labelings. Journal of Applied Computer Science and Mathematics, 18(8). |

2 | Gallian, J. A. (2014). Graph labeling. The Electronic Journal of Combinatorics, 1000, DS6-Dec. |

3 | Vaidya, S. K., & Barasara, C. M. On Embedding and NP-Complete Problems of Equitable Labelings. |

1 | Google Scholar |

2 | CiteSeerX |

3 | refSeek |

4 | Scribd |

5 | SlideShare |

6 | PdfSR |

1 | D B West. Introduction To Graph Theory, Prentice-Hall of India, 2001 |

2 | I Niven and H Zuckerman. An Introduction to the Theory of numbers, Wiley Eastern, New Delhi, 1972. |

3 | J A Gallian. A dynamic survey of graph labeling, The Electronics Journal of Combinatorics, 17, #DS6 , 2010. |

4 | L W Beineke and S M Hegde. “Strongly Multiplicative Graphs”, Discuss.Math.Graph Theory, 21, pp. 63-75, 2001. |

5 | A Rosa. “On Certain Valuation of the Vertices of a Graph”, Theory of Graphs (Internat. Symposium, Rome, July 1966) Gordon and Breach, N.Y. and Dunod Paris, pp. 349-355, 1967. |

6 | S W Golomb. “How to Number a Graph” in: Graph Theory and Computing, R.C.Read, (Eds.), Academic Press, New York, pp. 23-37, 1972. |

7 | I Cahit. “On Cordial and 3-equitable Labeling of Graphs”,Utilitas.Math, 37, pp. 189-198, 1990. |

8 | B D Acharya. S B Rao, S Arumugam, “Embeddings and NP-Complete problems for Graceful Graphs” in: B D Acharya, S Arumugam, A Rosa (Eds.),Labeling of Discrete Structures and Applications, Narosa Publishing House, New Delhi, pp. 57-62, 2008. |

9 | M R Garey and D S Johnson. Computers and Intractability- A guide to the theory of NPCompleteness, W.H.Freeman and Company, 1979. |

Professor S. K. Vaidya

Saurashtra University - India

samirkvaidya@yahoo.co.in

Mr. P. L. Vihol

Government Polytechnic - India