On Integral Sum Graphs |
| |
| Institution: | 1. Department of Applied Mathematics, National Sun Yat-sen University, Kaohsiung, 80424, Taiwan;2. National Center for Theoretical Sciences, Taiwan;3. Department of Mathematics, Zhejiang Normal University, Jinhua, China;1. University of California, Berkeley, Department of Mathematics, United States of America;2. Georgia Institute of Technology, School of Mathematics, United States of America;3. Massachusetts Institute of Technology, Department of Mathematics, United States of America;4. University of Michigan, Department of Mathematics, United States of America;1. Department of Mathematics, Evans Hall, UC Berkeley, Berkeley, CA 94720, United States;2. Institutionen för Matematik, KTH, SE-100 44 Stockholm, Sweden;1. School of Mathematical Sciences, Beihang University, Beijing 100191, China;2. School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia;1. Department of Computer Science, TU Dortmund, Germany;2. Physikalisch-Technische Bundesanstalt (PTB), Germany |
| |
| Abstract: | A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v) = f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K3 has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous relative results are also presented. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
