Volume 2, Issue 4, December 2017, Page: 119-124
Some Forbidden Subgraphs of Trees Being Opposition Graphs
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
Received: Mar. 17, 2017;       Accepted: Mar. 28, 2017;       Published: May 15, 2017
DOI: 10.11648/j.dmath.20170204.11      View  1930      Downloads  160
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.
Keywords
Trees, Orientations, Opposition Graphs
To cite this article
In-Jen Lin, Yi-Wu Chang, Cheng-Wei Pan, Some Forbidden Subgraphs of Trees Being Opposition Graphs, International Journal of Discrete Mathematics. Vol. 2, No. 4, 2017, pp. 119-124. doi: 10.11648/j.dmath.20170204.11
Copyright
Copyright © 2017 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Reference
[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.
Browse journals by subject