A Note on the Sparing Number of Graphs

MaRDI QIDQ2929780arXivFDO

Authors N. K. Sudev, K. A. Germina

Publication date 14 November 2014

Published in arXiv

Full work available at URL https://arxiv.org/abs/1402.4871, http://www.pphmj.com/abstract/8559.htm

zbMATH Keywords

mono-indexed elements of a graphsparing number of a graphweak integer additive set-indexers

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

arXiv classification

math.CO

Abstract: An integer additive set-indexer is defined as an injective function $f:V(G)ightarrow{2}^{mathbb{N}_0}$ such that the induced function $g_f:E(G)ightarrow{2}^{mathbb{N}_0}$ defined by $g_f(uv)=f(u)+f(v)$ is also injective. An IASI $f$ is said to be a weak IASI if $|g_f(uv)|=max(|f(u)|,|f(v)|)$ for all $u,vinV(G)$. A graph which admits a weak IASI may be called a weak IASI graph. The set-indexing number of an element of a graph $G$, a vertex or an edge, is the cardinality of its set-labels. The sparing number of a graph $G$ is the minimum number of edges with singleton set-labels, required for a graph $G$ to admit a weak IASI. In this paper, we study the sparing number of certain graphs and the relation of sparing number with some other parameters like matching number, chromatic number, covering number, independence number etc.

Recommendations

• A note on the sparing number of the sieve graphs of certain graphs
• The sparing number of certain graph powers
• A note on the sparing number of generalised Petersen graphs
• A note on \([k,l]\)-sparse graphs
• On the number of sparse connected graphs
• scientific article; zbMATH DE number 3235080
• The representation number of some sparse graphs
• scientific article; zbMATH DE number 7268059
• On Ramsey Numbers of Sparse Graphs
• A note on total graphs

Cited in

(6)

• The sparing number of certain graph powers
• Weak integer additive set-labeled graphs: a creative review
• On the number of sparse connected graphs
• scientific article; zbMATH DE number 7268059 (Why is no real title available?)
• A Combinatorial Classic — Sparse Graphs with High Chromatic Number
• The representation number of some sparse graphs

This page was built for publication: A Note on the Sparing Number of Graphs

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