Paper Info
Title
On Polar, Trivially Perfect Graphs
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.
Year
DOI
Venue
2010
10.15837/ijccc.2010.5.2257
INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL
Keywords
Field
DocType
Polar graphs, trivial perfect graphs, weakly decomposition, recognition algorithms, optimization algorithms
Discrete mathematics,Indifference graph,Modular decomposition,Combinatorics,Chordal graph,Cograph,Trivially perfect graph,Pathwidth,Mathematics,Maximal independent set,Split graph
Journal
Volume
Issue
ISSN
5
5
1841-9836
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Mihai Talmaciu142.83
Elena Nechita241.48