The recurrence

f(i, i) = 0

f(i, j) = g(f(i, j - 1), f(i + 1, j)) + cost(i, j)

for any function g and cost (minimum and (i + j), respectively, for example) generates a family of graphs that (informally) look like a complete binary tree that cuts into itself.

Has this family of graphs been named? Does it have properties that could be useful in competitive programming?

Notable things:

• The graphs have no Euler path nor circuit for depths larger than 2.

• Maximal independent set is taking the last depth, third last depth, etc.

• Seems like Hamiltonian paths don't exist for larger depths.

• Hamiltonian circuits definitely don't exist, since there are vertices with degree 1.

• Odd cycles don't seem to exist, which means the graphs are bipartite

Screenshot courtesy of VisuAlgo