论文标题
在star- $ k $ -pcgs：探索小$ k $ values的班级边界
On star-$k$-PCGs: Exploring class boundaries for small $k$ values
论文作者
论文摘要
图$ g =（v，e）$是star-$ k $ -pcg，如果存在权重函数$ w：v \ rightarrow r^+$和$ k $互用间隔$ i_1，i_2，i_2，i_2，\ ldots i_k $，以便在e $ y $ in $ if和if w w（u）中有一个edge $ uv \ y_ $ i i i if y（u）in y $ i i i i i if in y y y y（u）这些图与图形的两个重要类别有关：PCG和多坐孔图形。众所周知，对于任何图形$ g $，都有$ k $，因此$ g $是恒星-K $ -pcg。因此，对于给定的图形$ g $，很有趣的是，哪个是最低$ k $，因此$ g $是star-$ k $ -pcg。我们将最低$ k $定义为图表的星号，以$γ（g）$表示。在这里，我们研究了简单的图类类别的星数，例如小尺寸，毛毛虫，周期和网格的图形。具体而言，我们确定所有图形最多具有7个顶点的$γ（g）$的确切值。通过这样做，我们证明了2号恒星2的最小图仅4个，并且具有5个顶点。恒星数字3的最小图仅3，并且完全具有7个顶点。接下来，我们提供了一个结构，表明毛毛虫的恒星数量是其中之一。此外，我们表明，恒星数量和二维网格图为2，而$ 4 $维网格的星号至少为3。
A graph $G=(V,E)$ is a star-$k$-PCG if there exists a weight function $w: V \rightarrow R^+$ and $k$ mutually exclusive intervals $I_1, I_2, \ldots I_k$, such that there is an edge $uv \in E$ if and only if $w(u)+w(v) \in \bigcup_i I_i$. These graphs are related to two important classes of graphs: PCGs and multithreshold graphs. It is known that for any graph $G$ there exists a $k$ such that $G$ is a star-$k$-PCG. Thus, for a given graph $G$ it is interesting to know which is the minimum $k$ such that $G$ is a star-$k$-PCG. We define this minimum $k$ as the star number of the graph, denoted by $γ(G)$. Here we investigate the star number of simple graph classes, such as graphs of small size, caterpillars, cycles and grids. Specifically, we determine the exact value of $γ(G)$ for all the graphs with at most 7 vertices. By doing so we show that the smallest graphs with star number 2 are only 4 and have exactly 5 vertices; the smallest graphs with star number 3 are only 3 and have exactly 7 vertices. Next, we provide a construction showing that the star number of caterpillars is one. Moreover, we show that the star number of cycles and two dimensional grid graphs is 2 and that the star number of $4$-dimensional grids is at least 3. Finally, we conclude with numerous open problems.
