Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

(461.25KB)
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
Volume - 2   Issue - 1    |    Publication Date - July / August 2011  Table of Contents
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.
CITED BY (3)  
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