The adjacency dimension bound for the join of a graph with a universal vertex

About 11 years old · traced to

Let HH be a graph of order n≥2n\ge 2, let K1+HK_1+H denote the graph obtained by adding a universal vertex to HH, and let C(K1+H)\mathcal{C}(K_1+H) be its adjacency threshold. For k∈{1,…,C(K1+H)}k\in\{1,\ldots,\mathcal{C}(K_1+H)\}, write adim⁡k(G)\operatorname{adim}_k(G) for the kk-adjacency dimension of a graph GG. Adjacency dimension bound.

adim⁡k(K1+H)≤adim⁡k(H)+k.\operatorname{adim}_k(K_1+H)\le\operatorname{adim}_k(H)+k.

The bound gives an upper estimate for the adjacency dimension of a graph formed by adjoining a universal vertex, and the surrounding example shows that it can be tight. The supplied text does not state whether the bound has been proved or remains open.

References

Primary source

A. Estrada-Moreno, Y. Ramirez-Cruz and J. A. Rodriguez-Velazquez, “On the adjacency dimension of graphs”, arXiv:1501.04647 (2015).

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.