The spum and sum-diameter of graphs: labelings of sum graphs

DOI10.1016/J.DISC.2022.112806zbMATH Open1490.05242arXiv2107.09025OpenAlexW4206637309MaRDI QIDQ2113361FDOQ2113361

Authors: Rupert Li 

Publication date: 14 March 2022

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

Abstract: A sum graph is a finite simple graph whose vertex set is labeled with distinct positive integers such that two vertices are adjacent if and only if the sum of their labels is itself another label. The spum of a graph $G$ is the minimum difference between the largest and smallest labels in a sum graph consisting of $G$ and the minimum number of additional isolated vertices necessary so that a sum graph labeling exists. We investigate the spum of various families of graphs, namely cycles, paths, and matchings. We introduce the sum-diameter, a modification of the definition of spum that omits the requirement that the number of additional isolated vertices in the sum graph is minimal, which we believe is a more natural quantity to study. We then provide asymptotically tight general bounds on both sides for the sum-diameter, and study its behavior under numerous binary graph operations as well as vertex and edge operations. Finally, we generalize the sum-diameter to hypergraphs.

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

Recommendations

• Some results on the spum and the integral spum of graphs
• A characterization of the sum and integral sum labellings of some classes of graphs
• scientific article; zbMATH DE number 4148140
• A family of sparse graphs of large sum number
• Bounds on the number of isolates in sum graph labeling

zbMATH Keywords

hypergraphsgraph labelinggraph unionsum graphspumsum-diameter

Mathematics Subject Classification ID

Distance in graphs (05C12) Hypergraphs (05C65) Graph operations (line graphs, products, etc.) (05C76) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• A Theorem in Finite Projective Geometry and Some Applications to Number Theory
• A dynamic survey of graph labeling
• Theorems in the additive theory of numbers
• A complete annotated bibliography of work related to Sidon sequences
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• A characterization of the sum and integral sum labellings of some classes of graphs
• Harary's conjectures on integral sum graphs
• Sum graphs over all the integers
• Regular integral sum graphs
• Title not available (Why is that?)
• On integral sum graphs
• Chip-firing groups of iterated cones
• Critical groups of iterated cones
• Some results on the spum and the integral spum of graphs

Cited In (6)

• The minimax, maximin, and spread values for open neighborhood sums for 2-regular graphs
• Some results on the spum and the integral spum of graphs
• A family of sparse graphs of large sum number
• Sum-saturating labelings of trees
• The space complexity of sum labelling
• On the spum and sum-diameter of paths

This page was built for publication: The spum and sum-diameter of graphs: labelings of sum graphs

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