Metrics Based on Finite Directed Graphs and Coding Invariants

DOI10.1109/TIT.2017.2765658zbMATH Open1390.94902arXiv1609.08067OpenAlexW2962926340MaRDI QIDQ4569191FDOQ4569191

Authors: Tuvi Etzion, Marcelo Firer, Roberto Assis Machado 

Publication date: 27 June 2018

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Given a finite directed graph with $n$ vertices, we define a metric $d_G$ on $mathbb{F}_q^n$, where $mathbb{F}_q$ is the finite field with $q$ elements. The weight of a word is defined as the number of vertices that can be reached by a directed path starting at the support of the vector. Two canonical forms, which do not affect the metric, are given to each graph. Based on these forms we characterize each such metric. We further use these forms to prove that two graphs with different canonical forms yield different metrics. Efficient algorithms to check if a set of metric weights define a metric based on a graph are given. We provide tight bounds on the number of metric weights required to reconstruct the metric. Furthermore, we give a complete description of the group of linear isometries of the graph metrics and a characterization of the graphs for which every linear code admits a $G$-canonical decomposition. Considering those graphs, we are able to derive an expression of the packing radius of linear codes in such metric spaces. Finally, given a directed graph which determines a hierarchical poset, we present sufficient and necessary conditions to ensure the validity of the MacWilliams Identity and the MacWilliams Extension Property.

Full work available at URL: https://arxiv.org/abs/1609.08067

Mathematics Subject Classification ID

Distance in graphs (05C12) Combinatorial codes (94B25) Applications of graph theory to circuits and networks (94C15)

Cited In (2)

• Combinatorial metrics: MacWilliams-type identities, isometries and extension property
• Classification of weighted posets and digraphs admitting the extended Hamming code to be a perfect code

This page was built for publication: Metrics Based on Finite Directed Graphs and Coding Invariants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4569191)