| Autor: |
Hernández Basilio, Ludwin Ali, Macías, Jesús Leaños, Cayetano, Omar Rosario, Sigarreta Almira, José María, Hernández Basilio, Ludwin Ali, Macías, Jesús Leaños, Cayetano, Omar Rosario, Sigarreta Almira, José María |
| Zdroj: |
RAIRO - Operations Research; November 2024, Vol. 58 Issue: 6 p5467-5479, 13p |
| Abstrakt: |
Let G= (V(G), E(G)) be a simple graph with vertex set V(G) and edge set E(G). Let Sbe a subset of V(G), and let B(S) be the set of neighbours of Sin V(G)∖S. The differential ∂(S) of Sis the number |B(S)|−|S|. The maximum value of ∂(S) taken over all subsets S⊆V(G) is the differential ∂(G) of G. The graph R(G) is defined as the graph obtained from Gby adding a new vertex vefor each e∈E(G), and by joining veto the end vertices of e. In this paper we study the relationship between ∂(G) and ∂(R(G)), and give tight asymptotic bounds for ∂(R(G)). We also exhibit some relationships between certain vertex sets of Gand R(G) which involve well known graph theoretical parameters. |
| Databáze: |
Supplemental Index |
| Externí odkaz: |
|
