Applied and Computational Mathematics
Volume 2, Issue 3, June 2013, Pages: 86-91
Received: Jun. 2, 2013;
Published: Jul. 20, 2013
Views 3207 Downloads 111
Parvez Ali, Department of Mathematics, Maharana Pratap Engineering College, Mandhana , Kanpur, INDIA
Merajuddin , Department of Applied Mathematics, Faculty of Engineering, Aligarh Muslim University, Aligarh, INDIA
Syed Ajaz Kareem Kirmani, College of Engineering Unayzah, Qassim University, KINGDOM OF SAUDI ARABIA
In this paper we deal with some classes of self-complementary (sc) perfectly orderable graphs namely sc brittle, sc quasi chordal graphs and propose algorithms for these classes. We obtain some results on these classes and an algorithm is proposed based on these results that recognize these classes. We also compile a catalogue for these classes up to 17 vertices.
Syed Ajaz Kareem Kirmani,
A Note on Self Complementary Brittle and Self Complementary Quasi Chordal Graphs, Applied and Computational Mathematics.
Vol. 2, No. 3,
2013, pp. 86-91.
V. Chvátal, Perfect graph seminar, McGill university, Montreal, (1983).
E.M. Eschen, J.L. Johnson, J.P. Spinrad and R. Sritharan, Recognition of some perfectly orderable graph classes, Discrete Applied Mathematics, 128 (2003) 335-373.
M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, (1980).
I. Gorgos, C.T. Hoang and V. Voloshin, A note on quasi-triangulated graphs, SIAM Journal of Discrete Mathematics, 20 (2006) 597-602.
C.T. Hoàng and B.A. Reed, Some classes of perfectly orderable graphs, J. Graph Theory, 13 (1989) 445-463.
C.T. Hoàng and N. Khouzam, On brittle graphs, J. Graph Theory, 12 (1988) 391-404
C.T. Hoàng and N.V.R. Mahadev, A note on perfect orders, Discrete Mathematics, 74 (1989) 77-84.
C.T. Hoàng, Recognizing quasi-triangulated graphs in O(nm) time, Manuscript, (unpublished).
C.T. Hoàng, S. Hougardy, F, Maffray and N.V.R. Mahadev, On simplicial and Co-simplicial vertices in graphs, Discrete Applied Mathematics, 138 (2004) 117-132.
J.L. Ramirez and B.A. Reed, Perfect graphs, John Wiley and Sons, (2000).
A.A. Schaffer, Recognizing brittle graphs: remarks on a paper of Hoang and Khouzam, Discrete Applied Mathematics, 31 (1991) 29-35.
J.P. Spinrad and J. Johnson, Brittle and Bipolarizable graph recognition, Vanderbilt Uni. Comp. Sci. Deptt., Technical Report (1998).
J.P. Spinrad, Recognizing quasi-triangulated graphs, Disc. App. Math., 138 (2004) 203-213.
V.I. Voloshin, Quasi-triangulated graphs recognition program, Algorithms and programs, P006124, Moscow, Russian, 1983 (in Russian).
V.I. Voloshin, Quasi-triangulated graphs, Preprint, 5569-81, Kishinev state university, Kishinev, Moldova, 1981( in Russian).
J. Yellen and J Gross, Graph Theory and its Applications, CRC Press (USA), 1999.