“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 18132 |
|
| Abstract: | |
|
The â??-edge stability number esâ??(G) of a graph G is the minimum number of edges of G
whose removal results in a subgraph H with â??(H) = â??(G) - 1. Sets whose removal results
in a subgraph with smaller maximum degree are called mitigating sets. It is proved that
there always exists a mitigating set which induces a disjoint union of P2s and P3s. Minimum
mitigating sets which induce matchings are characterized. It is proved that to obtain an upper
bound of the form esâ??(G) â?ä c|V(G)| for an arbitrary graph G of given maximum degree â??,
where c is a given constant, it suffices to prove the bound for â??-regular graphs. Sharp upper
bounds of this form are derived for regular graphs. It is proved that esâ??(G) â?ä |V(G)|/2 if G
is a Class 1 graph, or G is a highly dense graph.
Download TeX format |
|
| back to top | |
