Graph polynomials for a class of DI-pathological graphs

AKCE International Journal of Graphs and Combinatorics

James M. Hammer¹  Joshua Harrington¹ 

[1] Department of Mathematics, Cedar Crest College;

关键词: graph domination;    di-pathological;    domination polynomial;    independence polynomial;    independent dominating polynomial;   

DOI  :  10.1016/j.akcej.2018.06.004

来源: DOAJ

【 摘 要 】

Let be a simple graph. A dominating set is a set such that the closed neighborhood of is the entire vertex set. An independence set of a graph is a subset of vertices that are pairwise non-adjacent. A DI-pathological graph is a graph where every minimum dominating set intersects every maximal independent set. Let denote the number of dominating sets of of size . The domination polynomial of a graph is defined by . Let denote the number of independent sets of size in a graph . The independence polynomial is defined by . In this paper, we will examine the domination polynomial and the independence polynomial of a family of extremal DI-pathological graphs. We will further define an independent dominating set and examine the corresponding independent domination polynomial for these graphs.

【 授权许可】

Unknown