A family of sparse graphs of large sum number

DOI10.1016/0012-365X(93)E0196-BMaRDI QIDQ1894767zbMATH OpenOpenAlexFDO

Authors Nora Hartsfield, W. F. Smyth

Publication date 27 November 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(93)e0196-b

zbMATH Keywords

labelsparse graphssum graphsum numberwheelwheel graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Review text

Given an (undirected) graph \(G= (V, E)\), and an integer \(r\geq 0\), \(G_r= (V_r, E)\) is obtained by adding \(r\) isolated vertices to \(G\). \(G_r\) is said to be a sum graph, if one can label the vertices \(v\in V_r\) with distinct positive integers \(L(v)\), such that for every pair of distinct vertices \(v,w\in V_r\), \((v,w)\in E\), if and only if there exists a vertex \(x\in V_r\) with \(L(x)= L(v)+ L(w)\). The sum number of a graph \(G\) is the smallest \(r\), such that \(G_r\) is a sum graph. In this paper, the authors consider the sum number of wheel graphs: graphs obtained by taking a circuit, and adding one vertex adjacent to each vertex in the circuit. They show, that for sufficiently large \(n\), a wheel with \(n+1\) vertices has sum number \(n/2+3\), if \(n\) is even, and sum number between \(n\) and \(n+2\), if \(n\) is odd. This is the first example of a class for which it is known that the sum number is proportional to the size of the graphs.

Recommendations

• scientific article; zbMATH DE number 1279038
• scientific article; zbMATH DE number 2188426
• The sum numbers and the integral sum numbers of the graph \(K_{n+1}\setminus E(K_{1,r})\)
• Some results on mod (integral) sum graphs.
• The spum and sum-diameter of graphs: labelings of sum graphs

Cited in

(13)

• Connected graphs which are not mod sum graphs
• Integral sum graphs from identification
• The spum and sum-diameter of graphs: labelings of sum graphs
• The space complexity of sum labelling
• The (mod, integral) sum numbers of fans and \(K_{n,n}-E(nK_{2})\)
• On the range of size of sum graphs \& integral sum graphs of a given order
• A sum labelling for the generalised friendship graph
• On the mod sum number of \(H _{m,n }\)
• scientific article; zbMATH DE number 1279038 (Why is no real title available?)
• Sum number of fans
• scientific article; zbMATH DE number 2188426 (Why is no real title available?)
• The space complexity of sum labelling
• Some results on exclusive sum graphs

This page was built for publication: A family of sparse graphs of large sum number

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