Relaxed graceful labellings of trees (Q5954317): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 02:09, 30 January 2024
scientific article; zbMATH DE number 1699542
Language | Label | Description | Also known as |
---|---|---|---|
English | Relaxed graceful labellings of trees |
scientific article; zbMATH DE number 1699542 |
Statements
Relaxed graceful labellings of trees (English)
0 references
7 February 2002
0 references
Summary: A graph \(G\) on \(m\) edges is considered graceful if there is a labelling \(f\) of the vertices of \(G\) with distinct integers in the set \(\{0,1,\dots,m\}\) such that the induced edge labelling \(g\) defined by \(g(uv)=|f(u)-f(v)|\) is a bijection to \(\{1,\dots,m\}\). We here consider some relaxations of these conditions as applied to tree labellings: 1. Edge-relaxed graceful labellings, in which repeated edge labels are allowed, 2. Range-relaxed graceful labellings, in which the upper bound \(m'\) is allowed to go higher than the number of edges, and 3. Vertex-relaxed graceful labellings, in which repeated vertex labels are allowed. The first of these had been looked at by \textit{A. Rosa} and \textit{J. Širáň} [J. Graph. Theory 19, No. 2, 201-215 (1995; Zbl 0818.05054)]. Here some linear bounds in the relevant metrics are given for range-relaxed and vertex-relaxed graceful labellings.
0 references
tree labellings
0 references
graceful labellings
0 references