2020/01/14 by Maryam Alipour, Alipour, Maryam
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Graph theory and applications #Topological and Geometric Data Analysis #math.CO #msc:05C31 #msc:05C69
paper · pdf · doi:10.48550/arxiv.2001.04870
11 pages
arxiv created 2020/01/16 · arxiv updated 2020/01/17
The neighborhood polynomial of graph G, denoted by N(G,x), is the generating function for the number of vertex subsets of G which are subsets of open neighborhoods of vertices in G. For any graph polynomial, it can be useful to generate a new family of polynomials by introducing some restrictions and characterizations. In this paper, we investigate two new graph polynomials that are obtained from N(G,x) by adding independence or connectivity restrictions to the vertex subsets or to the subgraphs induced by the vertex subsets which are generated by N(G,x). These new polynomials are not only related to N(G,x), but also having strong connections to other known graph polynomials of G or its subgraphs, such as independence polynomials or subgraph component polynomials.