On optimum summable graphs
type: Item
instance of: scholarly article
title: On optimum summable graphs
zbMATH Open document ID: 1103.05073
author: Mirka Miller
author: W. F. Smyth
author: Yan Wang
author: K. M. Koh
published in: AKCE International Journal of Graphs and Combinatorics
publication date: 2006-10-12T00:00:00Z
review text: For a graph \(G\) with \(\delta(G)>1\) and a positive integer \(k\), let \(G_k=G\cup\overline{K_k}\). The graph \(G_k\) is a sum graph if there exists an injective labeling \(L:V(G_k)\rightarrow N\) such that for any two distinct vertices \(u, v\), \(uv\in E(G_k)\) if and only if there exists \(w\in V(G_k)\) with \(L(w)=L(u)+L(v)\). The sum number \(\sigma(G)\) of a connected graph \(G\) is then defined as the smallest \(k\) for which \(G_k\) is a sum graph. A nontrivial connected graph \(G\) is called a \(k\)-optimum summable graph, where \(k\geq 1\), if \(\sigma(G)=\delta(G)=k\). In the present paper, it is shown that if \(G\) is a \(k\)-optimum summable graph of order \(n\), \(k\geq 3\), then \(n\geq 2k\) and the complete bipartite graph \(K_{n,n-k}\) is not a spanning subgraph of \(G\). There is also shown for some classes of graphs that they are \(k\)-optimum summable (1-optimum summable are certain tadpoles, and examples of 2-optimum and \(k\)-optimum, \(k\geq 3\), summable graphs are given too).
reviewed by: Vladimír Lacko
Mathematics Subject Classification ID: 05C78
zbMATH DE Number: 5063016
zbMATH Keywords: sum graph
zbMATH Keywords: sum number
zbMATH Keywords: sum labeling
zbMATH Keywords: minimum degree
MaRDI profile type: MaRDI publication profile
Recommended article: Optimum sum labeling of finite union of sum graphs
Recommended article: A Theorem on Sum Graphs
Recommended article: Q3136991
Recommended article: Some results on sum graphs
Recommended article: Exclusive sum labelings of trees
description: scientific article; zbMATH DE number 5063016