Neighborhood and Domination Polynomials of Graphs

被引：0
作者：
Irene Heinrich
Peter Tittmann
机构：
[1] University Kaiserslautern,
[2] University of Applied Sciences Mittweida,undefined
来源：
Graphs and Combinatorics | 2018年 / 34卷
关键词：
Dominating set; Graph polynomial; Graphical enumeration; Neighborhood complex; 05C31; 05C69;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The neighborhood complex of a graph is the family of subsets of open neighborhoods of its vertices. The neighborhood polynomial is the ordinary generating function for the number of sets of the neighborhood complex with respect to their cardinality. This paper provides a new representation of the neighborhood polynomial as a sum over complete bipartite subgraphs of a graph. Using the close relation between the domination polynomial and the neighborhood polynomial of a graph, we can also give a new presentation of the domination polynomial. Finally we show that finding the number of certain double cliques of a graph is sufficient to determine the number of dominating sets of a graph.
引用
收藏
页码：1203 / 1216
页数：13
相关论文
共 23 条
[1]  
Akbari S(2010)Characterization of graphs using domination polynomials Eur. J. Comb. 31 1714-1724
[2]  
Alikhani S(2000)Mean value for the matching and dominating polynomials Discuss. Math. Graph Theory 20 57-69
[3]  
Peng Yh(2008)The neighbourhood polynomial of a graph Aust. J. Comb. 42 55-68
[4]  
Arocha JL(2015)Bipartition polynomials, the ising model, and domination in graphs Discuss. Math. Graph Theory 35 335-353
[5]  
Llano B(2006)The topology of the independence complex Eur. J. Comb. 27 906-923
[6]  
Brown JI(2007)Threshold graphs, shifted complexes, and graphical complexes Discrete Math. 307 2591-2597
[7]  
Nowakowski RJ(2012)Recurrence relations and splitting formulas for the domination polynomial Electron. J. Comb. 19 47-660
[8]  
Dod M(2014)Subset-sum representations of domination polynomials Graphs Comb. 30 647-324
[9]  
Kotek T(1978)Kneser’s conjecture, chromatic number, and homotopy J. Comb. Theory Ser. A 25 319-undefined
[10]  
Preen J(undefined)undefined undefined undefined undefined-undefined
123