2025/05/07 by Walter Carballosa, Carballosa, Walter, Marcos Masip +3
Computer Science · Mathematics · #05C31 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2505.04092
openalex publication_date 2025/05/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work, we introduce the boundary polynomial of a graph G as the ordinary generating function in two variables B(G;x,y):= ∑S⊆ 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), 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^′;x,y) for the graphs G^′ 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.