Balanced group-labeled graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Manas Joglekar ^{manas@cse.iitb.ac.in} ; Nisarg Shah ^{nisarg@cse.iitb.ac.in} ; Ajit A. Diwan ; ^{aad@cse.iitb.ac.in}
• 关键词：Group-labeled graphs ; Signed graphs ; Marked graphs ; Balanced labellings ; Fundamental cycles ; Vertex switching ; Markable graphs
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：6 May, 2012
• 卷：312
• 期：9
• 页码：1542-1549
• 文件大小：220 K

摘要

A group-labeled graph is a graph whose vertices and edges have been assigned labels from some abelian group. The weight of a subgraph of a group-labeled graph is the sum of the labels of the vertices and edges in the subgraph. A group-labeled graph is said to be balanced if the weight of every cycle in the graph is zero. We give a characterization of balanced group-labeled graphs that generalizes the known characterizations of balanced signed graphs and consistent marked graphs. We count the number of distinct balanced labellings of a graph by a finite abelian group and show that this number depends only on the order of and not its structure. We show that all balanced labellings of a graph can be obtained from the all-zero labeling using simple operations. Finally, we give a new constructive characterization of consistent marked graphs and markable graphs, that is, graphs that have a consistent marking with at least one negative vertex.