Additive edge labelings

DOI10.1016/J.DAM.2009.10.006zbMATH Open1225.05211arXiv0904.2600OpenAlexW2081950086MaRDI QIDQ968162FDOQ968162

Alicia Dickenstein, Enrique A. Tobis

Publication date: 5 May 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Let G=(V,E) be a graph and d a positive integer. We study the following problem: for which labelings f_E: E o Z_d is there a labeling f_V:V o Z_d such that f_E(i,j) = f_V(i) + f_V(j) (mod d), for every edge (i,j) in E? We also explore the connections of the equivalent multiplicative version to toric ideals. We derive a polynomial algorithm to answer these questions and to obtain all possible solutions.

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

Recommendations

• Edge sum labelings of a graph
• On addition of edges of graphs
• Edge-sum distinguishing labeling
• On edge addition of altered graphs
• scientific article; zbMATH DE number 1556747
• Edge colouring by total labellings
• Edge pair sum labeling of some classes of graphs
• scientific article; zbMATH DE number 7103379
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 6605161

zbMATH Keywords

kerneltoric idealcyclesincidence matrixgraph labeling

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• A dynamic survey of graph labeling
• On Additive Bases and Harmonious Graphs
• Parallel concepts in graph theory
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Rees algebras of edge ideals
• On the minors of an incidence matrix and Smith normal form
• On felicitous graphs
• Algorithmic and Complexity Results for Decompositions of Biological Networks into Monotone Subsystems

This page was built for publication: Additive edge labelings

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