{
  "id": "2005.04556",
  "version": "v1",
  "published": "2020-05-10T02:40:21.000Z",
  "updated": "2020-05-10T02:40:21.000Z",
  "title": "The treewidth of 2-section of hypergraphs",
  "authors": [
    "Ke Liu",
    "Mei Lu"
  ],
  "categories": [
    "math.CO"
  ],
  "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\\not=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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-05-10T02:40:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "linear hypergraph",
      "algorithmic graph theory",
      "simple hypergraph",
      "important invariant",
      "minimum degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}