On balanced graphs

• 成果类型: Article; Proceedings Paper
• 署名作者: Bonomo, F; Durán, G; Lin, MC; Szwarcfiter, JL
• 署名单位: University of Buenos Aires; Universidad de Chile; Universidade Federal do Rio de Janeiro; Universidade Federal do Rio de Janeiro
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0651-y
• 发表日期: 2006
• 页码: 233-250
• 关键词: algorithm; clique

摘要

Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs. Two of them are characterized by 0-1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial time combinatorial algorithms for the problems of stable set, clique-independent set and clique-transversal for one of these subclasses of balanced graphs. Finally, we analyse the behavior of balanced graphs and these four subclasses under the clique graph operator.