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

DOI10.1016/J.DISC.2022.112806MaRDI QIDQ2113361zbMATH OpenOpenAlexFDO

Authors Rupert Li

Publication date 14 March 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

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)