Characterisation of graphs with exclusive sum labelling

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

		Thumbnail	File	Description	Size	Format