共查询到20条相似文献,搜索用时 0 毫秒
1.
Yang Yuansheng Zhao Chengye Lin Xiaohui Jiang Yongsong Hao Xin 《Journal of Graph Theory》2005,50(4):316-320
Let γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k?1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k?1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc. 相似文献
2.
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. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γt(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γt(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γt(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009 相似文献
3.
An m‐covering of a graph G is a spanning subgraph of G with maximum degree at most m. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus k ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most 6k ? 12 vertices of degree 7. We also construct, for every surface F2 with Euler genus k ≥ 2, a 3‐connected graph G on F2 with arbitrarily large representativity each of whose 2‐connected 7‐coverings contains at least 6k ? 12 vertices of degree 7. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 26–36, 2003 相似文献
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.
It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σx∈V(H) degG(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999 相似文献
6.
In this article, we apply a cutting theorem of Thomassen to show that there is a function f: N → N such that if G is a 3‐connected graph on n vertices which can be embedded in the orientable surface of genus g with face‐width at least f(g), then G contains a cycle of length at least cn, where c is a constant not dependent on g. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 69–84, 2002 相似文献
7.
Hong‐Jian Lai 《Journal of Graph Theory》2003,42(3):211-219
Let G be a graph. For each vertex v ∈V(G), Nv denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), Nv is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003 相似文献
8.
A well‐known result of Tutte states that a 3‐connected graph G is planar if and only if every edge of G is contained in exactly two induced non‐separating circuits. Bixby and Cunningham generalized Tutte's result to binary matroids. We generalize both of these results and give new characterizations of both 3‐connected planar graphs and 3‐connected graphic matroids. Our main result determines when a natural necessary condition for a binary matroid to be graphic is also sufficient. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 165–174, 2010 相似文献
9.
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. 相似文献
10.
称一个没有孤立点的图G 为临界全控制图, 如果G 满足对于任何一个不与悬挂点相邻的顶点v, G - v 的全控制数都小于G 的全控制数. 如果G 的全控制数记为γt, 则称这样的临界全控制图G 为γt- 临界的. 如果G 是γt- 临界的, 且阶数为n, 则n ≤ Δ(G)(γt(G)- 1) + 1, 其中Δ(G) 是G 的最大度. 本文将证明对γt = 3, 这个阶数的上界是紧的, 并给出所有满足n = Δ(G)(γt(G)- 1) + 1 的3-γt- 临界图. 相似文献
11.
Joanna Cyman Magdalena Lemańska Joanna Raczek 《Central European Journal of Mathematics》2006,4(1):34-45
For a given connected graph G = (V, E), a set
is a doubly connected dominating set if it is dominating and both 〈D〉 and 〈V (G)-D〉 are connected. The cardinality of the minimum doubly connected dominating set in G is the doubly connected domination number. We investigate several properties of doubly connected dominating sets and give some bounds on the doubly connected domination
number. 相似文献
12.
Ioan Tomescu 《Journal of Graph Theory》2003,43(3):210-222
In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if ci(G) ≤ ci(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where ci(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003 相似文献
13.
Su Jianji 《Journal of Graph Theory》2004,45(4):281-297
Mader conjectured that every k‐critical n‐connected noncomplete graph G has 2k + 2 pairwise disjoint fragments. The author in 9 proved that the conjecture holds if the order of G is greater than (k + 2)n. Now we settle this conjecture completely. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 281–297, 2004 相似文献
14.
For a graph G, let p(G) denote the order of a longest path in G and c(G) the order of a longest cycle in G, respectively. We show that if G is a 3‐connected graph of order n such that for every independent set {x1, x2, x3, x4}, then G satisfies c(G) ≥ p(G) ? 1. Using this result, we give several lower bounds to the circumference of a 3‐connected graph. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 137–156, 2001 相似文献
15.
A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G. The minimum number of vertices in a connected dominating set of G is called the connected domination number of G, and is denoted by γ
c
(G). Let G be a spanning subgraph of K
s,s
and let H be the complement of G relative to K
s,s
; that is, K
s,s
= G ⊕ H is a factorization of K
s,s
. The graph G is k-γ
c
-critical relative to K
s,s
if γ
c
(G) = k and γ
c
(G + e) < k for each edge e ∈ E(H). First, we discuss some classes of graphs whether they are γ
c
-critical relative to K
s,s
. Then we study k-γ
c
-critical graphs relative to K
s,s
for small values of k. In particular, we characterize the 3-γ
c
-critical and 4-γ
c
-critical graphs. 相似文献
16.
A graph is called γ-critical if the removal of any vertex from the graph decreases the domination number, while a graph with no isolated vertex is γt-critical if the removal of any vertex that is not adjacent to a vertex of degree 1 decreases the total domination number. A γt-critical graph that has total domination number k, is called k-γt-critical. In this paper, we introduce a class of k-γt-critical graphs of high connectivity for each integer k≥3. In particular, we provide a partial answer to the question “Which graphs are γ-critical and γt-critical or one but not the other?” posed in a recent work [W. Goddard, T.W. Haynes, M.A. Henning, L.C. van der Merwe, The diameter of total domination vertex critical graphs, Discrete Math. 286 (2004) 255-261]. 相似文献
17.
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. 相似文献
18.
19.
It is shown that every sufficiently large almost‐5‐connected non‐planar graph contains a minor isomorphic to an arbitrarily large graph from one of six families of graphs. The graphs in these families are also almost‐5‐connected, by which we mean that they are 4‐connected and all 4‐separations contain a “small” side. As a corollary, every sufficiently large almost‐5‐connected non‐planar graph contains both a K3, 4‐minor and a ‐minor. The connectivity condition cannot be reduced to 4‐connectivity, as there are known infinite families of 4‐connected non‐planar graphs that do not contain a K3, 4‐minor. Similarly, there are known infinite families of 4‐connected non‐planar graphs that do not contain a ‐minor. 相似文献
20.
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.
相似文献