Induced-paired dominating graphs of some graphs

An induced-paired dominating set D of a graph G is a set of vertices of G in which every vertex of G is adjacent to some vertex in D, and the subgraph induced by D contains only nonadjacent edges. The set D is minimal if every proper subset is not an induced-paired dominating set.An upper induced-paired domination number of G denoted by Gamma_{ip}(G), is the maximum cardinality of a minimal induced-paired dominating set of G.An induced-paired domination number of G, denoted by \gamma_{ip}(G), is the minimum cardinality of a minimal induced-paired dominating set.A minimal induced-paired dominating set of G is called an Gamma_{ip}(G)-set if its cardinality is Gamma_{ip}(G). Similarly, it is called a gamma_{ip}(G)-set if its cardinality is \gamma_{ip}(G). The Gamma-induced-paired dominating graph and the gamma-induced-paired dominating graph of G are the graphs whose vertices are Gamma_{ip}(G)-sets and gamma_{ip}(G)-sets, respectively. Two sets are adjacent in these two graphs if they differ by only one vertex. In this dissertation, we determine gamma-induced-paired dominating graphs of paths, cycles, complete graphs, wheel graphs, and complete bipartite graphs. We also determined Gamma-induced-paired dominating graphs of cycles, complete graphs, wheel graphs, and complete bipartite graphs.

图G的导出配对控制集（induced-paired dominating set）D，是指满足如下条件的G的顶点集：G中每一个顶点都与D中的某一顶点邻接，且由D所导出的子图仅包含互不邻接的边。若D的任意真子集都不是导出配对控制集，则称集合D为极小导出配对控制集。图G的上导出配对控制数（upper induced-paired domination number）记为Γ_{ip}(G)，其定义为G的所有极小导出配对控制集中顶点数的最大值。而图G的导出配对控制数（induced-paired domination number）记为γ_{ip}(G)，其定义为G的所有极小导出配对控制集中顶点数的最小值。若G的一个极小导出配对控制集的顶点数等于Γ_{ip}(G)，则称其为Γ_{ip}(G)集；同理，若其顶点数等于γ_{ip}(G)，则称其为γ_{ip}(G)集。图G的Γ导出配对控制图（Γ-induced-paired dominating graph）与γ导出配对控制图（γ-induced-paired dominating graph），分别是以其Γ_{ip}(G)集与γ_{ip}(G)集作为顶点的图。在这两类图中，当两个集合仅相差一个顶点时，二者互为邻接点。在本论文中，我们确定了路、环、完全图、轮图以及完全二部图的γ导出配对控制图；同时我们还确定了环、完全图、轮图以及完全二部图的Γ导出配对控制图。