The treewidth of 2-section of hypergraphs

Abstract

Let $H=(V,F)$ be a simple hypergraph without loops. $H$ is called linear if $|f\cap g|\le 1$ for any $f,g\in F$ with $f\ne g$. The $2$-section of $H$, denoted by $[H{]}_2$, is a graph with $V([H{]}_2)=V$ and for any $u,v\in V([H{]}_2)$, $uv\in E([H{]}_2)$ if and only if there is $f\in F$ such that $u,v\in f$. The treewidth of a graph is an important invariant in structural and algorithmic graph theory. In this paper, we consider the treewidth of the $2$-section of a linear hypergraph. We will use the minimum degree, maximum degree, anti-rank and average rank of a linear hypergraph to determine the upper and lower bounds of the treewidth of its $2$-section. Since for any graph $G$, there is a linear hypergraph $H$ such that $[H{]}_2\cong G$, we provide a method to estimate the bound of treewidth of graph by the parameters of the hypergraph.

arXiv admin note: text overlap with arXiv:1409.6810 by other authors