Matching of 5-gamma-critical leafless graph with a cut edge
Matching of 5-gamma-critical leafless graph with a cut edge
复制标题
5-gamma 临界无叶图与切边的匹配
DOI：
10.1016/j.amc.2017.11.050
复制
发表时间：
2018
影响因子：
4
通讯作者：
Lu Mei
中科院分区：
文献类型：
--
作者：
Yang Yuxuan;Lu Mei
给定图G=(V， E)，如果V∈S中的每个顶点与S中的一个顶点相邻，则V的子集S是G的支配集。图G中的支配集的最小基数称为G的支配数，用γ (G)表示。如果γ (G)= k，则图G是k-γ-临界的，但对于每条边e∈e （G¯），γ (G+ e)< k，其中G¯是G的补。在本文中，我们首先给出了具有非平凡切边的k-γ-临界连通图的结构。然后证明了每一个5-γ临界偶阶无叶连通图都包含一个完美匹配。
Given a graph G=(V, E), a subset S of V is a dominating set of G if every vertex in V∖ S is adjacent to a vertex in S. The minimum cardinality of a dominating set in a graph G is called the domination number of G and is denoted by γ (G). A graph G is said to be k-γ-critical if γ (G)= k, but γ (G+ e)< k for each edge e∈ E (G¯), where G¯ is the complement of G. In this paper, we first provide the structure of k-γ-critical connected graphs with a nontrivial cut edge. Then we establish that each 5-γ-critical leafless connected graph of even order contains a perfect matching.