Mycielskian图的凸控制和弱凸控制数的研究

Research on Convex and Weakly Convex Domination Numbers of Mycielskian Graphs

摘要: 令 G = (V, E) 是一个连通图。用 d_G(u, v) 表示图 G 中的两个顶点 u 和 u 之间的最短(u, v) 路的长 ，一个长 为 d_G(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) (或γ_con(G)). 本文主要给出了一些特殊图的Mycielskian图的控制数、弱凸控制数和凸控制数的确切值。

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