TY - JOUR
ID - 14720
TI - On the strength and independence number of powers of paths and cycles
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Ichishima, Rikio
AU - Muntaner Batle, Francisco Antonio
AU - Takahashi, Yukio
AD - Department of Sport and Physical Education, Faculty of Physical Education, Kokushikan University
AD - The University of Newcastle
AD - Department of Electronics and Informatics, School of Science and Engineering, Kokushikan University
Y1 - 2024
PY - 2024
VL -
IS -
SP -
EP -
KW - strength
KW - independence number
KW - $k$th power of a graph
KW - graph labeling
KW - combinatorial optimization
DO - 10.22049/cco.2024.29087.1839
N2 - 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.
UR - https://comb-opt.azaruniv.ac.ir/article_14720.html
L1 - https://comb-opt.azaruniv.ac.ir/article_14720_64c90a09bab45be62e744bcdc10e4680.pdf
ER -