Artículo
Null decomposition of bipartite graphs without cycles of length 0 modulo 4
Fecha de publicación:
04/2021
Editorial:
Elsevier Science Inc.
Revista:
Linear Algebra and its Applications
ISSN:
0024-3795
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
In this work we study the null space of bipartite graphs without cycles of length 0 modulo 4 (denoted as C4k-free bipartite graphs), and its relation to structural properties. We extend the Null Decomposition of trees, introduced by Jaume and Molina (2018), to C4k-free bipartite graphs. This decomposition uses the null space of the adjacency matrix of a graph G to decompose it into two different types of graphs: CN(G) and CS(G). CN has perfect matching number. CS(G) has a unique maximum independent set. We obtain formulas for the independence number and the matching number of a C4k-free bipartite graph using this decomposition. We also show how the number of maximum matchings and the number of maximum independent sets in a C4k-free bipartite graph are related to its null decomposition.
Palabras clave:
BIPARTITE GRAPHS
,
CYCLES
,
INDEPENDENT SETS
,
MATCHING SETS
,
NULL SPACE
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(IMASL)
Articulos de INST. DE MATEMATICA APLICADA DE SAN LUIS
Articulos de INST. DE MATEMATICA APLICADA DE SAN LUIS
Citación
Jaume, Daniel Alejandro; Molina Munafó, Luis Gonzalo; Pastine, Adrián Gabriel; Null decomposition of bipartite graphs without cycles of length 0 modulo 4; Elsevier Science Inc.; Linear Algebra and its Applications; 614; 4-2021; 176-196
Compartir
Altmétricas