On Polar, Trivially Perfect Graphs
Keywords:
Polar graphs, trivial perfect graphs, weakly decomposition, recognition algorithms, optimization algorithmsAbstract
During the last decades, different types of decompositions have been processed in the field of graph theory. In various problems, for example in the construction of recognition algorithms, frequently appears the so-called weakly decomposition of graphs.
Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. Recognizing a polar graph is known to be NP-complete. For this class of graphs, polynomial algorithms for the maximum stable set problem are unknown and algorithms for the dominating set problem are also NP-complete.
In this paper we characterize the polar graphs using the weakly decomposition, give a polynomial time algorithm for recognizing graphs that are both trivially perfect and polar, and directly calculate the domination number. For the stability number and clique number, we give polynomial time algorithms.Â
References
C. Berge, Graphs, North-Holland, Amsterdam, 1985.
A. A. Bertoss, Dominating sets for split and bipartite graphs, Inform. Process. Lett., 19:37- 40, 1984. http://dx.doi.org/10.1016/0020-0190(84)90126-1
Z. A. Chernyak, A. A. Chernyak, About recognizing (α,ω)-classes of polar graphs, Discrete Mathematics, 62:133-138, 1986. http://dx.doi.org/10.1016/0012-365X(86)90113-5
D. G. Corneil, Y. Perl, Clustering and domination in perfect graphs, Discrete Appl. Math., 9:27-39, 1984. http://dx.doi.org/10.1016/0166-218X(84)90088-X
C. Croitoru, E. Olaru, M. Talmaciu, Confidentially connected graphs, Proceedings of the international conference "The risk in contemporany economy", in Annals of the University "Dunarea de Jos" of Galati, Suppliment to Tome XVIII (XXII), 2000.
C. Croitoru, M. Talmaciu, A new graph search algorithm and some applications, presented at ROSYCS 2000, Univ. "Al.I.Cuza" IaÅŸi, 2000.
T. Ekim, P. Heggernes, D. Meister, Polar permutation graphs, Report in Informatics, Report no 385, March 2009.
T. Ekim, P. Hell, J. Stacho, D. de Werra, Polarity of Chordal Graphs, Discrete Applied Mathematics, Volume 156, 2469-2479, 2008. http://dx.doi.org/10.1016/j.dam.2008.01.026
T. Ekim, N. V. R. Mahadev, D. de Werra, Polar cographs, Discrete Applied Mathematics, Volume 156, 1652-1660, 2008. http://dx.doi.org/10.1016/j.dam.2007.08.025
M. C. Golumbic, "Trivially perfect graphs", Discrete Math. 24:105-107, 1978. http://dx.doi.org/10.1016/0012-365X(78)90178-4
D. Koschutzki, K. Lehman, L. Peaters, S. Richter, Tenfelde-Padehl and O. Zlotowski, "Centrality Indices", Lecture Notes in Computer Sciences, Springer Berlin / Heidelberg, Network Analysis, 16-61, 2005.
V. V. Lozin, R. Mosca, Polar Graphs and Maximal Independent Sets, Rutcor Research Report 4-2004, February, 2004.
M. Talmaciu, Decomposition Problems in the Graph Theory with Applications in Combinatorial Optimization - Ph. D. Thesis, University "Al. I. Cuza" Iasi, Romania, 2002.
M. Talmaciu, E. Nechita, Recognition Algorithm for diamond-free graphs, Informatica, Vol. 18, No. 3, 457-462, 2007.
M. Talmaciu, E. Nechita, An algorithm for the bisection problem on trivially perfect graphs, BICS 2008, Amer. Inst. Physics, Volume 1117:60-66, 2008.
http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc-314.html.
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
