Research article Special Issues

The differential on operator $ {{\mathcal{S}}({\Gamma})} $

  • Received: 16 March 2023 Revised: 17 April 2023 Accepted: 23 April 2023 Published: 05 May 2023
  • Consider a simple graph $ \Gamma = (V(\Gamma), E(\Gamma)) $ with $ n $ vertices and $ m $ edges. Let $ P $ be a subset of $ V(\Gamma) $ and $ B(P) $ the set of neighbors of $ P $ in $ V(\Gamma)\backslash P $. In the study of graphs, the concept of differential refers to a measure of how much the number of edges leaving a set of vertices exceeds the size of that set. Specifically, given a subset $ P $ of vertices, the differential of $ P $, denoted by $ \partial(P) $, is defined as $ |B(P)|-|P| $. The differential of $ \Gamma $, denoted by $ \partial(\Gamma) $, is then defined as the maximum differential over all possible subsets of $ V(\Gamma) $. Additionally, the subdivision operator $ {{\mathcal{S}}({\Gamma})} $ is defined as the graph obtained from $ \Gamma $ by inserting a new vertex on each edge of $ \Gamma $. In this paper, we present results for the differential of graphs on the subdivision operator $ {{\mathcal{S}}({\Gamma})} $ where some of these show exact values of $ \partial({{\mathcal{S}}({\Gamma})}) $ if $ \Gamma $ belongs to a classical family of graphs. We obtain bounds for $ \partial({{\mathcal{S}}({\Gamma})}) $ involving invariants of a graph such as order $ n $, size $ m $ and maximum degree $ \Delta $, and we study the realizability of the graph $ \Gamma $ for any value of $ \partial({{\mathcal{S}}({\Gamma})}) $ in the interval $ \left[n-2, \frac{n(n-1)}{2}-n+2\right] $. Moreover, we give a characterization for $ \partial({{\mathcal{S}}({\Gamma})}) $ using the notion of edge star packing.

    Citation: Jair Castro, Ludwin A. Basilio, Gerardo Reyna, Omar Rosario. The differential on operator $ {{\mathcal{S}}({\Gamma})} $[J]. Mathematical Biosciences and Engineering, 2023, 20(7): 11568-11584. doi: 10.3934/mbe.2023513

    Related Papers:

  • Consider a simple graph $ \Gamma = (V(\Gamma), E(\Gamma)) $ with $ n $ vertices and $ m $ edges. Let $ P $ be a subset of $ V(\Gamma) $ and $ B(P) $ the set of neighbors of $ P $ in $ V(\Gamma)\backslash P $. In the study of graphs, the concept of differential refers to a measure of how much the number of edges leaving a set of vertices exceeds the size of that set. Specifically, given a subset $ P $ of vertices, the differential of $ P $, denoted by $ \partial(P) $, is defined as $ |B(P)|-|P| $. The differential of $ \Gamma $, denoted by $ \partial(\Gamma) $, is then defined as the maximum differential over all possible subsets of $ V(\Gamma) $. Additionally, the subdivision operator $ {{\mathcal{S}}({\Gamma})} $ is defined as the graph obtained from $ \Gamma $ by inserting a new vertex on each edge of $ \Gamma $. In this paper, we present results for the differential of graphs on the subdivision operator $ {{\mathcal{S}}({\Gamma})} $ where some of these show exact values of $ \partial({{\mathcal{S}}({\Gamma})}) $ if $ \Gamma $ belongs to a classical family of graphs. We obtain bounds for $ \partial({{\mathcal{S}}({\Gamma})}) $ involving invariants of a graph such as order $ n $, size $ m $ and maximum degree $ \Delta $, and we study the realizability of the graph $ \Gamma $ for any value of $ \partial({{\mathcal{S}}({\Gamma})}) $ in the interval $ \left[n-2, \frac{n(n-1)}{2}-n+2\right] $. Moreover, we give a characterization for $ \partial({{\mathcal{S}}({\Gamma})}) $ using the notion of edge star packing.



    加载中


    [1] J. M. Sigarreta, Total domination on some graph operators, Mathematics, 9 (2021), 241. https://doi.org/10.3390/math9030241 doi: 10.3390/math9030241
    [2] S. Bermudo, Total domination on tree operators, Mediterr. J. Math., 20 (2023), 42. https://doi.org/10.1007/s00009-022-02236-7 doi: 10.1007/s00009-022-02236-7
    [3] A. Aslam, J. L. García-Guirao, S. Ahmad, W. Gao, Topological indices of the line graph of subdivision graph of complete bipartite graphs, Appl. Math. Inf. Sci., 11 (2017), 1631–1636. http://doi.org/10.18576/amis/110610 doi: 10.18576/amis/110610
    [4] A. R. Bindusree, I. N. Cangul, V. Lokesha, A. S. Cevik, Zagreb polynomials of three graph operators, Filomat, 30 (2016), 1979–1986. http://doi.org/10.2298/FIL1607979B doi: 10.2298/FIL1607979B
    [5] J. C. Hernández-Gómez, J. A. Méndez-Bermúdez, J. M. Rodríguez, J. M. Sigarreta, Harmonic index and harmonic polynomial on graph operations, Symmetry, 10 (2018), 456. https://doi.org/10.3390/sym10100456 doi: 10.3390/sym10100456
    [6] V. Lokesha, R. Shruti, P. S. Ranjini, A. Sinan-Cevik, On certain topological indices of nanoestructures using ${{\mathcal{Q}}({G})}$ and ${{\mathcal{R}}({G})}$ operators, Commun. Fac. Sci. Univ. Ankara Ser. A1 Math. Stat., 67 (2018), 178–187.
    [7] P. S. Ranjini, V. Lokesha, Smarandache-Zagreb index on three graph operators, Int. J. Math. Comb., 3 (2010), 1. https://doi.org/10.5281/ZENODO.9051 doi: 10.5281/ZENODO.9051
    [8] W. Yan, B. Y. Yang, Y. N. Yeh, The behavior of Wiener indices and polynomials of graphs under five graph decorations, Appl. Math. Lett., 20 (2007), 290–295. https://doi.org/10.1016/j.aml.2006.04.010 doi: 10.1016/j.aml.2006.04.010
    [9] W. Carballosa, J. M. Rodríguez, J. M. Sigarreta, N. Vakhania, f-polynomial on some graph operations, Mathematics, 7 (2019), 1074. https://doi.org/10.3390/math7111074 doi: 10.3390/math7111074
    [10] W. Carballosa, J. M. Rodríguez, J. M. Sigarreta, M. Villeta, On the hyperbolicity constant of line graphs, Electron. J. Comb., 18 (2011), 210. https://doi.org/10.37236/697 doi: 10.37236/697
    [11] F. Harary, R. Z. Norman, Some properties of line digraphs, Rend. Circ. Mat. Palermo, 9 (1960), 161–168. https://doi.org/10.1007/BF02854581 doi: 10.1007/BF02854581
    [12] J. A. Méndez-Bermúdez, R. Reyes, J. M. Rodríguez, J. M. Sigarreta, Hyperbolicity on graph operators, Symmetry, 10 (2018), 360. https://doi.org/10.3390/sym10090360 doi: 10.3390/sym10090360
    [13] R. Nagarathinam, N. Parvathi, Study of chromatic parameters of line, total, middle graphs and graph operators of bipartite graph, J. Phys. Conf. Ser. 1000 (2018), 012036. https://doi.org/10.1088/1742-6596/1000/1/012036 doi: 10.1088/1742-6596/1000/1/012036
    [14] C. Natarajan, S. K. Ayyaswamy, A note on the hop domination number of a subdivision graph, Int. J. Appl. Math., 32 (2019), 381. https://doi.org/10.12732/ijam.v32i3.2 doi: 10.12732/ijam.v32i3.2
    [15] P. S. Ranjini, V. Lokesha, S. Kumar, Degree sequence of graph operator for some standard graphs, Appl. Math. Nonlinear Sci., 5 (2020), 99–108. https://doi.org/10.2478/amns.2020.2.00018 doi: 10.2478/amns.2020.2.00018
    [16] J. M. Sigarreta, J. A. Rodríguez, On defensive alliances and line graphs, Appl. Math. Lett., 19 (2006), 1345–1350. https://doi.org/10.1016/j.aml.2006.02.001 doi: 10.1016/j.aml.2006.02.001
    [17] J. Mashburn, T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, P. J. Slater, Differentials in graphs, Util. Math., 69 (2006), 43–54.
    [18] S. Bermudo, H. Fernau, Computing the differential of a graph: hardness, approximability and exact algorithms, Discrete Appl. Math., 165 (2014), 69–82. https://doi.org/10.1016/j.dam.2012.11.013 doi: 10.1016/j.dam.2012.11.013
    [19] L. A. Basilio, S. Bermudo, J. M. Sigarreta, Bounds on the differential of a graph, Util. Math., 103 (2017), 319–334.
    [20] S. Bermudo, H. Fernau, Lower bound on the differential of a graph, Discrete Math., 312 (2012), 3236–3250. https://doi.org/10.1016/j.disc.2012.07.021 doi: 10.1016/j.disc.2012.07.021
    [21] S. Bermudo, J. M. Rodriguez, J. M. Sigarreta, On the differential in graphs, Util. Math., 97 (2015), 257–270.
    [22] L. A. Basilio, S. Bermudo, J. Leaños, J. M. Sigarreta, The differential of the line graph $\mathcal{L}(G)$, Discrete Appl. Math., 321 (2022), 82–89. https://doi.org/10.1016/j.dam.2022.05.004 doi: 10.1016/j.dam.2022.05.004
    [23] L. A. Basilio, J. Castro-Simón, J. Leaños, O. R. Cayetano, The differential on graph operator ${{\mathcal{Q}}({G})}$, Symmetry, 12 (2020), 751. https://doi.org/10.3390/sym12050751 doi: 10.3390/sym12050751
    [24] S. Bermudo, L. De la Torre, A. M. Martín-Caraballo, J. M. Sigarreta, The differential of the strong product graphs, Int. J. Comput. Math., 92 (2015), 1124–1134. https://doi.org/10.1080/00207160.2014.941359 doi: 10.1080/00207160.2014.941359
    [25] J. M. Sigarreta, Differential in cartesian product graphs, Ars Comb., 126 (2016), 259–267.
    [26] C. Armada, J. S. Canoy, A-differential of graphs, Int. J. Math. Anal., 9 (2015), 2171–2180. http://doi.org/10.12988/ijma.2015.54132 doi: 10.12988/ijma.2015.54132
    [27] L. A. Basilio, S. Bermudo, J. Leaños, J. M. Sigarreta, $\beta$ -differential of a graph, Symmetry, 9 (2017), 205. https://doi.org/10.3390/sym9100205 doi: 10.3390/sym9100205
    [28] A. Cabrera-Martínez, J. A. Rodríguez-Velázquez, On the perfect differential of a graph, Quaest. Math., 45 (2022), 327–345. https://doi.org/10.2989/16073606.2020.1858992 doi: 10.2989/16073606.2020.1858992
    [29] S. Bermudo, On the differential and roman domination number of a graph with minimum degree two, Discrete Appl. Math., 232 (2017), 64–72. https://doi.org/10.1016/j.dam.2017.08.005 doi: 10.1016/j.dam.2017.08.005
    [30] S. Bermudo, H. Fernau, Combinatorics for smaller kernels: the differential of a graph, Theor. Comput. Sci., 562 (2015), 330–345. https://doi.org/10.1016/j.tcs.2014.10.007 doi: 10.1016/j.tcs.2014.10.007
    [31] S. Bermudo, H. Fernau, J. M. Sigarreta, The differential and the roman domination number of a graph, Appl. Anal. Discrete Math., 8 (2014), 155–171. https://doi.org/10.2298/AADM140210003B doi: 10.2298/AADM140210003B
    [32] A. Kanli, Z. N. O. Berberler, Differential in infrastructure networks, RAIRO Oper. Res., 55 (2021), S1249–S1259. https://doi.org/10.1051/ro/2020032 doi: 10.1051/ro/2020032
    [33] P. Pushpam, D. Yokesh, Differential in certain classes of graphs, Tamkang J. Math., 41 (2010), 129–138. https://doi.org/10.5556/j.tkjm.41.2010.664 doi: 10.5556/j.tkjm.41.2010.664
    [34] L. A. Basilio, W. Carballosa, J. Leaños, J. M. Sigarreta, On the differential polynomial of a graph, Acta Math. Sin. Engl. Ser., 35 (2019), 338–354. https://doi.org/10.1007/s10114-018-7307-3 doi: 10.1007/s10114-018-7307-3
    [35] T. Gallai, Uber extreme punkt-und kantenmengen, annales universitatis scientiarum budapestinensis de rolando eotvos nominatae, Sect. Math., 2 (1959), 133–138.
  • Reader Comments
  • © 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1086) PDF downloads(77) Cited by(0)

Article outline

Figures and Tables

Figures(7)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog