Weak harmonic labeling of graphs and multigraphs

Abstract

En este artículo, introducimos el concepto de etiquetado armónico débil de un grafo, una generalización del concepto de etiquetado armónico definido recientemente por Benjamini, Cyr, Procaccia y Tessler, que permite su extensión a grafos finitos y grafos con hojas. Presentamos varias familias de ejemplos y proporcionamos varias construcciones que extienden un etiquetado armónico débil dado a grafos mayores. En particular, utilizamos modelos débiles finitos para producir nuevos ejemplos de etiquetados armónicos (fuertes). Como resultado principal, proporcionamos una caracterización de grafos débilmente etiquetados en términos de subconjuntos armónicos de Z y mostramos evidencia cuantitativa de la eficiencia de este método para calcular todos los grafos finitos débilmente etiquetados, en oposición a un cálculo de búsqueda exhaustivo. En particular, caracterizamos grafos etiquetados armónicamente según la definición de Benjamini et al. Extendemos las definiciones y los resultados principales al caso de multigrafos y etiquetados totales.

In this article we introduce the notion of weak harmonic labeling of a graph, a generalization of the concept of harmonic labeling defined recently by Benjamini, Cyr, Procaccia and Tessler that allows extension to finite graphs and graphs with leaves. We present various families of examples and provide several constructions that extend a given weak harmonic labeling to larger graphs. In particular, we use finite weak models to produce new examples of (strong) harmonic labelings. As a main result, we provide a characterization of weakly labeled graphs in terms of harmonic subsets of Z and exhibit quantitative evidence of the efficiency of this method for computing all weakly labeled finite graphs as opposed to an exhaustive search calculation. In particular, we characterize harmonically labeled graphs as defined by Benjamini et al. We further extend the definitions and main results to the case of multigraphs and total labelings.

Neste artigo, introduzimos a noção de rotulagem harmônica fraca de um grafo, uma generalização do conceito de rotulagem harmônica definido recentemente por Benjamini, Cyr, Procaccia e Tessler, que permite a extensão a grafos finitos e grafos com folhas. Apresentamos várias famílias de exemplos e fornecemos diversas construções que estendem uma dada rotulagem harmônica fraca a grafos maiores. Em particular, usamos modelos fracos finitos para produzir novos exemplos de rotulagens harmônicas (fortes). Como resultado principal, fornecemos uma caracterização de grafos fracamente rotulados em termos de subconjuntos harmônicos de Z e exibimos evidências quantitativas da eficiência desse método para calcular todos os grafos finitos fracamente rotulados, em oposição a um cálculo de busca exaustivo. Em particular, caracterizamos grafos harmonicamente rotulados conforme definido por Benjamini et al. Estendemos ainda mais as definições e os principais resultados para o caso de multigrafos e rotulagens totais.