Diameter extremality conjecture for Bell-type io-decomposable Riordan graphs

About 7 years old · traced to

Let GnG_n be an io-decomposable Riordan graph of the Bell type. The Pascal and Catalan graphs are

PGn=Gn(1/(1−z),z/(1−z)),CGn=Gn(C(z),zC(z)).PG_n=G_n(1/(1-z),z/(1-z)),\qquad CG_n=G_n(C(z),zC(z)).

Here diam(G){\rm diam}(G) denotes the graph diameter. Diameter extremality conjecture. For n≥4n\geq4,

2=diam(PGn)≤diam(Gn)≤diam(CGn).2={\rm diam}(PG_n)\leq {\rm diam}(G_n)\leq {\rm diam}(CG_n).

Moreover, PGnPG_n is the only graph in the class of io-decomposable graphs of the Bell type whose diameter is 22 for all n≥4n\geq4. This conjecture identifies the Pascal and Catalan graphs as the lower and upper diameter extremizers in this class; the supplied text does not state whether it has been resolved.

References

Primary source

Ji-Hwan Jung, “Diameter of io-decomposable Riordan graphs of the Bell type”, arXiv:1901.11156 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.