共查询到20条相似文献,搜索用时 31 毫秒
1.
Tao Wang 《Discrete Mathematics》2009,309(5):1079-1083
A vertex subset S of a graph G is a dominating set if every vertex of G either belongs to S or is adjacent to a vertex of S. The cardinality of a smallest dominating set is called the dominating number of G and is denoted by γ(G). A graph G is said to be γ-vertex-critical if γ(G−v)<γ(G), for every vertex v in G.Let G be a 2-connected K1,5-free 3-vertex-critical graph of odd order. For any vertex v∈V(G), we show that G−v has a perfect matching (except two graphs), which solves a conjecture posed by Ananchuen and Plummer [N. Ananchuen, M.D. Plummer, Matchings in 3-vertex critical graphs: The odd case, Discrete Math., 307 (2007) 1651-1658]. 相似文献
2.
A vertex subset S of a graph G = (V,E) is a total dominating set if every vertex of G is adjacent to some vertex in S. The total domination number of G, denoted by γ t (G), is the minimum cardinality of a total dominating set of G. A graph G with no isolated vertex is said to be total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ t (G?v) < γ t (G). A total domination vertex critical graph G is called k-γ t -critical if γ t (G) = k. In this paper we first show that every 3-γ t -critical graph G of even order has a perfect matching if it is K 1,5-free. Secondly, we show that every 3-γ t -critical graph G of odd order is factor-critical if it is K 1,5-free. Finally, we show that G has a perfect matching if G is a K 1,4-free 4-γ t (G)-critical graph of even order and G is factor-critical if G is a K 1,4-free 4-γ t (G)-critical graph of odd order. 相似文献
3.
A graph G is said to be k-γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k-1 vertices. The structure of k-γ-critical graphs remains far from completely understood when k?3.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G) and is bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G). More generally, a graph is said to be k-factor-critical if G-S has a perfect matching for every set S of k vertices in G. In three previous papers [N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs, Discrete Math. 272 (2003) 5-15; N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs. II. Utilitas Math. 70 (2006) 11-32], we explored the toughness of 3-γ-critical graphs and some of their matching properties. In particular, we obtained some properties which are sufficient for a 3-γ-critical graph to be factor-critical and, respectively, bicritical. In the present work, we obtain similar results for k-factor-critical graphs when k=3. 相似文献
4.
A dominating set of vertices S of a graph G is connected if the subgraph G[S] is connected. Let γc(G) denote the size of any smallest connected dominating set in G. A graph G is k-γ-connected-critical if γc(G)=k, but if any edge is added to G, then γc(G+e)?k-1. This is a variation on the earlier concept of criticality of edge addition with respect to ordinary domination where a graph G was defined to be k-critical if the domination number of G is k, but if any edge is added to G, the domination number falls to k-1.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G), bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G) or, more generally, k-factor-critical if, for every set S⊆V(G) with |S|=k, the graph G-S contains a perfect matching. In two previous papers [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].] on ordinary (i.e., not necessarily connected) domination, the first and third authors showed that under certain assumptions regarding connectivity and minimum degree, a critical graph G with (ordinary) domination number 3 will be factor-critical (if |V(G)| is odd), bicritical (if |V(G)| is even) or 3-factor-critical (again if |V(G)| is odd). Analogous theorems for connected domination are presented here. Although domination and connected domination are similar in some ways, we will point out some interesting differences between our new results for the case of connected domination and the results in [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].]. 相似文献
5.
A connected graph G is said to be a factor-critical graph if G ?v has a perfect matching for every vertex v of G. In this paper, the 2-connected factor-critical graph G which has exactly |E(G)| + 1 maximum matchings is characterized. 相似文献
6.
The k-Dominating Graph 总被引:1,自引:0,他引:1
Given a graph G, the k-dominating graph of G, D k (G), is defined to be the graph whose vertices correspond to the dominating sets of G that have cardinality at most k. Two vertices in D k (G) are adjacent if and only if the corresponding dominating sets of G differ by either adding or deleting a single vertex. The graph D k (G) aids in studying the reconfiguration problem for dominating sets. In particular, one dominating set can be reconfigured to another by a sequence of single vertex additions and deletions, such that the intermediate set of vertices at each step is a dominating set if and only if they are in the same connected component of D k (G). In this paper we give conditions that ensure D k (G) is connected. 相似文献
7.
Sambhu Charan Barman Sukumar Mondal Madhumangal Pal 《Journal of Applied Mathematics and Computing》2013,43(1-2):133-150
For a fixed positive integer k, a k-tuple dominating set of a graph G=(V,E) is a subset D?V such that every vertex in V is dominated by at least k vertex in D. The k-tuple domination number γ ×k (G) is the minimum size of a k-tuple dominating set of G. The special case when k=1 is the usual domination. The case when k=2 was called double domination or 2-tuple domination. A 2-tuple dominating set D 2 is said to be minimal if there does not exist any D′?D 2 such that D′ is a 2-tuple dominating set of G. A 2-tuple dominating set D 2, denoted by γ ×2(G), is said to be minimum, if it is minimal as well as it gives 2-tuple domination number. In this paper, we present an efficient algorithm to find a minimum 2-tuple dominating set on permutation graphs with n vertices which runs in O(n 2) time. 相似文献
8.
Adriana Hansberg 《Discrete Mathematics》2008,308(11):2277-2281
Let G be a simple graph, and let p be a positive integer. A subset D⊆V(G) is a p-dominating set of the graph G, if every vertex v∈V(G)-D is adjacent to at least p vertices in D. The p-domination numberγp(G) is the minimum cardinality among the p-dominating sets of G. Note that the 1-domination number γ1(G) is the usual domination numberγ(G). This definition immediately leads to the inequality γ(G)?γ2(G).In this paper we present some sufficient as well as some necessary conditions for graphs G with the property that γ2(G)=γ(G). In particular, we characterize all cactus graphs H with γ2(H)=γ(H). 相似文献
9.
Odile Favaron 《Journal of Combinatorial Theory, Series B》1985,39(1):101-102
A set D of vertices of a graph is k-dependent if every vertex of D is joined to at most k?1 vertices in D. Let βk(G) be the maximum order of a k-dependent set in G. A set D of vertices of G is k-dominating if every vertex not in D is joined to at least k vertices of D. Let γk(G) be the minimum order of a k-dominating set in G. Here we prove the following conjecture of Fink and Jacobson: for any simple graph G and any positive integer k, γk(G) ≤ βk(G). 相似文献
10.
《Quaestiones Mathematicae》2013,36(2):237-257
AbstractIf n is an integer, n ≥ 2 and u and v are vertices of a graph G, then u and v are said to be Kn-adjacent vertices of G if there is a subgraph of G, isomorphic to Kn , containing u and v. For n ≥ 2, a Kn- dominating set of G is a set D of vertices such that every vertex of G belongs to D or is Kn-adjacent to a vertex of D. The Kn-domination number γKn (G) of G is the minimum cardinality among the Kn-dominating sets of vertices of G. It is shown that, for n ε {3,4}, if G is a graph of order p with no Kn-isolated vertex, then γKn (G) ≤ p/n. We establish that this is a best possible upper bound. It is shown that the result is not true for n ≥ 5. 相似文献
11.
A dominating setD of a graph G is a subset of V(G) such that for every vertex v∈V(G), either v∈D or there exists a vertex u∈D that is adjacent to v in G. Dominating sets of small cardinality are of interest. A connected dominating setC of a graph G is a dominating set of G such that the subgraph induced by the vertices of C in G is connected. A weakly-connected dominating setW of a graph G is a dominating set of G such that the subgraph consisting of V(G) and all edges incident with vertices in W is connected. In this paper we present several algorithms for finding small connected dominating sets and small weakly-connected dominating sets of regular graphs. We analyse the average-case performance of these heuristics on random regular graphs using differential equations, thus giving upper bounds on the size of a smallest connected dominating set and the size of a smallest weakly-connected dominating set of random regular graphs. 相似文献
12.
Mostafa Blidia 《Discrete Mathematics》2008,308(10):1785-1791
We examine classes of extremal graphs for the inequality γ(G)?|V|-max{d(v)+βv(G)}, where γ(G) is the domination number of graph G, d(v) is the degree of vertex v, and βv(G) is the size of a largest matching in the subgraph of G induced by the non-neighbours of v. This inequality improves on the classical upper bound |V|-maxd(v) due to Claude Berge. We give a characterization of the bipartite graphs and of the chordal graphs that achieve equality in the inequality. The characterization implies that the extremal bipartite graphs can be recognized in polynomial time, while the corresponding problem remains NP-complete for the extremal chordal graphs. 相似文献
13.
A graphoidal cover of a graph G is a collection ψ of (not necessarily open) paths inG such that every path in ψ has at least two vertices, every vertex ofG is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. Let Ω (ψ) denote the intersection graph of ψ. A graph G is said to be graphoidal if there exists a graphH and a graphoidal cover ψof H such that G is isomorphic to Ω(ψ). In this paper we study the properties of graphoidal graphs and obtain a forbidden subgraph characterisation of bipartite graphoidal graphs. 相似文献
14.
A vertex u in an undirected graph G = (V, E) is said to dominate all its adjacent vertices and itself. A subset D of V is a dominating set in G if every vertex in G is dominated by a vertex in D, and is a minimum dominating set in G if no other dominating set in G has fewer vertices than D. The domination number of G is the cardinality of a minimum dominating set in G.The problem of determining, for a given positive integer k and an undirected graph G, whether G has a dominating set D in G satisfying ¦D¦ ≤ k, is a well-known NP-complete problem. Cockayne have presented a linear time algorithm for finding a minimum dominating set in a tree. In this paper, we will present a linear time algorithm for finding a minimum dominating set in a series-parallel graph. 相似文献
15.
Let G be a graph of order n and maximum degree Δ(G) and let γt(G) denote the minimum cardinality of a total dominating set of a graph G. A graph G with no isolated vertex is the total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G−v is less than the total domination number of G. We call these graphs γt-critical. For any γt-critical graph G, it can be shown that n≤Δ(G)(γt(G)−1)+1. In this paper, we prove that: Let G be a connected γt-critical graph of order n (n≥3), then n=Δ(G)(γt(G)−1)+1 if and only if G is regular and, for each v∈V(G), there is an A⊆V(G)−{v} such that N(v)∩A=0?, the subgraph induced by A is 1-regular, and every vertex in V(G)−A−{v} has exactly one neighbor in A. 相似文献
16.
A dominating cycle for a graph G = (V, E) is a subset C of V which has the following properties: (i) the subgraph of G induced by C has a Hamiltonian cycle, and (ii) every vertex of V is adjacent to some vertex of C. In this paper, we develop an O(n2) algorithm for finding a minimum cardinality dominating cycle in a permutation graph. We also show that a minimum cardinality dominating cycle in a permutation graph always has an even number of vertices unless it is isomorphic to C3. 相似文献
17.
Linda Eroh 《Discrete Mathematics》2008,308(18):4212-4220
Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by dG(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, dH(S)=dG(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed. 相似文献
18.
Fuji Zhang 《Discrete Mathematics》2006,306(13):1415-1423
A graph G is said to be bicritical if G-u-v has a perfect matching for every choice of a pair of points u and v. Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least 2k+2 points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an O(mn) algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G. 相似文献
19.
Michael A. Henning 《Discrete Applied Mathematics》2010,158(2):147-153
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 γt(G) of G. The graph G is total domination edge critical if for every edge e in the complement of G, γt(G+e)<γt(G). We call such graphs γtEC. Properties of γtEC graphs are established. 相似文献
20.
The graph G is a covering of the graph H if there exists a (projection) map p from the vertex set of G to the vertex set of H which induces a one-to-one correspondence between the vertices adjacent to v in G and the vertices adjacent to p(v) in H, for every vertex v of G. We show that for any two finite regular graphs G and H of the same degree, there exists a finite graph K that is simultaneously a covering both of G and H. The proof uses only Hall's theorem on 1-factors in regular bipartite graphs. 相似文献