| Peer-Reviewed

Some Forbidden Subgraphs of Trees Being Opposition Graphs

Received: 17 March 2017     Accepted: 28 March 2017     Published: 15 May 2017
Views:       Downloads:
Abstract

In this paper, we use the number of vertices with degree greater than or equal to 3 as a criterion for trees being opposition graphs. Finally, we prove some families of graphs such as the complement of Pn, Cn with n≥3 and n = 4k, for k∈ℕ, are opposition graphs and some families of graphs such as the complement of Tn, Cn with n≥3 and n ≠ 4k, for k∈ℕ, are not opposition graphs.

Published in International Journal of Discrete Mathematics (Volume 2, Issue 4)
DOI 10.11648/j.dmath.20170204.11
Page(s) 119-124
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), 2017. Published by Science Publishing Group

Keywords

Trees, Orientations, Opposition Graphs

References
[1] A. N. Trenk, Tolerance Graphs, Cambridge Univ Pr, 2004. J. Clerk Maxwell, A Treatise on Electricity and Magnetism, 3rd ed., vol. 2. Oxford: Clarendon, 1892, 68–73.
[2] Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad, Graph classes: A survey, in: SIAM Monographs on Discrete Math. Appl., vol. 3, Philadelphia, 1999.
[3] Van Bang Le, On opposition graphs, coalition graphs, and bipartite permutation graphs, Discrete Appl. Math. 168, 2014, 26–33.
[4] Vašek Chvátal, Which claw-free graphs are perfectly orderable? Discrete Appl. Math. 44, 1993, 39–63.
[5] Elaine M. Eschen, Julie L. Johnson, Jeremy P. Spinrad, R. Sritharan, Recognition of some perfectly orderable graph classes, Discrete Appl. Math. 128, 2003, 355–373.
[6] Chính T. Hoàng, Bruce A. Reed, Some classes of perfectly orderable graphs, J. Graph Theory 13, 1989, 445–463.
[7] D. Link, Stefan Olariu, A simple NC algorithm for Welsh-Powell opposition graphs, Int. J. Comput. Math. 41, 1991, 49–53.
[8] Stephan Olariu, All variations on perfectly orderable graphs, J. Combin. Theory Ser. B 45, 1988, 150–159.
[9] Stavros D. Nikolopoulos, Leonidas Palios, Recognizing HH-free, HHD-free, and Welsh–Powell opposition graphs, Discrete Math. Theor. Comput Sci. 8, 2006, 65–82.
[10] Stephan Olariu, J. Randall, Welsh–Powell opposition graphs, Inform. Process. Lett. 31, 1989, 43–46.
Cite This Article
  • APA Style

    In-Jen Lin, Yi-Wu Chang, Cheng-Wei Pan. (2017). Some Forbidden Subgraphs of Trees Being Opposition Graphs. International Journal of Discrete Mathematics, 2(4), 119-124. https://doi.org/10.11648/j.dmath.20170204.11

    Copy | Download

    ACS Style

    In-Jen Lin; Yi-Wu Chang; Cheng-Wei Pan. Some Forbidden Subgraphs of Trees Being Opposition Graphs. Int. J. Discrete Math. 2017, 2(4), 119-124. doi: 10.11648/j.dmath.20170204.11

    Copy | Download

    AMA Style

    In-Jen Lin, Yi-Wu Chang, Cheng-Wei Pan. Some Forbidden Subgraphs of Trees Being Opposition Graphs. Int J Discrete Math. 2017;2(4):119-124. doi: 10.11648/j.dmath.20170204.11

    Copy | Download

  • @article{10.11648/j.dmath.20170204.11,
      author = {In-Jen Lin and Yi-Wu Chang and Cheng-Wei Pan},
      title = {Some Forbidden Subgraphs of Trees Being Opposition Graphs},
      journal = {International Journal of Discrete Mathematics},
      volume = {2},
      number = {4},
      pages = {119-124},
      doi = {10.11648/j.dmath.20170204.11},
      url = {https://doi.org/10.11648/j.dmath.20170204.11},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.dmath.20170204.11},
      abstract = {In this paper, we use the number of vertices with degree greater than or equal to 3 as a criterion for trees being opposition graphs. Finally, we prove some families of graphs such as the complement of Pn, Cn with n≥3 and n = 4k, for k∈ℕ, are opposition graphs and some families of graphs such as the complement of Tn, Cn with n≥3 and n ≠ 4k, for k∈ℕ, are not opposition graphs.},
     year = {2017}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Some Forbidden Subgraphs of Trees Being Opposition Graphs
    AU  - In-Jen Lin
    AU  - Yi-Wu Chang
    AU  - Cheng-Wei Pan
    Y1  - 2017/05/15
    PY  - 2017
    N1  - https://doi.org/10.11648/j.dmath.20170204.11
    DO  - 10.11648/j.dmath.20170204.11
    T2  - International Journal of Discrete Mathematics
    JF  - International Journal of Discrete Mathematics
    JO  - International Journal of Discrete Mathematics
    SP  - 119
    EP  - 124
    PB  - Science Publishing Group
    SN  - 2578-9252
    UR  - https://doi.org/10.11648/j.dmath.20170204.11
    AB  - In this paper, we use the number of vertices with degree greater than or equal to 3 as a criterion for trees being opposition graphs. Finally, we prove some families of graphs such as the complement of Pn, Cn with n≥3 and n = 4k, for k∈ℕ, are opposition graphs and some families of graphs such as the complement of Tn, Cn with n≥3 and n ≠ 4k, for k∈ℕ, are not opposition graphs.
    VL  - 2
    IS  - 4
    ER  - 

    Copy | Download

Author Information
  • Department of Computer Science and Engineering, National Taiwan Ocean University, Keelung, Taiwan

  • Department of Mathematical Sciences, National Chengchi University, Taipei, Taiwan

  • Department of Mathematical Sciences, National Chengchi University, Taipei, Taiwan

  • Sections