On the strength and independence number of powers of paths and cycles

Document Type : Original paper


1 Department of Sport and Physical Education, Faculty of Physical Education, Kokushikan University

2 The University of Newcastle

3 Department of Electronics and Informatics, School of Science and Engineering, Kokushikan University


A numbering $f$ of a graph $G$ of order $n$ is a labeling that assigns distinct elements of the set $\left\{1,2, \ldots, n \right\}$ to the vertices of $G$. The strength $\mathrm{str}\left(G\right) $ of $G$ is defined by $\mathrm{str}\left( G\right) =\min \left\{ \mathrm{str}_{f}\left( G\right)\left\vert f\text{ is a numbering of }G\right. \right\}$, where $\mathrm{str}_{f}\left( G\right) =\max \left\{ f\left( u\right)+f\left( v\right) \left\vert uv\in E\left( G\right) \right. \right\} $.
Using the concept of independence number of a graph, we determine formulas for the strength of powers of paths and cycles. To achieve the latter result, we establish a sharp upper bound for the strength of a graph in terms of its order and independence number and a formula for the independence number of powers of cycles.


Main Subjects

[1] B.D. Acharya and S.M. Hegde, Strongly indexable graphs, Discrete Math. 93 (1991), no. 2-3, 123–129.
[2] G. Chartrand and L. Lesniak, Graphs & Digraphs, 3th edition, CRC Press, 1996.
[3] P.Z. Chinn, J. Chvátalová, A.K. Dewdney, and N.E. Gibbs, The bandwidth problem for graphs and matrices—a survey, J. Graph Theory 6 (1982), no. 3, 223–254.
[4] F.R.K. Chung, Labelings of graphs, Selected Topics in Graph Theory (L.W. Beineke and R.J. Wilson, eds.), vol. 3, 1988, pp. 151–168.
[5] V. Chvátal, A remark on a problem of Harary, Czechoslovak Math. J. 20 (1970), no. 1, 109–111.
[6] H. Enomoto, A.S. Llado, T. Nakamigawa, and G. Ringel, Super edge-magic graphs, SUT J. Math. 34 (1998), no. 2, 105–109.
[7] R.M. Figueroa-Centeno, R. Ichishima, and F.A. Muntaner-Batle, The place of super edge-magic labelings among other classes of labelings, Discrete Math. 231 (2001), no. 1-3, 153–168.
[8] J.A. Gallian, Graph labeling, Electron. J. Comb. 18 (2023), #DS6.
[9] Z.B. Gao, G.C. Lau, and W.C. Shiu, Graphs with minimal strength, Symmetry 13 (2021), no. 3, Article ID: 513
[10] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Math. Sci., Freeman, San Francisco, 1979.
[11] F. Harary, Problem 16, Theory of Graphs and its Applications (M. Ficdler, ed.), Czech. Acad. Sci., Prague, 1967.
[12] L.H. Harper, Optimal assignments of numbers to vertices, SIAM J. Appl. Math. 12 (1964), no. 1, 131–135.
[13] R. Ichishima, F.A. Muntaner-Batle, and A. Oshima, Bounds for the strength of graphs, Australas. J. Combin. 72 (2018), no. 3, 492–508.
[14] R. Ichishima, F.A. Muntaner-Batle, and A. Oshima, On the strength of some trees, AKCE Int. J. Graphs Comb. 17 (2020),
no. 1, 486–494.
[15] R. Ichishima, F.A. Muntaner-Batle, and A. Oshima, Minimum degree conditions for the strength and bandwidth of graphs, Discrete Appl. Math. 320 (2022), 191–198.
[16] R. Ichishima, F.A. Muntaner-Batle, and A. Oshima, A result on the strength of graphs by factorizations of complete graphs, Discrete Math. Lett. 8 (2022), 78–82.
[17] R. Ichishima, F.A. Muntaner-Batle, A. Oshima, and Y. Takahashi, The strength of graphs and related invariants, Memoirs Kokushikan Univ. Inf. Sci. 41 (2020), 1–8.
[18] R. Ichishima, F.A. Muntaner-Batle, and Y. Takahashi, On the strength and independence number of graphs, Contrib. Math. 6 (2022), 25–29.
[19] R. Ichishima, A. Oshima, and Y. Takahashi, The edge-strength of graphs, Discrete Math. Lett. 3 (2020), 44–49.
[20] R. Ichishima, A. Oshima, and Y. Takahashi, Some new results on the edge-strength and strength of graphs, Discrete
Math. Lett. 12 (2023), 22–25.
[21] Y.L. Lai and K. Williams, A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs, J. Graph Theory 31 (1999), no. 2, 75–94.
[22] D.B. West, Introduction to Graph Theory, Prentice Hall, New Jersey, 1996.