آمار
| تعداد نشریات | 5 |
| تعداد شمارهها | 117 |
| تعداد مقالات | 1,383 |
| تعداد مشاهده مقاله | 1,395,076 |
| تعداد دریافت فایل اصل مقاله | 1,364,176 |
On the strength and independence number of powers of paths and cycles | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 1، دوره 10، شماره 4، اسفند 2025، صفحه 717-728 اصل مقاله (371.58 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2024.29087.1839 | ||
| نویسندگان | ||
| Rikio Ichishima* 1؛ Francisco Antonio Muntaner-Batle2؛ Yukio Takahashi3 | ||
| 1Department of Sport and Physical Education, Faculty of Physical Education, Kokushikan University, 7-3-1 Nagayama, Tama-shi, Tokyo 206-8515, Japan | ||
| 2Graph Theory and Applications Research Group, School of Electrical Engineering and Computer Science, Faculty of Engineering and Built Environment, The University of Newcastle, NSW 2308, Australia | ||
| 3Department of Science and Engineering, Faculty of Electronics and Informatics, Kokushikan University, 4-28-1 Setagaya, Setagaya-ku, Tokyo 154-8515, Japan | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| strength؛ independence number؛ $k$th power of a graph؛ graph labeling؛ combinatorial optimization | ||
| مراجع | ||
|
[1] B.D. Acharya and S.M. Hegde, Strongly indexable graphs, Discrete Math. 93 (1991), no. 2-3, 123–129. https://doi.org/10.1016/0012-365X(91)90248-Z
[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. https://doi.org/10.1002/jgt.3190060302
[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. http://dx.doi.org/10.21136/CMJ.1970.100949
[6] H. Enomoto, A.S. Llado, T. Nakamigawa, and G. Ringel, Super edge-magic graphs, SUT J. Math. 34 (1998), no. 2, 105–109. http://dx.doi.org/10.55937/sut/991985322
[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. https://doi.org/10.1016/S0012-365X(00)00314-9
[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 https://doi.org/10.3390/sym13030513
[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. https://doi.org/10.1137/0112012
[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. https://doi.org/10.1016/j.akcej.2019.06.002
[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. https://doi.org/10.1016/j.dam.2022.05.005
[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. https://doi.org/10.47443/dml.2021.0096
[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. https://doi.org/10.47443/cm.2022.036
[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. https://doi.org/10.47443/dml.2022.208 [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. | ||
|
آمار تعداد مشاهده مقاله: 1,296 تعداد دریافت فایل اصل مقاله: 1,424 |
||