On the boundary polynomial of a graph

Abstract

In this work, we introduce the boundary polynomial of a graph $G$ as the ordinary generating function in two variables $B(G;x,y):=\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.

20 pages, 1 figure