Decomposing split graphs into locally irregular graphs

Autor(es)

Lintzmayer, C. N. ^[1] ; Mota, G. O. ^[2] ; Sambinelli, M. ^[1]

Afiliação do(s) autor(es)

^[1] Fed Univ ABC, Ctr Math Comp & Cognit, Sao Paulo - Brazil

^[2] Univ Sao Paulo, Inst Math & Stat, Sao Paulo - Brazil

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE APPLIED MATHEMATICS; v. 292, p. 33-44, MAR 31 2021.
• Citações Web of Science: 0

Resumo

A graph is locally irregular if any pair of adjacent vertices have distinct degrees. A locally irregular decomposition of a graph G is a decomposition D of G such that every subgraph H is an element of D is locally irregular. A graph is said to be decomposable if it admits a locally irregular decomposition. We prove that any decomposable split graph can be decomposed into at most three locally irregular subgraphs and we characterize all split graphs whose decomposition can be into one, two or three locally irregular subgraphs. (C) 2020 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 17/23623-4 - Problemas de partição em grafos e dígrafos
• Beneficiário: Maycon Sambinelli
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores
• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático