| Peer-Reviewed

A Note on Self Complementary Brittle and Self Complementary Quasi Chordal Graphs

Received: 2 June 2013     Published: 20 July 2013
Views:       Downloads:
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.

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

Keywords

Self Complementary, Brittle, Quasi Chordal, No Mid, No End

References
[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.
Cite This Article
  • 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

    Copy | Download

    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

    Copy | Download

    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

    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}
    }
    

    Copy | Download

  • 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  - 

    Copy | Download

Author Information
  • Department of Mathematics, Maharana Pratap Engineering College, Mandhana , Kanpur, INDIA

  • Department of Applied Mathematics, Faculty of Engineering, Aligarh Muslim University, Aligarh, INDIA

  • College of Engineering Unayzah, Qassim University, KINGDOM OF SAUDI ARABIA

  • Sections