加边对图的弱凸控制数和凸控制数的影响

The Influence of the Edge Adding on the Weakly Convex and Convex Domination Number of Graphs

摘要: 令 G = (V, E) 是一个连通图。用 d_G(u, v) 表示图 G 中的两个顶点 u 和 v 之间的最短(u, v) 路的长，一个长 为 dG(u, v) 的(u, v) 路 一个(u, v) -测地线。图 G 的一个点子集 X ⊆ V 叫做图 G 的一个弱凸集，如果对 X 中的任意两个顶点 a, b ，在图 G 中都存在一个(a, b) -测地线使得(a, b) - 测地线上的所有顶点都属千 X。类似地，图 G 的一个点子集 X ⊆ V 叫做图 G 的一个凸集，如果对 X 中的任意两个顶点 a, b, 图 G 中的每一条(a, b) -测地线上的所有顶点都属千 X。图 G 的一个点子集 D ⊆ V 叫做图 G 的一个控制集，如果 V -D 中的每一个顶点都至少有一个邻点在 D 中. V 的点子集 X 为 G 的弱凸控制集，如果 X 既是弱凸集又是控制集。图 G 的弱凸控制数，是点数最少的弱凸控制集所包含的点数，记为 γ_wcon(G)。图 G 的凸控制集和凸控制数类似正义，用 γ_con(G) 来表示图 G 的凸控制数。本文主要研究了加边对一些图类的弱凸控制数和凸控制数的影响。

Abstract: Let G = (V, E) be a connected graph. The distance d_G(u, v) between two vertices u and v in a connected graph G is the length of the shortest (u, v) path in G.  A (u, v) path   of length dG(u, v) is called a (u, v)-geodesic.  A set X ⊆ V  is called weakly convex in G if for every two vertices a, b ∈ X, there exists an (a, b)- geodesic, all of whose vertices belong to X. A set X is convex in G if for all a, b ∈ X all vertices from every (a, b)- geodesic belong to X. A subset D of V  is dominating  in G if every vertex of V − D has  at least one neighbour in D.  A set X ⊆ V  is called weakly convex dominating set  in G if it is weakly convex and dominating, and called convex dominating set in G if it is convex and dominating. The weakly convex domination number of a graph G is the minimum cardinality of a weakly convex dominating set of G, while the convex domination number of a graph G is the minimum cardinality of a convex dominating set of G, denoted by γ_wcon(G) and γ_con(G), respectively. In this paper, we  study edge adding and its effect  on the weakly convex domination numbers and convex domination numbers for some graphs.