共查询到20条相似文献,搜索用时 46 毫秒
1.
A dominating set D ⊆ V(G) is a weakly connected dominating set in G if the subgraph G[D]
w
= (N
G
[D], E
w
) weakly induced by D is connected, where E
w
is the set of all edges having at least one vertex in D. Weakly connected domination number
γw
(G) of a graph G is the minimum cardinality among all weakly connected dominating sets in G. A graph G is said to be weakly connected domination stable or just
γw
-stable if
γw
(G) =
γ w
(G + e) for every edge e belonging to the complement Ḡ of G. We provide a constructive characterization of weakly connected domination stable trees.
相似文献
2.
Let G=(V,E) be a graph without an isolated vertex. A set DV(G) is a total dominating set if D is dominating, and the induced subgraph G[D] does not contain an isolated vertex. The total domination number of G is the minimum cardinality of a total dominating set of G. A set DV(G) is a total outer-connected dominating set if D is total dominating, and the induced subgraph G[V(G)−D] is a connected graph. The total outer-connected domination number of G is the minimum cardinality of a total outer-connected dominating set of G. We characterize trees with equal total domination and total outer-connected domination numbers. We give a lower bound for the total outer-connected domination number of trees and we characterize the extremal trees. 相似文献
3.
Let G=(V,E) be a connected graph. A dominating set S of G is a weakly connected dominating set of G if the subgraph (V,E∩(S×V)) of G with vertex set V that consists of all edges of G incident with at least one vertex of S is connected. The minimum cardinality of a weakly connected dominating set of G is the weakly connected domination number, denoted . A set S of vertices in 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 γt(G) of G. In this paper, we show that . Properties of connected graphs that achieve equality in these bounds are presented. We characterize bipartite graphs as well as the family of graphs of large girth that achieve equality in the lower bound, and we characterize the trees achieving equality in the upper bound. The number of edges in a maximum matching of G is called the matching number of G, denoted α′(G). We also establish that , and show that for every tree T. 相似文献
4.
A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ
t
(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number
is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that for every simple
connected graph G of order n ≥ 3,
where d
2(v) is the number of vertices of G at distance 2 from v.
R. Khoeilar: Research supported by the Research Office of Azarbaijan University of Tarbiat Moallem. 相似文献
5.
A set S of vertices of a connected graph G is a doubly connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraphs induced by S and V−S are connected. The doubly connected domination numberγcc(G) is the minimum size of such a set. We prove that when G and are both connected of order n, and we describe the two infinite families of extremal graphs achieving the bound. 相似文献
6.
A set S of vertices in a graph G = (V, E) without isolated vertices is a total outer-connected dominating set (TCDS) of G if S is a total dominating set of G and G[V − S] is connected. The total outer-connected domination number of G, denoted by γ
tc
(G), is the minimum cardinality of a TCDS of G. For an arbitrary graph without isolated vertices, we obtain the upper and lower bounds on γ
tc
(G) + γ
tc
($
\bar G
$
\bar G
), and characterize the extremal graphs achieving these bounds. 相似文献
7.
A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number sdγ(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Haynes et al. (Discussiones Mathematicae Graph
Theory 21 (2001) 239-253) conjectured that for any graph G with . In this note we first give a counterexample to this conjecture in general and then we prove it for a particular class of
graphs. 相似文献
8.
Marcin KRZYWKOWSKI 《数学年刊B辑(英文版)》2012,33(1):113-126
A vertex of a graph is said to dominate itself and all of its neighbors.A double dominating set of a graph G is a set D of vertices of G,such that every vertex of G is dominated by at least two vertices of D.The double domination number of a graph G is the minimum cardinality of a double dominating set of G.For a graph G =(V,E),a subset D V(G) is a 2-dominating set if every vertex of V(G) \ D has at least two neighbors in D,while it is a 2-outer-independent dominating set of G if additionally the set V(G)\D is independent.The 2-outer-independent domination number of G is the minimum cardinality of a 2-outer-independent dominating set of G.This paper characterizes all trees with the double domination number equal to the 2-outer-independent domination number plus one. 相似文献
9.
H. Karami S. M. Sheikholeslami Abdollah Khodkar 《Czechoslovak Mathematical Journal》2008,58(3):595-603
The open neighborhood N
G
(e) of an edge e in a graph G is the set consisting of all edges having a common end-vertex 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 total dominating function of G. The minimum of the values , taken over all signed edge total dominating function f of G, is called the signed edge total domination number of G and is denoted by γ
st
′(G). Obviously, γ
st
′(G) is defined only for graphs G which have no connected components isomorphic to K
2. In this paper we present some lower bounds for γ
st
′(G). In particular, we prove that γ
st
′(T) ⩾ 2 − m/3 for every tree T of size m ⩾ 2. We also classify all trees T with γ
st
′(T).
Research supported by a Faculty Research Grant, University of West Georgia. 相似文献
10.
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. 相似文献
11.
A lower bound on the total signed domination numbers of graphs 总被引:4,自引:0,他引:4
Xin-zhong LU Department of Mathematics Zhejiang Normal University Jinhua China 《中国科学A辑(英文版)》2007,50(8):1157-1162
Let G be a finite connected simple graph with a vertex set V(G)and an edge set E(G). A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1}.The weight of f is W(f)=∑_(x∈V)(G)∪E(G))f(X).For an element x∈V(G)∪E(G),we define f[x]=∑_(y∈NT[x])f(y).A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1} such that f[x]≥1 for all x∈V(G)∪E(G).The total signed domination numberγ_s~*(G)of G is the minimum weight of a total signed domination function on G. In this paper,we obtain some lower bounds for the total signed domination number of a graph G and compute the exact values ofγ_s~*(G)when G is C_n and P_n. 相似文献
12.
Peter Dankelmann Johannes H. Hattingh Michael A. Henning Henda C. Swart 《Journal of Global Optimization》2006,34(4):597-607
Let G = (V,E) be a graph and let S V. The set S is a packing in G if the vertices of S are pairwise at distance at least three apart in G. The set S is a dominating set (DS) if every vertex in V − S is adjacent to a vertex in S. Further, if every vertex in V − S is also adjacent to a vertex in V − S, then S is a restrained dominating set (RDS). The domination number of G, denoted by γ(G), is the minimum cardinality of a DS of G, while the restrained domination number of G, denoted by γr(G), is the minimum cardinality of a RDS of G. The graph G is γ-excellent if every vertex of G belongs to some minimum DS of G. A constructive characterization of trees with equal domination and restrained domination numbers is presented. As a consequence
of this characterization we show that the following statements are equivalent: (i) T is a tree with γ(T)=γr(T); (ii) T is a γ-excellent tree and T ≠ K2; and (iii) T is a tree that has a unique maximum packing and this set is a dominating set of T. We show that if T is a tree of order n with ℓ leaves, then γr(T) ≤ (n + ℓ + 1)/2, and we characterize those trees achieving equality. 相似文献
13.
Sanming Zhou 《Czechoslovak Mathematical Journal》2000,50(2):321-330
Let f be an integer-valued function defined on the vertex set V(G) of a graph G. A subset D of V(G) is an f-dominating set if each vertex x outside D is adjacent to at least f(x) vertices in D. The minimum number of vertices in an f-dominating set is defined to be the f-domination number, denoted by
f
(G). In a similar way one can define the connected and total f-domination numbers
c,f
(G) and
t,f
(G). If f(x) = 1 for all vertices x, then these are the ordinary domination number, connected domination number and total domination number of G, respectively. In this paper we prove some inequalities involving
f
(G),
c,f
(G),
t,f
(G) and the independence domination number i(G). In particular, several known results are generalized. 相似文献
14.
Ladislav Nebeský 《Czechoslovak Mathematical Journal》2006,56(2):317-338
If G is a connected graph of order n ⩾ 1, then by a hamiltonian coloring of G we mean a mapping c of V (G) into the set of all positive integers such that |c(x) − c(y)| ⩾ n − 1 − D
G
(x, y) (where D
G
(x, y) denotes the length of a longest x − y path in G) for all distinct x, y ∈ V (G). Let G be a connected graph. By the hamiltonian chromatic number of G we mean
, where the minimum is taken over all hamiltonian colorings c of G.
The main result of this paper can be formulated as follows: Let G be a connected graph of order n ⩾ 3. Assume that there exists a subgraph F of G such that F is a hamiltonian-connected graph of order i, where 2 ⩽ i ⩽ 1/2 (n+1). Then hc(G) ⩽ (n−2)2+1−2(i−1)(i−2). 相似文献
15.
Let G = (V, E) be a simple graph. A subset S ⊆ V is a dominating set of G, if for any vertex u ∈ V-S, there exists a vertex v ∈ S such that uv ∈ E. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. In this paper we will prove that if G is a 5-regular graph, then γ(G) ⩽ 5/14n. 相似文献
16.
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. 相似文献
17.
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. 相似文献
18.
A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G. The connected domatic number of G is the maximum number of pairwise disjoint, connected dominating sets in V(G). We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic number 3. 相似文献
19.
Let G=(V(G),E(G)) be a graph. A function f:E(G)→{+1,−1} is called the signed edge domination function (SEDF) of G if ∑e′N[e]f(e′)≥1 for every eE(G). The signed edge domination number of G is defined as is a SEDF of G}. Xu [Baogen Xu, Two classes of edge domination in graphs, Discrete Applied Mathematics 154 (2006) 1541–1546] researched on the edge domination in graphs and proved that for any graph G of order n(n≥4). In the article, he conjectured that: For any 2-connected graph G of order n(n≥2), . In this note, we present some counterexamples to the above conjecture and prove that there exists a family of k-connected graphs Gm,k with . 相似文献
20.
On total restrained domination in graphs 总被引:2,自引:0,他引:2
In this paper we initiate the study of total restrained domination in graphs. Let G = (V,E) be a graph. A total restrained dominating set is a set S
V where every vertex in V - S is adjacent to a vertex in S as well as to another vertex in V - S, and every vertex in S is adjacent to another vertex in S. The total restrained domination number of G, denoted by
r
t
(G), is the smallest cardinality of a total restrained dominating set of G. First, some exact values and sharp bounds for
r
t
(G) are given in Section 2. Then the Nordhaus-Gaddum-type results for total restrained domination number are established in Section 3. Finally, we show that the decision problem for
r
t
(G) is NP-complete even for bipartite and chordal graphs in Section 4.This work was supported by National Natural Sciences Foundation of China (19871036). 相似文献