<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
Graphs of high girth have been much studied, especially in the context of the minimum vertex number of graphs of given girth and minimum degree. The authors study the treewidth \(\text{tw}(G)\) of a graph \(G\), giving a lower bound in terms of the girth \(g(G)\) and average degree \(d(G)\). They show that \[ \text{tw}(G)\geq c {1\over g(G)+1} (d(G)-1)^{\lfloor (g(G) -1)/2\rfloor} \] holds. Since the treewidth is smaller than the vertex number of the graph, \(\text{tw}(G) < v(G)\), and the existence of a graph with \[ v(G)\leq c^{\prime} (d(G)-1)^{\lfloor( g(G)-1 )/2\rfloor} \] is conjectured, this bound appears to be almost tight.
Extremal problems in graph theory, tree decomposition, Treewidth, Graph minors, Theoretical Computer Science, Tree decompositions, Minors, Girth, Computational Theory and Mathematics, average degree, minors, Discrete Mathematics and Combinatorics, Paths and cycles
Extremal problems in graph theory, tree decomposition, Treewidth, Graph minors, Theoretical Computer Science, Tree decompositions, Minors, Girth, Computational Theory and Mathematics, average degree, minors, Discrete Mathematics and Combinatorics, Paths and cycles
citations 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). | 23 | |
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). | Top 10% | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |