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, F., Durán, G., Lin, M.C., Szwarcfiter, J.L.
Formato:	JOUR
Materias:	0-1 matrices Algorithms Balanced graphs Balanced hypergraphs Clique graphs Domination Graph theory Matrix algebra Polynomials Mathematical programming
Acceso en línea:	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	todo:paper_00255610_v105_n2-3_p233_Bonomo
record_format	dspace
spelling	todo:paper_00255610_v105_n2-3_p233_Bonomo2023-10-03T14:36:08Z On balanced graphs Bonomo, F. Durán, G. Lin, M.C. Szwarcfiter, J.L. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, F. Durán, G. Lin, M.C. Szwarcfiter, J.L. 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.
format	JOUR
author	Bonomo, F. Durán, G. Lin, M.C. Szwarcfiter, J.L.
author_facet	Bonomo, F. Durán, G. Lin, M.C. Szwarcfiter, J.L.
author_sort	Bonomo, F.
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
url	http://hdl.handle.net/20.500.12110/paper_00255610_v105_n2-3_p233_Bonomo
work_keys_str_mv	AT bonomof onbalancedgraphs AT durang onbalancedgraphs AT linmc onbalancedgraphs AT szwarcfiterjl onbalancedgraphs
_version_	1807321725218586624

On balanced graphs

Ejemplares similares