On Polar, Trivially Perfect Graphs

Authors

  • Mihai Talmaciu University of Bacău, Romania
  • Elena Nechita University of Bacău, Romania

Keywords:

Polar graphs, trivial perfect graphs, weakly decomposition, recognition algorithms, optimization algorithms

Abstract

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

2010-12-01

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.