DOMINATION TRIANGLE GRAPHS AND UPPER BOUND GRAPHS
Abstract
In this article we introduce and study a proper subclass of triangle graphs, namely, the domination triangle graphs. A graph G is called a domination triangle graph if for every minimal dominating set D of G and any adjacent vertices u and v not contained in D, there exists a vertex w є D such that the set {u, v, w} induces a triangle in G. We propose a number of characterizations of domination triangle graphs which show in particular that this class of graphs coincides with a well-known class of upper bound graphs and a class of irredundance triangle graphs. We establish the computational complexity and the complexity of approximation for some independence and domination-related graph-theoretical parameters within domination triangle graphs.
About the Authors
Yu. A. KARTYNNIK
Белорусский государственный университет, Минск
Belarus
Belarus
Yu. L. ORLOVICH
Белорусский государственный университет, Минск
Belarus
Belarus
References
1. Orlovich Y., Zverovich I. // Electronic Notes in Discrete Math. 2007. Vol. 28. P. 341–348.
2. McAvaney K., Robertson J., De Temple D. // Discrete Math. 1993. Vol. 113, N 1–3. P. 131–142.
3. Anbeek C., De Temple D., McAvaney K., Robertson J. // Australas. J. Comb. 1997. Vol. 16. P. 285–293.
4. Kloks T., Lee C.-M., Liu J., Müller H. // Lect. Notes Comput. Sci. 2003. Vol. 2880. P. 273–283.
5. Орлович Ю. Л., Гордон В. С., Блажевич Я. и др. // Докл. НАН Беларуси. 2009. Т. 53, № 1. С. 39–44.
6. Miklavič Š., Milanič M. // Discrete Appl. Math. 2011. Vol. 159, N 11. P. 1148–1159.
7. Orlovich Y., Blazewicz J., Dolgui A. et al. // Discrete Math. 2011. Vol. 311, N 16. P. 1670–1680.
8. Levit V. E., Milanič M. // Discrete Appl. Math. 2014. Vol. 165. P. 205–212.
9. Payan C. // Discrete Math. 1980. Vol. 29, N 1. P. 47–52.
10. Mahadev N. V. R., Peled U. N., Sun F. // J. Graph Theory. 1994. Vol. 18, N 3. P. 281–299.
11. Mahadev N. V. R., Peled U. N. Threshold graphs and related topics. Amsterdam: Elsevier, 1995.
12. De Temple D., Robertson J. M. // J. Aust. Math. Soc., Ser. A. 1989. Vol. 47, N 3. P. 391–398.
13. McMorris F. R., Zaslavsky T. // J. Combin. Inform. System Sci. 1982. Vol. 7, N 2. P. 134–138.
14. Skowrońsk M., Sysło M. // Discrete Appl. Math. 1984. Vol. 7. P. 201–208.
15. Cheston G. A., Jap T. S. // J. Graph Algorithms Appl. 2006. Vol. 10, N 2. P. 159–190.
16. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М., 1990.
17. Berge C. Graphs and hypergraphs. New York: American Elsevier Publishing Company, 1976.
18. Bollobás B., Cockayne E. J. // J. Graph Theory. 1979. Vol. 3, N 3. P. 241–250.
19. Cockayne E. J., Hedetniemi S. T., Miller D. J. // Canad. Math. Bull. 1978. Vol. 21. P. 461–468.
20. Sampathkumar E., Neeralagi P. S. // Indian J. Pure Appl. Math. 1985. Vol. 16. P. 126–132.
21. Sampathkumar E., Neeralagi P. S. // J. Combin. Inf. Syst. Sci. 1994. Vol. 19. P. 139–145.
22. Cheston G. A., Hare E. O., Hedetniemi S. T., Laskar R. C. // Congr. Numer. 1988. Vol. 67. P. 105–113.
23. Lundgren J. R., Maybee J. S. // Congr. Numer. 1983. Vol. 40. P. 189–193.
24. Ogawa K., Tagusari S., Tsuchiya M. // Discrete Math. 2009. Vol. 309. P. 3659–3663.
25. Cheston G. A., Fricke G. // Discrete Appl. Math. 1994. Vol. 55. P. 241–258.
26. Raz R., Safra S. // Proc. of the 29th annual ACM symp. on theory of computing. New York: ACM Press, 1997. P. 475–484.
27. Paz A., Moran S. // Theor. Comput. Sci. 1981. Vol. 15. P. 251–277.
28. Kann V. On the approximability of NP-complete optimization problems: Ph. D. thesis / Royal Institute of Technology. Stockholm, 1992.
Review
Views: 745
Email this article 