شاخص بی نظمی تبدیلات گراف ها

نوع مقاله : مقاله مستقل

نویسنده
میثم طاهری دهکردی
دانشگاه جامع علمی کاربردی
10.22034/mmr.2026.131055.0
چکیده
با استفاده از تبدیلات گراف می توان تعداد زیادی گراف بزرگ از گراف های کوچکتر به وجود آورد. ضرب های گراف ها جزء مفاهیم بسیار بنیادی در نظریه ی گراف به شمار می آیند. این ضرب ها شامل طیف بسیار گسترده ای هستند که هر کدام موجب تولید گراف های جدید با خواص و کاربردهای متفاوت می شوند. همچنین، برای گراف دلخواه 𝐺 با 𝑛 رأس و 𝑚 یال، ساختار 𝑅𝑘(𝐺) گرافی شامل 𝑘 کپی از گراف 𝐺 با 𝑘𝑛 رأس و 𝑘2𝑚 یال ایجاد می کند. شاخص بی نظمی برای گراف همبند 𝐺 به صورت 𝐼𝑟𝑟(𝐺)=Σ|𝑑𝐺(𝑢)−𝑑𝐺(𝑣)|𝑢𝑣∈𝐸(𝐺) تعریف می شود. در این مقاله، ما شاخص بی نظمی را برای چند ضرب شامل ضرب لکزیکوگرافی، ضرب کرونا و ضرب مستقیم گراف ها به دست می آوریم و کران هایی برای بی نظمی این ضرب ها تعیین می کنیم. علاوه بر آن، بی نظمی ساختار 𝑅𝑘(𝐺) را برای گراف دلخواه 𝐺 به دست می آوریم.
کلیدواژه‌ها
ضرب گراف ها
بی نظمی
ساختار 𝑅𝑘(𝐺)
موضوعات

عنوان مقاله English

Irregularity Index of Graph Transformations

نویسنده English

Meysam Taheri-Dehkordi
University of Applied Science and Technology
چکیده English

Using graph transformations, a large number of graphs can be generated from smaller graphs. Graph products are considered among the fundamental concepts in graph theory. These products encompass a wide range of types, each of which produces new graphs with different properties and applications. Moreover, for an arbitrary graph 𝐺 with 𝑛 vertices and 𝑚 edges, the structure 𝑅𝑘(𝐺) produces a graph consisting of 𝑘 copies of 𝐺 with 𝑘𝑛 vertices and 𝑘2𝑚 m edges. The irregularity index of a connected graph 𝐺 is defined as 𝐼𝑟𝑟(𝐺)=Σ|𝑑𝐺(𝑢)−𝑑𝐺(𝑣)|𝑢𝑣∈𝐸(𝐺). In this paper, we compute the irregularity index for several graph products, including the lexicographic product, the corona product, and the direct product of graphs, and we establish bounds for the irregularity of these products. Additionally, we determine the irregularity of the structure 𝑅𝑘(𝐺) for an arbitrary graph 𝐺.

کلیدواژه‌ها English

Graph products
Irregularity
Structure 𝑅𝑘(𝐺)
[1] Abd Aziz, N. A., 2026. A note on graphs with integer Sombor index. Commun. Comb. Optim., 11, pp. 205–209.
[2] Abdo, H., Brandt, S. and Dimitrov, D., 2014. The total irregularity of a graph. Discrete Math. Theor. Comput. Sci., 16, pp. 201–206.
[3] Abdo, H., Dimitrov, D. and Gao, W., 2017. On the irregularity of some molecular structures. Canad. J. Chem., 95, pp. 174–183.
[4] Abdo, H. and Dimitrov, D., The irregularity of graphs under graph operations, Discuss. Math. Graph Theory 34 (2014) 263–278.
[5] Abdo, H. and Dimitrov, D., 2014. The total irregularity of graphs under graph operations. Miskolc Math. Notes., 15, pp. 3–17.
[6] Albertson, M. O., 1997, The irregularity of a graph. Ars Combin, 46, pp. 219–225.
[7] Barriére, L., Comellas, F., Dalfó, C. and Fiol, M. A., 2009. The hierarchical product of graphs. Discrete Appl. Math., 157.
[8] Bondy, A., Murty, R., et al. 1976. Graph theory with applications, volume 290. Macmillan London.
[9] Dimitrov, D. and Réti, T., 2014. Graphs with equal irregularity indices. Acta Polytechn. Hung., 11 (4), pp. 41–57.
[10] Fath–Tabar, G. H., 2011. Old and new Zagreb indices of graphs. MATCH Commun. Math. Comput. Chem., 65, pp. 79–84.
[11] Fath-tabar, G. H., Gutman, I. and Nasiri, R., 2013. Extremely irregular trees. Bull. Acad. Serbe Sci. Arts., 38, pp. 1–8.
[12] Forcan, J. and Qi, J., 2024. Maker-Breaker domination number for Cartesian products of path graphs P2 and Pn, Discrete Math. Theor. Comput. Sci., 25 (2).
[13] Frucht, R. and Harary, F., 1970. On the corona of two graphs. Aequationes mathematicae, 4 (3), pp. 322-325.
[14] Godsil, C., and Royle, G. F., 2001. Algebraic Graph Theory. Springer.
[15] Gutman, I., 2016. Irregularity of molecular graphs. Kragujevac Journal of Science, 38, pp. 71-81.
[16] Hammack, R., Imrich, W. and Klavžar, S., 2011. HandBook of Product Graphs, CRC Press, 2nd edition.
[17] Hammack, R., Imrich, W. and Klavžar, S., 2011. Handbook of graph products. Discrete Math. Appl.
[18] Hansen, P. and Mélot, H., 2005. Variable neighborhood search for extremal graphs. 9. Bounding the irregularity of a graph. Discr. Math. Theor. Comput. Sci., 69, pp. 253–264.
[19] Harary, F., 1969. Graph Theory. Addison-Wesley, Reading, MA.
[20] Henning, M. A. and Rautenbach, D., 2007. On the irregularity of bipartite graph. Discrete Math., 307, pp. 1467–1472.
[21] Imrich, W. and Klavžar, S., 2000, Product Graphs, Structure and Recognition. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley.
[22] Imrich, W., Klavžar, S. and Rall, D. F., 2008. Topics in Graph Theory: Graphs and Their Cartesian Product. A.K Press.
[23] Johnson, M. A., 1993. Structure-activity maps for visualizing the graph variables arising in drug design. J. Biopharm. Stat., 3, pp. 203–236.
[24] Khuller, S., Raghavachari, B. and Rosenfeld, A., 1996. Landmarks in graphs. Discret. Appl. Math., 70, pp. 217–229.
[25] Réti, T. and Dimitrov, D., 2013. On irregularities of bidegreed graphs, Acta Polytechn. Hung., 10 (7), pp. 117–134.
[26] Spacapan, S., 2008. Connectivity of Cartesian products of graphs. Appl. Math. Lett., 21, pp. 682-685.
[27] Stong, R., 1991. Hamilton decompositions of Cartesian products of graphs. Discrete Math., 90, pp. 169–190.
[28] Tardif, C., 1998. Graph products and the chromatic difference sequence of vertex-transitive graphs. Discrete Math., 185, pp. 193–200.
[29] Taylor, D. T., 2009. Perfect r-codes in lexicographic products of graphs. Ars Combin, 93, pp. 215–223.
[30] Weichsel, P. M., 1962. THE KRONECKER PRODUCT OF GRAPHS.
[31] Zhu, Y., You, L. and Yang, J., 2016. The minimal total irregularity of some classes of graphs. Filomat, 30, pp. 1203–1211.