A Note on Self Complementary Brittle and Self Complementary Quasi Chordal Graphs
Applied and Computational Mathematics
Volume 2, Issue 3, June 2013, Pages: 86-91
Received: Jun. 2, 2013; Published: Jul. 20, 2013
Views 3254      Downloads 117
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
Article Tools
Follow on us
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.
Self Complementary, Brittle, Quasi Chordal, No Mid, No End
To cite this article
Parvez Ali, Merajuddin , 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. doi: 10.11648/j.acm.20130203.13
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.
Science Publishing Group
1 Rockefeller Plaza,
10th and 11th Floors,
New York, NY 10020
Tel: (001)347-983-5186