共查询到19条相似文献,搜索用时 103 毫秒
1.
我们分别用γ(G),β(G)和α(G)表示图G的控制数、匹配数和覆盖数,对任意连通图,有γ(G)≤β(G)≤α(G)成立,1998年,Randerath和Volkmann给出了控制数等于覆盖数的图的特征,本文首先证明了匹配数与控制数相等的图其最小度不超过2,而后给出了最小度为2的图的结构性质。 相似文献
2.
3.
设G是一个图。G的最小度,连通度,控制数,独立控制数和独立数分别用δ,k,γ,i和α表示,图G是3-γ-临界的,如果γ=3,而且G增加任一条边所得的图的控制数为2.Sumner和Blitch猜想:任意连通的3-γ临界图满足i=3,本文证明了如果G是使α=k 1≤δ的连通3-γ-临界图,那么Sumner-Blitch猜想成立。 相似文献
4.
5.
6.
图的强符号全控制数有着许多重要的应用背景,因而确定其下界有重要的意义.本文提出了图的强符号全控制数的概念,在构造适当点集的基础上对其进行了研究,给出了:(1)一般图的强符号全控制数的5个独立可达的下界及达到其界值的图;(2)确定了圈、轮图、完全图、完全二部图的强符号全控制数的值. 相似文献
7.
特殊图类的符号控制数 总被引:2,自引:1,他引:1
王军秀 《纯粹数学与应用数学》2005,21(1):59-61
图G的符号控制数γS(G)有着许多重要的应用背景.已知它的计算是NP-完全问题,因而确定其上下界有重要意义.本文研究了1)一般图G的符号控制数,给出了一个新的下界;2)确定了Cn图的符号控制数的精确值. 相似文献
8.
《数学的实践与认识》2015,(17)
设G=(V,E)是一个无孤立点的图,一个实值函数f:E(G)→[0,1]若对所有的点u∈V(G),均有∑uv∈Ef(uv)≥1成立,则称f为图G的一个Fractional星控制函数.图G的Fractional星控制数定义为γ_(fs)(G)=min{∑uv∈Ef(uv)|f为图G的一个Fractional星控制函数}.研究了几类乘积图的Fractional星控制问题,给出了一些常见特殊图的Fractional星控制数,主要确定了积图P_m×P_n和C_m×P_n的Fractional星控制数. 相似文献
9.
本文研究了图的反符号圈控制的问题.利用分类和反证的方法,获得了满足反符号圈控制数为负边数加4的连通图的刻画和完全二部分图的反符号圈控制数. 相似文献
10.
11.
A subset S of vertices of a graph G with no isolated vertex is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex in V (G) S is also adjacent to a vertex in V (G) S. The total restrained domination number of G is the minimum cardinality of a total restrained dominating set of G. In this paper we initiate the study of total restrained bondage in graphs. The total restrained bondage number in a graph G with no isolated vertex, is the minimum cardinality of a subset of edges E such that G E has no isolated vertex and the total restrained domination number of G E is greater than the total restrained domination number of G. We obtain several properties, exact values and bounds for the total restrained bondage number of a graph. 相似文献
12.
Vladimir Samodivkin 《Czechoslovak Mathematical Journal》2013,63(1):191-204
For a graph property P and a graph G, we define the domination subdivision number with respect to the property P to be the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to change the domination number with respect to the property P. In this paper we obtain upper bounds in terms of maximum degree and orientable/non-orientable genus for the domination subdivision number with respect to an induced-hereditary property, total domination subdivision number, bondage number with respect to an induced-hereditary property, and Roman bondage number of a graph on topological surfaces. 相似文献
13.
Total domination critical and stable graphs upon edge removal 总被引:1,自引:0,他引:1
A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. A graph is total domination edge critical if the removal of any arbitrary edge increases the total domination number. On the other hand, a graph is total domination edge stable if the removal of any arbitrary edge has no effect on the total domination number. In this paper, we characterize total domination edge critical graphs. We also investigate various properties of total domination edge stable graphs. 相似文献
14.
The bondage number b (G ) of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with domination number greater than that of G . Denote P n × P m the Cartesian product of two paths P n and P m . This paper determines the exact values of b (P n × P 2), b (P n × P 3), and b(P n × P 4) for n ≥2. 相似文献
15.
16.
Stephanie A. RickettTeresa W. Haynes 《Discrete Applied Mathematics》2011,159(10):1053-1057
A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Two vertices of G are said to be dotted (identified) if they are combined to form one vertex whose open neighborhood is the union of their neighborhoods minus themselves. We note that dotting any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most 2. A graph is total domination dot-stable if dotting any pair of adjacent vertices leaves the total domination number unchanged. We characterize the total domination dot-stable graphs and give a sharp upper bound on their total domination number. We also characterize the graphs attaining this bound. 相似文献
17.
The bondage number of a graph is the smallest number of its edges whose removal results in a graph having a larger domination number. We provide constant upper bounds for the bondage number of graphs on topological surfaces, and improve upper bounds for the bondage number in terms of the maximum vertex degree and the orientable and non-orientable genera of graphs. Also, we present stronger upper bounds for graphs with no triangles and graphs with the number of vertices larger than a certain threshold in terms of graph genera. This settles Teschner’s Conjecture in affirmative for almost all graphs. As an auxiliary result, we show tight lower bounds for the number of vertices of graphs 2-cell embeddable on topological surfaces of a given genus. 相似文献
18.
MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213–229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. Henning, Domination in planar graphs with small diameter, J. Graph Theory 40 (2002) 1–25] showed that there is a unique planar graph of diameter two with domination number three. It follows that the total domination number of a planar graph of diameter two is at most three. In this paper, we consider the problem of characterizing planar graphs with diameter two and total domination number three. We say that a graph satisfies the domination-cycle property if there is some minimum dominating set of the graph not contained in any induced 5-cycle. We characterize the planar graphs with diameter two and total domination number three that satisfy the domination-cycle property and show that there are exactly thirty-four such planar graphs. 相似文献
19.
A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. A graph is total domination edge addition stable if the addition of an arbitrary edge has no effect on the total domination number. In this paper, we characterize total domination edge addition stable graphs. We determine a sharp upper bound on the total domination number of total domination edge addition stable graphs, and we determine which combinations of order and total domination number are attainable. We finish this work with an investigation of claw-free total domination edge addition stable graphs. 相似文献