Differential in infrastructure networks
RAIRO. Operations Research, Tome 55 (2021), pp. S1249-S1259

Let G = (V, E) be a graph of order n and let B(D) be the set of vertices in V \ D that have a neighbor in the vertex set D. The differential of a vertex set D is defined as ∂(D) = |B(D)| − |D| and the maximum value of ∂(D) for any subset D of V is the differential of G. A set D of vertices of a graph G is said to be a dominating set if every vertex in V \ D is adjacent to a vertex in D. G is a dominant differential graph if it contains a ∂-set which is also a dominating set. This paper is devoted to the computation of differential of wheel, cycle and path-related graphs as infrastructure networks. Furthermore, dominant differential wheel, cycle and path-related types of networks are recognized.

DOI : 10.1051/ro/2020032
Classification : 05C69
Keywords: Differential, domination, graph invariant 
@article{RO_2021__55_S1_S1249_0,
     author = {Kanli, Akin and Berberler, Zeynep Nihan Odabas\c{s}},
     title = {Differential in infrastructure networks},
     journal = {RAIRO. Operations Research},
     pages = {S1249--S1259},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     doi = {10.1051/ro/2020032},
     mrnumber = {4223163},
     zbl = {1469.05132},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2020032/}
}
TY  - JOUR
AU  - Kanli, Akin
AU  - Berberler, Zeynep Nihan Odabasş
TI  - Differential in infrastructure networks
JO  - RAIRO. Operations Research
PY  - 2021
SP  - S1249
EP  - S1259
VL  - 55
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2020032/
DO  - 10.1051/ro/2020032
LA  - en
ID  - RO_2021__55_S1_S1249_0
ER  - 
%0 Journal Article
%A Kanli, Akin
%A Berberler, Zeynep Nihan Odabasş
%T Differential in infrastructure networks
%J RAIRO. Operations Research
%D 2021
%P S1249-S1259
%V 55
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2020032/
%R 10.1051/ro/2020032
%G en
%F RO_2021__55_S1_S1249_0
Kanli, Akin; Berberler, Zeynep Nihan Odabasş. Differential in infrastructure networks. RAIRO. Operations Research, Tome 55 (2021), pp. S1249-S1259. doi: 10.1051/ro/2020032

L. A. Basilio, S. Bermudo and J. M. Sigarreta, Bounds on the differential of a graph. Utilitas Math. 103 (2017) 319–334. | MR | Zbl

S. Bermudo, On the differential and Roman domination number of a graph with minimum degree two. Disc. Appl. Math. 232 (2017) 64–72. | MR | Zbl | DOI

S. Bermudo and H. Fernau, Lower bounds on the differential of a graph. Disc. Math. 312 (2012) 3236–3250. | MR | Zbl | DOI

S. Bermudo and H. Fernau, Computing the differential of a graph: hardness, approximability and exact algorithms. Disc. Appl. Math. 165 (2014) 69–82. | MR | Zbl | DOI

S. Bermudo and H. Fernau, Combinatorics for smaller kernels: the differential of a graph. Theor. Comput. Sci. 562 (2015) 330–345. | MR | Zbl | DOI

S. Bermudo, H. Fernau and J. M. Sigarreta, The differential and the Roman domination number of a graph. Appl. Anal. Disc. Math. 8 (2014) 155–171. | MR | Zbl | DOI

S. Bermudo, J. C. Hernández-Gómez, J. M. Rodríguez and J. M. Sigarreta, Relations between the differential and parameters in graphs. Electron. Notes Disc. Math. 46 (2014) 281–288. | MR | Zbl | DOI

S. Bermudo, L. De La Torre, A. M. Martín-Caraballo and J. M. Sigarreta, The differential of the strong product graphs. Int. J. Comput. Math. 92 (2015) 1124–1134. | MR | Zbl | DOI

S. Bermudo, J. M. Rodríguez and J. M. Sigarreta, On the differential in graphs. Utilitas Math. 97 (2015) 257–270. | MR | Zbl

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd edition. The MIT Press, Cambridge, MA (2009). | MR | Zbl

M. Cygan, M. Pilipczuk and R. Škrekovski, Relation between Randić index and average distance of trees. MATCH Commun. Math. Comput. Chem. 66 (2011) 605–612. | MR | Zbl

J. A. Gallian, A dynamic survey of graph labeling. Electron. J. Comb. 15 (2008) DS6. | MR | Zbl

J. H. Hattingh and E. Ungerer, The signed and minus k -subdomination numbers of comets. Disc. Math. 183 (1998) 141–152. | MR | Zbl | DOI

J. C. Hernández-Gómez, Differential and operations on graphs. Int. J. Math. Anal. 9 (2015) 341–349. | DOI

I. Javaid and S. Shokat, On the partition dimension of some wheel related graphs. J. Prime Res. Math. 4 (2008) 154–164. | MR | Zbl

J. R. Lewis, Differentials of graphs, Master’s thesis. East Tennessee State University, Johnson City, TN (2004).

J. L. Mashburn, T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi and P. J. Slater, Differentials in graphs. Utilitas Math. 69 (2006) 43–54. | MR | Zbl

M. J. Morgan, S. Mukwembi and H. C. Swart, On the eccentric connectivity index of a graph. Disc. Math. 311 (2011) 1229–1234. | MR | Zbl | DOI

P. R. L. Pushpam and D. Yokesh, Differential in certain classes of graphs. Tamkang J. Math. 41 (2010) 129–138. | MR | Zbl | DOI

J. M. Sigarreta, Differential in cartesian product graphs. Ars Comb. CXXVI (2016) 259–267. | MR | Zbl

D. B. West, Introduction to Graph Theory. Prentice Hall, NJ (2001). | Zbl

Cité par Sources :