کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428821 | 686938 | 2016 | 5 صفحه PDF | دانلود رایگان |
• We study functions vanishing on each cycle of a directed graph.
• The number of such functions depends on whether or not the underlying undirected graph is bipartite.
• If every edge is one-way, then the number of such functions depends on the number of strongly connected components.
A group valued function on a graph is called balanced if the product of its values along any cycle is equal to the identity element of the group. We compute the number of balanced functions from the set of edges and vertices of a directed graph to a finite group considering two cases: when we are allowed to walk against the direction of an edge and when we are not allowed to walk against the edge direction. In the first case it appears that the number of balanced functions on edges and vertices depends on whether or not the graph is bipartite, while in the second case this number depends on the number of strong connected components of the graph.
Journal: Information Processing Letters - Volume 116, Issue 7, July 2016, Pages 484–488