
arXiv: 1909.10701
The maximum average degree $\mathrm{mad}(G)$ of a graph $G$ is the maximum over all subgraphs of $G$, of the average degree of the subgraph. In this paper, we prove that for every $G$ and positive integer $k$ such that $\mathrm{mad}(G) \ge k$ there exists $S \subseteq V(G)$ such that $\mathrm{mad}(G - S) \le \mathrm{mad}(G) - k$ and $G[S]$ is $(k-1)$-degenerate. Moreover, such $S$ can be computed in polynomial time. In particular, if $G$ contains at least one edge then there exists an independent set $I$ in $G$ such that $\mathrm{mad}(G-I) \le \mathrm{mad}(G)-1$ and if $G$ contains a~cycle then there exists an induced forest $F$ such that $\mathrm{mad}(G-F) \le \mathrm{mad}(G) - 2$. As a side result, we also obtain a subexponential bound on the diameter of reconfiguration graphs of generalized colourings of graphs with bounded value of their $\mathrm{mad}$.
FOS: Computer and information sciences, Extremal problems in graph theory, Discrete Mathematics (cs.DM), Directed graphs (digraphs), tournaments, Vertex degrees, Planar graphs; geometric and topological aspects of graph theory, Coloring of graphs and hypergraphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), reconfiguration graphs, FOS: Mathematics, Mathematics - Combinatorics, Structural characterization of families of graphs, Combinatorics (math.CO), sparse graph classes, Flows in graphs, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Extremal problems in graph theory, Discrete Mathematics (cs.DM), Directed graphs (digraphs), tournaments, Vertex degrees, Planar graphs; geometric and topological aspects of graph theory, Coloring of graphs and hypergraphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), reconfiguration graphs, FOS: Mathematics, Mathematics - Combinatorics, Structural characterization of families of graphs, Combinatorics (math.CO), sparse graph classes, Flows in graphs, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
