Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/111344
Title: | Equating two maximum degrees |
Authors: | Caro, Yair Lauri, Josef Zarb, Christina |
Keywords: | Mathematics Graph theory Hypergraphs |
Issue Date: | 2018 |
Publisher: | Centre for Discrete Mathematics & Computing |
Citation: | Caro, Y., Lauri, J., & Zarb, C. (2018). Equating two maximum degrees. Australasian Journal of Combinatorics, 72(2), 206-225. |
Abstract: | Given a graph G and a positive integer k, we would like to find (if it exists) the largest induced subgraph H in which there are at least k vertices realizing the maximum degree of H. This problem was first posed by Caro and Yuster. They proved, for example, that for every graph G on n vertices we can guarantee, for k = 2, such an induced subgraph H by deleting at most 2√n vertices, but the question of whether 2√n is best possible remains open. |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/111344 |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Equating_two_maximum_degrees_2018.pdf Restricted Access | 275.11 kB | Adobe PDF | View/Open Request a copy |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.