Logo image
Back
A family of sparse graphs of large sum number
Journal article   Open access   Peer reviewed

A family of sparse graphs of large sum number

N. Hartsfield and W.F. Smyth
Discrete Mathematics, Vol.141(1-3), pp.163-171
1995
DOI: https://doi.org/10.1016/0012-365X(93)E0196-B
pdf
sumlarge.pdfDownloadView
Author’s Version Open Access
url
Link to Published Version *Subscription may be requiredView

Abstract

Given an integer r > 0, let Gr, = (Vr, E) denote a graph consisting of a simple finite undirected graph G = (V, E) of order n and size m together with r isolated vertices . Then | V | = n, |Vr| = n+r, and |E| = m. Let L:Vr → + denote a labelling of the vertices of Gr with distinct positive integers. Then Gr is said to be a sum graph if there exists a labelling L such that for every distinct vertex pair u and v of Vr, (u, v) ϵE if and only if there exists a vertex wϵVr whose label L(w) = L(u) + L(v). For a given graph G, the sum numberσ = σ(G) is defined to be the least value of r for which Gr is a sum graph. Gould and Rödl have shown that there exist infinite classes of graphs such that, over Gϵ, σ(G)ϵΘ(n2), but no such classes have been constructed. In fact, for all classes for which constructions have so far been found, σ(G)ϵo(m). In this paper we describe constructions which show that for wheels Wn of (sufficiently large) order n + 1 and size m = 2n, σ(Wn) = n/2 + 3 if n is even and n ⩽ σ (Wn) ⩽ n + 2 if n is odd. Hence for wheels σ (Wn) ϵΘ(m).

Details

Metrics

118 File views/ downloads
66 Record Views
21 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types
Domestic collaboration
International collaboration
Citation topics
4 Electrical Engineering, Electronics & Computer Science
4.293 Communication Protocols
4.293.1569 Graph Labeling
Web Of Science research areas
Mathematics
ESI research areas
Mathematics
Logo image