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.
| Published in | Applied and Computational Mathematics (Volume 2, Issue 3) |
| DOI | 10.11648/j.acm.20130203.13 |
| Page(s) | 86-91 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2013. Published by Science Publishing Group |
Self Complementary, Brittle, Quasi Chordal, No Mid, No End
| [1] | V. Chvátal, Perfect graph seminar, McGill university, Montreal, (1983). |
| [2] | 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. |
| [3] | M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, (1980). |
| [4] | I. Gorgos, C.T. Hoang and V. Voloshin, A note on quasi-triangulated graphs, SIAM Journal of Discrete Mathematics, 20 (2006) 597-602. |
| [5] | C.T. Hoàng and B.A. Reed, Some classes of perfectly orderable graphs, J. Graph Theory, 13 (1989) 445-463. |
| [6] | C.T. Hoàng and N. Khouzam, On brittle graphs, J. Graph Theory, 12 (1988) 391-404 |
| [7] | C.T. Hoàng and N.V.R. Mahadev, A note on perfect orders, Discrete Mathematics, 74 (1989) 77-84. |
| [8] | C.T. Hoàng, Recognizing quasi-triangulated graphs in O(nm) time, Manuscript, (unpublished). |
| [9] | 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. |
| [10] | J.L. Ramirez and B.A. Reed, Perfect graphs, John Wiley and Sons, (2000). |
| [11] | A.A. Schaffer, Recognizing brittle graphs: remarks on a paper of Hoang and Khouzam, Discrete Applied Mathematics, 31 (1991) 29-35. |
| [12] | J.P. Spinrad and J. Johnson, Brittle and Bipolarizable graph recognition, Vanderbilt Uni. Comp. Sci. Deptt., Technical Report (1998). |
| [13] | J.P. Spinrad, Recognizing quasi-triangulated graphs, Disc. App. Math., 138 (2004) 203-213. |
| [14] | V.I. Voloshin, Quasi-triangulated graphs recognition program, Algorithms and programs, P006124, Moscow, Russian, 1983 (in Russian). |
| [15] | V.I. Voloshin, Quasi-triangulated graphs, Preprint, 5569-81, Kishinev state university, Kishinev, Moldova, 1981( in Russian). |
| [16] | J. Yellen and J Gross, Graph Theory and its Applications, CRC Press (USA), 1999. |
APA Style
Parvez Ali, Merajuddin, Syed Ajaz Kareem Kirmani. (2013). A Note on Self Complementary Brittle and Self Complementary Quasi Chordal Graphs. Applied and Computational Mathematics, 2(3), 86-91. https://doi.org/10.11648/j.acm.20130203.13
ACS Style
Parvez Ali; Merajuddin; Syed Ajaz Kareem Kirmani. A Note on Self Complementary Brittle and Self Complementary Quasi Chordal Graphs. Appl. Comput. Math. 2013, 2(3), 86-91. doi: 10.11648/j.acm.20130203.13
AMA Style
Parvez Ali, Merajuddin, Syed Ajaz Kareem Kirmani. A Note on Self Complementary Brittle and Self Complementary Quasi Chordal Graphs. Appl Comput Math. 2013;2(3):86-91. doi: 10.11648/j.acm.20130203.13
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.acm.20130203.13,
author = {Parvez Ali and Merajuddin and Syed Ajaz Kareem Kirmani},
title = {A Note on Self Complementary Brittle and Self Complementary Quasi Chordal Graphs},
journal = {Applied and Computational Mathematics},
volume = {2},
number = {3},
pages = {86-91},
doi = {10.11648/j.acm.20130203.13},
url = {https://doi.org/10.11648/j.acm.20130203.13},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20130203.13},
abstract = {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.},
year = {2013}
}
TY - JOUR T1 - A Note on Self Complementary Brittle and Self Complementary Quasi Chordal Graphs AU - Parvez Ali AU - Merajuddin AU - Syed Ajaz Kareem Kirmani Y1 - 2013/07/20 PY - 2013 N1 - https://doi.org/10.11648/j.acm.20130203.13 DO - 10.11648/j.acm.20130203.13 T2 - Applied and Computational Mathematics JF - Applied and Computational Mathematics JO - Applied and Computational Mathematics SP - 86 EP - 91 PB - Science Publishing Group SN - 2328-5613 UR - https://doi.org/10.11648/j.acm.20130203.13 AB - 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. VL - 2 IS - 3 ER -
Email: