On minimal forbidden subgraph characterizations of balanced graphs

Mostrar todas las versiones(4)

A graph is balanced if its clique-matrix contains no edge-vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we prov...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Bonomo, F., Durán, G., Safe, M.D., Wagler, A.K.
Formato:	Artículo publishedVersion
Publicado:	2013
Materias:	Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Line graph Perfect graph Directed graphs Graphic methods Characterization
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_0166218X_v161_n13-14_p1925_Bonomo https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v161_n13-14_p1925_Bonomo_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-paper_0166218X_v161_n13-14_p1925_Bonomo_oai
record_format	dspace
spelling	I28-R145-paper_0166218X_v161_n13-14_p1925_Bonomo_oai2024-08-16 Bonomo, F. Durán, G. Safe, M.D. Wagler, A.K. 2013 A graph is balanced if its clique-matrix contains no edge-vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes. © 2013 Elsevier B.V. All rights reserved. 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:Safe, M.D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf http://hdl.handle.net/20.500.12110/paper_0166218X_v161_n13-14_p1925_Bonomo info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Discrete Appl Math 2013;161(13-14):1925-1942 Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graph Perfect graph Directed graphs Graphic methods Characterization On minimal forbidden subgraph characterizations of balanced graphs info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v161_n13-14_p1925_Bonomo_oai
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-145
collection	Repositorio Digital de la Universidad de Buenos Aires (UBA)
topic	Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graph Perfect graph Directed graphs Graphic methods Characterization
spellingShingle	Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graph Perfect graph Directed graphs Graphic methods Characterization Bonomo, F. Durán, G. Safe, M.D. Wagler, A.K. On minimal forbidden subgraph characterizations of balanced graphs
topic_facet	Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graphs Perfect graphs Balanced graphs Bipartite graphs Hereditary clique-Helly graphs Line graph Perfect graph Directed graphs Graphic methods Characterization
description	A graph is balanced if its clique-matrix contains no edge-vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes. © 2013 Elsevier B.V. All rights reserved.
format	Artículo Artículo publishedVersion
author	Bonomo, F. Durán, G. Safe, M.D. Wagler, A.K.
author_facet	Bonomo, F. Durán, G. Safe, M.D. Wagler, A.K.
author_sort	Bonomo, F.
title	On minimal forbidden subgraph characterizations of balanced graphs
title_short	On minimal forbidden subgraph characterizations of balanced graphs
title_full	On minimal forbidden subgraph characterizations of balanced graphs
title_fullStr	On minimal forbidden subgraph characterizations of balanced graphs
title_full_unstemmed	On minimal forbidden subgraph characterizations of balanced graphs
title_sort	on minimal forbidden subgraph characterizations of balanced graphs
publishDate	2013
url	http://hdl.handle.net/20.500.12110/paper_0166218X_v161_n13-14_p1925_Bonomo https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v161_n13-14_p1925_Bonomo_oai
work_keys_str_mv	AT bonomof onminimalforbiddensubgraphcharacterizationsofbalancedgraphs AT durang onminimalforbiddensubgraphcharacterizationsofbalancedgraphs AT safemd onminimalforbiddensubgraphcharacterizationsofbalancedgraphs AT waglerak onminimalforbiddensubgraphcharacterizationsofbalancedgraphs
_version_	1809357091424436224

On minimal forbidden subgraph characterizations of balanced graphs

Ejemplares similares