- Title
- Characterisation of graphs with exclusive sum labelling
- Creator
- Miller, Mirka; Ryan, Joe; Ryjáček, Zdeněk
- Relation
- Australasian Journal of Combinatorics Vol. 69, Issue Part 3, p. 334-348
- Relation
- https://ajc.maths.uq.edu.au/?page=get_volumes&volume=69
- Publisher
- Centre for Discrete Mathematics & Computing
- Resource Type
- journal article
- Date
- 2017
- Description
- A sum graph G is a graph with an injective mapping of the vertex set of G onto a set of positive integers S in such a way that two vertices of G are adjacent if and only if the sum of their labels is an element of S. In an exclusive sum graph the integers of S that are the sum of two other integers of S form a set of integers that label a collection of isolated vertices associated with the graph G. A graph bears a k-exclusive sum labelling (abbreviated k-ESL), if the set of isolated vertices is of cardinality k, an optimal exclusive sum labelling, if k is as small as possible, and Δ-optimal if k equals the maximum degree of the graph. In this paper, observing that the property of having a k-ESL is hereditary, we provide a characterisation of graphs that have a k-exclusive sum labelling, for any k ≥ 1, in terms of describing a universal graph for the property.
- Subject
- sum graph; graphs; graph labelling; exclusive sum labelling
- Identifier
- http://hdl.handle.net/1959.13/1388447
- Identifier
- uon:32758
- Identifier
- ISSN:1034-4942
- Language
- eng
- Reviewed
- Hits: 1111
- Visitors: 1241
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|