标题： 关于图的边界多项式 显示英文标题

标题： On the boundary polynomial of a graph

摘要： 在这项工作中，我们引入图 $G$ 的边界多项式作为两个变量 $B(G;x,y):= \displaystyle\sum_{S\subseteq V(G)} x^{|B(S)|}y^{|S|}$ 的普通生成函数，其中 $B(S)$ 表示 $S$ 的外边界。 我们研究了这个图多项式，得到了该多项式的某些代数性质。 我们发现 $G$ 的一些参数在 $B(G;x,y)$、\emph{例如}、图 $G$ 的支配数、罗马支配数、顶点连通度和微分中以代数方式编码。 此外，我们计算了一些经典图族的边界多项式。 我们还建立了$B(G;x,y)$与$B(G^\prime;x,y)$之间的某些关系，这些关系涉及通过删除、添加和细分边从$G$图得到的图$G^\prime$。此外，我们证明了一个图$G$包含孤立顶点当且仅当其边界多项式有一个因子 ($y+1$)。最后，我们表明完全图、少一条边的完全图、空图、路径图、圈图、轮图、星图、双星图等许多图类都可以由边界多项式来刻画。 显示英文摘要

摘要： In this work, we introduce the boundary polynomial of a graph $G$ as the ordinary generating function in two variables $B(G;x,y):= \displaystyle\sum_{S\subseteq V(G)} x^{|B(S)|}y^{|S|}$, where $B(S)$ denotes the outer boundary of $S$. We investigate this graph polynomial obtaining some algebraic properties of the polynomial. We found that some parameters of $G$ are algebraically encoded in $B(G;x,y)$, \emph{e.g.}, domination number, Roman domination number, vertex connectivity, and differential of the graph $G$. Furthermore, we compute the boundary polynomial for some classic families of graphs. We also establish some relationships between $B(G;x,y)$ and $B(G^\prime;x,y)$ for the graphs $G^\prime$ obtained by removing, adding, and subdividing an edge from $G$. In addition, we prove that a graph $G$ has an isolated vertex if and only if its boundary polynomial has a factor ($y+1$). Finally, we show that the classes of complete, complete without one edge, empty, path, cycle, wheel, star, double-star graphs, and many others are characterized by the boundary polynomial.