Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/75947
Title: | Reducing the maximum degree of a graph : comparisons of bounds |
Authors: | Borg, Peter |
Keywords: | Mathematics Logic, Symbolic and mathematical Set theory Hypergraphs |
Issue Date: | 2021 |
Publisher: | Georgia Southern University |
Citation: | Borg, P. (2021). Reducing the maximum degree of a graph : comparisons of bounds. Theory and Applications of Graphs, 8(1), Article 6. |
Abstract: | Let λ(G) be the smallest number of vertices that can be removed from a non-empty graph G so that the resulting graph has a smaller maximum degree. Let λe(G) be the smallest number of edges that can be removed from G for the same purpose. Let k be the maximum degree of G, let t be the number of vertices of degree k, let M(G) be the set of vertices of degree k, let n be the number of vertices in the closed neighbourhood of M(G), and let m be the number of edges incident to vertices in M(G). Fenech and the author showed that λ(G)≤n+(k−1)t2k, and they essentially showed that λ(G)≤n(1−kk+1(n(k+1)t)1/k). They also showed that λe(G)≤m+(k−1)t2k−1 and λe(G)≤m(1−k−1k(mkt)1/(k−1)). These bounds are attained if k≥2 and G is the union of t pairwise vertex-disjoint (k+1)-vertex stars. For each of λ(G) and λe(G), the two bounds on the parameter are compared for the purpose of determining, for each bound, the cases in which the bound is better than the other. This work is also motivated by the likelihood that similar pairs of bounds will be discovered for other graph parameters and the same analysis can be applied. |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/75947 |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Reducing_the_maximum_degree_of_a_graph_comparisons_of_bounds_2021.pdf | 285.07 kB | Adobe PDF | View/Open |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.