Geodesic Convexity and Hop Domination in Graph Powers: The Path Family

Karrar Khudhair Obayes, Ghadeer Khudhair Obayes

Abstract


Graph powers alter distances in a predictable manner, making them a useful setting for domination parameters defined through distance. We consider convex hop domination in powers of paths. The usual distance identity for graph powers is employed only as a metric reduction: distance two in the powered graph corresponds to the condition k < dG(u,v) ≤ 2k in the original graph. Our contribution is the complete exact classification for path powers with k ≥ 2, supported by matching upper and lower bounds in the complete, diameter-two transition, and stable ranges. The case k = 1 is not new; it is the path result of Hassan, Canoy, and Saromines (2023) and is retained only to present the classification in a unified form. For higher powers, the argument relies on k-step geodesic progressions, endpoint-span estimates, and common-neighbor structure in the transition range. We also check the formulas exhaustively for 102 pairs with 1 ≤ k ≤ 6 and 2 ≤ n ≤ 18. The verification procedure, complete tested values, and executable Python code are supplied to make this computational check reproducible.


Keywords


convex hop domination; graph powers; path graphs; distance transfer; geodesic convexity; domination number; metric graph theory

Full Text:

PDF - En

References


[1] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs. New York, NY, USA: Marcel Dekker, 1998.

[2] S. K. Ayyaswamy, B. Krishnakumari, C. Natarajan, and Y. B. Venkatakrishnan, "Bounds on the hop domination number of a tree," Proc. Math. Sci., vol. 125, no. 4, pp. 449–455, 2015, doi: 10.1007/s12044-015-0251-6.

[3] M. A. Henning and N. Jafari Rad, "On 2-step and hop dominating sets in graphs," Graphs Combin., vol. 33, no. 4, pp. 913–927, 2017, doi: 10.1007/s00373-017-1789-0.

[4] F. Buckley and F. Harary, Distance in Graphs. Redwood City, CA, USA: Addison-Wesley, 1990.

[5] F. Harary and J. Nieminen, "Convexity in graphs," J. Differential Geom., vol. 16, pp. 185–190, 1981, doi: 10.4310/jdg/1214436096.

[6] I. M. Pelayo, Geodesic Convexity in Graphs. New York, NY, USA: Springer, 2013, doi: 10.1007/978-1-4614-8699-2.

[7] J. A. Hassan, S. R. Canoy, Jr., and C. J. Saromines, "Convex hop domination in graphs," Eur. J. Pure Appl. Math., vol. 16, no. 1, pp. 319–335, 2023, doi: 10.29020/nybg.ejpam.v16i1.4656.

[8] S. R. Canoy, Jr. and J. A. Hassan, "Weakly convex hop dominating sets in graphs," Eur. J. Pure Appl. Math., vol. 16, no. 2, pp. 1196–1211, 2023, doi: 10.29020/nybg.ejpam.v16i2.4761.

[9] A.-A. Y. Isahac, J. A. Hassan, L. S. Laja, and H. B. Copel, "Outer-convex hop domination in graphs under some binary operations," Eur. J. Pure Appl. Math., vol. 16, no. 4, pp. 2035–2048, 2023, doi: 10.29020/nybg.ejpam.v16i4.4862.

[10] A. Etawi, M. Ghanem, and H. Al-Ezeh, "Acyclic and star coloring of powers of paths and cycles," Eur. J. Pure Appl. Math., vol. 15, no. 4, pp. 1822–1835, 2022, doi: 10.29020/nybg.ejpam.v15i4.4574.

[11] M. C. Lin, D. Rautenbach, F. J. Soulignac, and J. L. Szwarcfiter, "Powers of cycles, powers of paths, and distance graphs," Discrete Appl. Math., vol. 159, no. 7, pp. 621–627, 2011, doi: 10.1016/j.dam.2010.03.012.

[12] A. Brandstädt, V. D. Chepoi, and F. F. Dragan, "Perfect elimination orderings of chordal powers of graphs," Discrete Math., vol. 158, no. 1–3, pp. 273–278, 1996, doi: 10.1016/0012-365X(95)00081-7.

[13] A. Brandstädt and V. B. Le, "Simplicial powers of graphs," Theor. Comput. Sci., vol. 410, no. 52, pp. 5443–5454, 2009, doi: 10.1016/j.tcs.2009.04.010.

[14] L. Alcón and G. Hurlbert, "Pebbling in powers of paths," Discrete Math., vol. 346, no. 5, Art. no. 113315, 2023, doi: 10.1016/j.disc.2023.113315.

[15] E. K. Hng, "Minimum degrees for powers of paths and cycles," SIAM J. Discrete Math., vol. 36, no. 4, pp. 2667–2736, 2022, doi: 10.1137/20M1359183.




DOI: https://doi.org/10.18860/jrmm.v6i1.45881

Refbacks

  • There are currently no refbacks.