On k-graceful, locally finite graphs
type: Item
instance of: scholarly article
title: On k-graceful, locally finite graphs
zbMATH Open document ID: 0534.05057
DOI: 10.1016/0095-8956(83)90058-8
author: Peter Slater
published in: Journal of Combinatorial Theory. Series B
publication date: 1983-01-01T00:00:00Z
review text: A finite graph G with e edges is k-graceful, if there is a one-to-one mapping \(h: V(G)\to \{0,1,...,k+e-1\}\) such that the edge differences \(| h(u)-h(v)|\) (for u\(v\in E(G))\) are all distinct and range from k to \(k+e-1\). Some bipartite graphs may be k-graceful for all k, but if a k-graceful finite graph G contains an odd cycle of length \(2j+1\), then \(k\leq j\) (e-j-1). This inequality, proved by the author in an earlier paper, is strengthened for the situation where G contains several edge- disjoint odd cycles. A countably infinite graph G (with both V(G) and E(G) infinite) is bijectively k-graceful if there is a bijection \(h: V(G)\to \{0,1,2,...\}\) such that the mapping taking u\(v\in E(G)\) to \(| h(u)-h(v)|\) is also a bijection of E(G) onto \(\{k,k+1,k+2,...\}\). The second result asserts that a locally finite graph is bijectively k-graceful for all \(k\geq 1\).
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 3847445
zbMATH Keywords: numberings
zbMATH Keywords: graceful graphs
zbMATH Keywords: edge-disjoint odd cycles
zbMATH Keywords: bijectively k- graceful
reviewed by: Pavol Hell
MaRDI profile type: Publication
full work available at URL: 0095-8956(83)90058-8
OpenAlex ID: W2047601102
cites work: Q3863924
cites work: Q4198517
cites work: Q4179025
cites work: Q3916587
cites work: Q3663343
cites work: Q4744302
cites work: Q5589124
cites work: On k-sequential and other numbered graphs
cites work: Q3669464
cites work: Permutations of the positive integers with restrictions on the sequence of differences
description: scientific article; zbMATH DE number 3847445