The subdivision graph of a graceful tree is a graceful tree

DOI10.1016/S0012-365X(97)00069-1MaRDI QIDQ1381864zbMATH OpenOpenAlexFDO

Authors Marco Burzio, Giorgio Ferrarese

Publication date 10 December 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(97)00069-1

zbMATH Keywords

graceful treesubdivision graph

Mathematics Subject Classification ID

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

Review text

A graph \(G= (V,E)\) is graceful, if there is a numbering \(f\) of the vertices from \(1\) to \(| V|\), such that all values \(| f(v)- f(w)|\) are distinct for all edges \(\{v,w\}\in E\). The subdivision graph of a graph is obtained by adding a vertex on the middle of each edge. It is shown that the subdivision graph of a graceful tree is also graceful. The same result holds if exactly \(n\) vertices are inserted on each edge of a graceful tree. The result does not generalize to arbitrary graphs.

Recommendations

• Graceful and cordial labeling of subdivision of graphs
• A substitution theorem for graceful trees and its applications
• scientific article; zbMATH DE number 1925192
• Graceful labelings of super-subdivision of \(F\)-tree and \(P^+_n\)-tree
• Every tree is a subtree of graceful tree, graceful graph and alpha-labeled graph.

Cites work

• A survey: Recent results, conjectures, and open problems in labeling graphs
• scientific article; zbMATH DE number 4174979 (Why is no real title available?)
• scientific article; zbMATH DE number 3698968 (Why is no real title available?)
• scientific article; zbMATH DE number 3308125 (Why is no real title available?)
• The factorial representation of balanced labelled graphs
• Two theorems on graceful trees

Cited in

(16)

• A substitution theorem for graceful trees and its applications
• Products of graceful bipartite graphs
• Improved bounds for relaxed graceful trees
• Strong labelings of linear forests
• Any tree with m edges can be embedded in a graceful tree with less than 4m edges and in a graceful planar graph
• Construction of an \(\alpha\)-labeled tree from a given set of \(\alpha\)-labeled trees
• Generating graceful trees from caterpillars by recursive attachment
• Graceful Labeling of Balanced Stars of Paths
• Graceful labelings of super-subdivision of \(F\)-tree and \(P^+_n\)-tree
• scientific article; zbMATH DE number 7595319 (Why is no real title available?)
• Binomial trees are graceful
• Graceful pairings
• Odd harmonious and strongly odd harmonious graphs
• scientific article; zbMATH DE number 7742560 (Why is no real title available?)
• Maker-breaker domination game on trees when Staller wins
• Embedding an arbitrary tree in a graceful tree

This page was built for publication: The subdivision graph of a graceful tree is a graceful tree

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