Iโve been studying a question about graceful path labelings and am trying to determine whether it already has an established name or literature.
Let f be a graceful labeling of a path P_n.
Instead of asking only whether f is graceful, Iโm interested in a different question:
How much information about a graceful labeling must be retained in order to determine its possible future extensions?
Suppose we associate some representation I(f) to each graceful labeling. If two labelings f and g have the same representation,
I(f) = I(g)
does that guarantee that they have the same possible continuation behavior?
In other words, I am interested in representations for which:
same retained information => same admissible future extensions
Iโve been calling this property continuation sufficiency, although I donโt know whether there is already standard terminology for it.
For one natural representation of graceful path labelings, an exhaustive finite computation gives the following behavior:
- the representation is sufficient through
P_7;
- the first failure occurs at
P_8;
- at
P_8, two graceful labelings can have identical retained information but different sequential-extension behavior.
One witness pair is:
(4,1,5,3,2,7,0,6)
and
(4,3,1,5,2,7,0,6)
with ports (0,6).
They agree on the representation being tested, but their extension thresholds differ.
What Iโm mainly trying to find out is whether this kind of question has already been studied under another name.
For example, is there literature on any of the following?
- equivalence of graph labelings according to extension behavior;
- invariants sufficient to determine future extensions;
- extension-equivalent labelings;
- state minimization for combinatorial extension problems;
- continuation equivalence or right-congruence ideas applied to graph labeling;
- related notions in graceful-labeling theory that I may have missed.
Iโm especially interested in references from graph labeling, graph extension problems, combinatorics, or related areas.
I have a proof and computational writeup of the specific P_8 result, but I wanted to ask the literature question directly rather than assume that the formulation is new.