共查询到20条相似文献,搜索用时 15 毫秒
1.
A set D of vertices of a graph G = (V, E) is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed's result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most (3n +IV21)/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk (G, γ) ≤ (3n+5k)/8 for all graphs of order n with minimum degree at least 3. 相似文献
2.
Paul Dorbec Michael A. Henning Mickael Montassier Justin Southey 《Journal of Graph Theory》2015,80(4):329-349
A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by , is the minimum cardinality of an independent dominating set. In this article, we show that if is a connected cubic graph of order n that does not have a subgraph isomorphic to K2, 3, then . As a consequence of our main result, we deduce Reed's important result [Combin Probab Comput 5 (1996), 277–295] that if G is a cubic graph of order n, then , where denotes the domination number of G. 相似文献
3.
Let G be a finite and simple graph with vertex set V(G), and let f:V(G)→{−1,1} be a two-valued function. If ∑x∈N[v]f(x)≥1 for each v∈V(G), where N[v] is the closed neighborhood of v, then f is a signed dominating function on G. A set {f1,f2,…,fd} of signed dominating functions on G with the property that for each x∈V(G), is called a signed dominating family (of functions) on G. The maximum number of functions in a signed dominating family on G is the signed domatic number on G. In this paper, we investigate the signed domatic number of some circulant graphs and of the torus Cp×Cq. 相似文献
4.
关于图的减控制与符号控制 总被引:18,自引:2,他引:18
给定一个图G=(V,E),一个函数f:V→{-1,0,1}被称为G的减控制函数,如果对任意v∈V(G)均有∑μ∈N[v]f(μ)≥1。G的减控制数定义为γ-(G)=min{∑v∈Vf(v)|f是G的减控制函数}。图G的符号控制函数的正如减控制函数,差别是广{-1,0,1}换成{-1,1}。符号控制数γs(G)是类似的。本文获得γ-G)和γs(G)的一些下界。同时也证明并推广了 Jean Dunbar等提出的一个猜想,即对任意 n阶 2部图 G,均有γ-(G)≥ 4(n+11/2-1)-n成立。 相似文献
5.
It was proved by Hell and Zhu that, if G is a series‐parallel graph of girth at least 2⌊(3k − 1)/2⌋, then χc(G) ≤ 4k/(2k − 1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series‐parallel graph G of girth 2⌊(3k − 1)/2⌋ − 1 such that χc(G) > 4k/(2k − 1). © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 185–198, 2000 相似文献
6.
7.
V. E. Zverovich 《Journal of Graph Theory》1998,29(3):139-149
Let γ(G) and ir(G) denote the domination number and the irredundance number of a graph G, respectively. Allan and Laskar [Proc. 9th Southeast Conf. on Combin., Graph Theory & Comp. (1978) 43–56] and Bollobás and Cockayne [J. Graph Theory (1979) 241–249] proved independently that γ(G) < 2ir(G) for any graph G. For a tree T, Damaschke [Discrete Math. (1991) 101–104] obtained the sharper estimation 2γ(T) < 3ir(T). Extending Damaschke's result, Volkmann [Discrete Math. (1998) 221–228] proved that 2γ(G) ≤ 3ir(G) for any block graph G and for any graph G with cyclomatic number μ(G) ≤ 2. Volkmann also conjectured that 5γ(G) < 8ir(G) for any cactus graph. In this article we show that if G is a block-cactus graph having π(G) induced cycles of length 2 (mod 4), then γ(G)(5π(G) + 4) ≤ ir(G)(8π(G) + 6). This result implies the inequality 5γ(G) < 8ir(G) for a block-cactus graph G, thus proving the above conjecture. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 139–149, 1998 相似文献
8.
9.
Gašper Mekiš 《Discrete Mathematics》2010,310(23):3310-3317
A sharp lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: . Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: γ(G×H)≥γ(G)+γ(H)−1. Infinite families of graphs that attain the bound are presented. For these graphs it also holds that γt(G×H)=γ(G)+γ(H)−1. Some additional parallels with the total domination number are made. 相似文献
10.
11.
An edge colouring of a graph G is called acyclic if it is proper and every cycle contains at least three colours. We show that for every , there exists a such that if G has maximum degree Δ and girth at least g then G admits an acyclic edge colouring with colours. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 511–533, 2017 相似文献
12.
A set of vertices in a graph is an independent dominating set of if is an independent set and every vertex not in is adjacent to a vertex in . The independent domination number, , of is the minimum cardinality of an independent dominating set. In this paper, we extend the work of Henning, Löwenstein, and Rautenbach (2014) who proved that if is a bipartite, cubic graph of order and of girth at least , then . We show that the bipartite condition can be relaxed, and prove that if is a cubic graph of order and of girth at least , then . 相似文献
13.
Let G be a simple graph. A subset S V is a dominating set of G, if for any vertex v V – S there exists a vertex u S such that uv E(G). The domination number, denoted by (G), is the minimum cardinality of a dominating set. In this paper we prove that if G is a 4-regular graph with order n, then (G) 4/11 n 相似文献
14.
Vladimir Samodivkin 《Mathematica Slovaca》2007,57(5):401-406
The k-restricted domination number of a graph G is the minimum number d
k
such that for any subset U of k vertices of G, there is a dominating set in G including U and having at most d
k
vertices. Some new upper bounds in terms of order and degrees for this number are found.
相似文献
15.
16.
《Discrete Mathematics》2022,345(4):112784
A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, every vertex in S is adjacent to some other vertex in S, then S is a total dominating set. The domination number of G is the minimum cardinality of a dominating set in G, while the total domination number of G is the minimum cardinality of total dominating set in G. A claw-free graph is a graph that does not contain as an induced subgraph. Let G be a connected, claw-free, cubic graph of order n. We show that if we exclude two graphs, then , and this bound is best possible. In order to prove this result, we prove that if we exclude four graphs, then , and this bound is best possible. These bounds improve previously best known results due to Favaron and Henning (2008) [7], Southey and Henning (2010) [19]. 相似文献
17.
18.
19.
Changping Wang 《Discrete Applied Mathematics》2007,155(11):1497-1505
Let G be a graph with vertex set V(G) and edge set E(G). A function f:E(G)→{-1,1} is said to be a signed star dominating function of G if for every v∈V(G), where EG(v)={uv∈E(G)|u∈V(G)}. The minimum of the values of , taken over all signed star dominating functions f on G, is called the signed star domination number of G and is denoted by γSS(G). In this paper, a sharp upper bound of γSS(G×H) is presented. 相似文献
20.
The closed neighborhood NG[e] of an edge e in a graph G is the set consisting of e and of all edges having an end-vertex in common with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If
for each e ∈ E(G), then f is called a signed edge dominating function of G. The signed edge domination number γs′(G) of G is defined as
. Recently, Xu proved that γs′(G) ≥ |V(G)| − |E(G)| for all graphs G without isolated vertices. In this paper we first characterize all simple connected graphs G for which γs′(G) = |V(G)| − |E(G)|. This answers Problem 4.2 of [4]. Then we classify all simple connected graphs G with precisely k cycles and γs′(G) = 1 − k, 2 − k.
A. Khodkar: Research supported by a Faculty Research Grant, University of West Georgia.
Send offprint requests to: Abdollah Khodkar. 相似文献