论文标题
超图2部分的树宽
The treewidth of 2-section of hypergraphs
论文作者
论文摘要
令$ h =（v，f）$为无循环的简单超图。 $ h $如果$ | f \ cap g | \ le 1 $对于任何$ f，g \ in f $ a $ f \ not = g $。 $ 2 $ - $ h $的节，由$ [h] _2 $表示，是$ v（[h] _2）= v $的图形，对于任何$ u，v \ in v（[h] _2）$，$ uv \ in E（[h] _2）$，仅在f $ f $ f $中$ f $ f \ uv $，图的树宽是在结构和算法图理论中的重要不变。在本文中，我们考虑了线性超图的$ 2 $部分的树宽。我们将使用线性超图的最低度，最高度，反级和平均等级来确定其$ 2 $分段的树宽的上限和下限。由于对于任何图$ g $，因此有一个线性超图$ h $，因此$ [h] _2 \ cong g $，我们提供了一种通过HyperGraph的参数来估算图形宽度的方法。
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.
