On balanced graphs

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....

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Bonomo, Flavia, Durán, Guillermo A., Lin, Min Chih
Publicado:	2006
Materias:	0-1 matrices Algorithms Balanced graphs Balanced hypergraphs Clique graphs Domination Graph theory Matrix algebra Polynomials Mathematical programming
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00255610_v105_n2-3_p233_Bonomo http://hdl.handle.net/20.500.12110/paper_00255610_v105_n2-3_p233_Bonomo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_00255610_v105_n2-3_p233_Bonomo
record_format	dspace
spelling	paper:paper_00255610_v105_n2-3_p233_Bonomo2023-06-08T14:53:11Z On balanced graphs Bonomo, Flavia Durán, Guillermo A. Lin, Min Chih 0-1 matrices Algorithms Balanced graphs Balanced hypergraphs Clique graphs Domination Algorithms Graph theory Matrix algebra Polynomials Balanced graphs Balanced hypergraphs Clique graphs Domination Mathematical programming 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. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2006 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00255610_v105_n2-3_p233_Bonomo http://hdl.handle.net/20.500.12110/paper_00255610_v105_n2-3_p233_Bonomo
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	0-1 matrices Algorithms Balanced graphs Balanced hypergraphs Clique graphs Domination Algorithms Graph theory Matrix algebra Polynomials Balanced graphs Balanced hypergraphs Clique graphs Domination Mathematical programming
spellingShingle	0-1 matrices Algorithms Balanced graphs Balanced hypergraphs Clique graphs Domination Algorithms Graph theory Matrix algebra Polynomials Balanced graphs Balanced hypergraphs Clique graphs Domination Mathematical programming Bonomo, Flavia Durán, Guillermo A. Lin, Min Chih On balanced graphs
topic_facet	0-1 matrices Algorithms Balanced graphs Balanced hypergraphs Clique graphs Domination Algorithms Graph theory Matrix algebra Polynomials Balanced graphs Balanced hypergraphs Clique graphs Domination Mathematical programming
description	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.
author	Bonomo, Flavia Durán, Guillermo A. Lin, Min Chih
author_facet	Bonomo, Flavia Durán, Guillermo A. Lin, Min Chih
author_sort	Bonomo, Flavia
title	On balanced graphs
title_short	On balanced graphs
title_full	On balanced graphs
title_fullStr	On balanced graphs
title_full_unstemmed	On balanced graphs
title_sort	on balanced graphs
publishDate	2006
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00255610_v105_n2-3_p233_Bonomo http://hdl.handle.net/20.500.12110/paper_00255610_v105_n2-3_p233_Bonomo
work_keys_str_mv	AT bonomoflavia onbalancedgraphs AT duranguillermoa onbalancedgraphs AT linminchih onbalancedgraphs
_version_	1768546148407050240

On balanced graphs

Ejemplares similares