Some Forbidden Subgraphs of Trees Being Opposition Graphs

In-Jen Lin; Yi-Wu Chang; Cheng-Wei Pan

doi:doi:10.11648/j.dmath.20170204.11

| Peer-Reviewed

Some Forbidden Subgraphs of Trees Being Opposition Graphs

In-Jen Lin, Yi-Wu Chang, Cheng-Wei Pan

Published in International Journal of Discrete Mathematics (Volume 2, Issue 4)

Received: 17 March 2017 Accepted: 28 March 2017 Published: 15 May 2017

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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 P_n, C_n with n≥3 and n = 4k, for k∈ℕ, are opposition graphs and some families of graphs such as the complement of T_n, C_n 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

Plain Text BibTeX RIS

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

In-Jen Lin

Department of Computer Science and Engineering, National Taiwan Ocean University, Keelung, Taiwan
Yi-Wu Chang

Department of Mathematical Sciences, National Chengchi University, Taipei, Taiwan
Cheng-Wei Pan

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

Download PDF

Sections

Plain Text BibTeX RIS

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