共查询到20条相似文献,搜索用时 78 毫秒
1.
An edge of a 5-connected graph is said to be 5-contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no 5-contractible edge is said to be contraction-critically 5-connected. Let V(G) and V5(G) denote the vertex set of a graph G and the set of degree 5 vertices of G, respectively. We prove that each contraction-critically 5-connected graph G has at least |V(G)|/2 vertices of degree 5. We also show that there is a sequence of contraction-critically 5-connected graphs {Gi} such that limi→∞|V5(Gi)|/|V(Gi)|=1/2. 相似文献
2.
Michael B. Dillencourt 《Journal of Graph Theory》1994,18(1):103-107
The toughness indexτ(G) of a graph G is defined to be the largest integer t such that for any S ? V(G) with |S| > t, c(G - S) < |S| - t, where c(G - S) denotes the number of components of G - S. In particular, 1-tough graphs are exactly those graphs for which τ(G) ≥ 0. In this paper, it is shown that if G is a planar graph, then τ(G) ≥ 2 if and only if G is 4-connected. This result suggests that there may be a polynomial-time algorithm for determining whether a planar graph is 1-tough, even though the problem for general graphs is NP-hard. The result can be restated as follows: a planar graph is 4-connected if and only if it remains 1-tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4-connected planar graph yields a Hamiltonian graph. 相似文献
3.
Mekkia Kouider 《Combinatorica》2000,20(2):219-226
G =(V,E) is a 2-connected graph, and X is a set of vertices of G such that for every pair x,x' in X, , and the minimum degree of the induced graph <X> is at least 3, then X is covered by one cycle.
This result will be in fact generalised by considering tuples instead of pairs of vertices.
Let be the minimum degree in the induced graph <X>. For any ,
.
If , and , then X is covered by at most (p-1) cycles of G. If furthermore , (p-1) cycles are sufficient.
So we deduce the following:
Let p and t () be two integers.
Let G be a 2-connected graph of order n, of minimum degree at least t. If , and , then V is covered by at most cycles, where k is the connectivity of G.
If furthermore , (p-1) cycles are sufficient.
In particular, if and , then G is hamiltonian.
Received April 3, 1998 相似文献
4.
We prove the following theorem: For a connected noncomplete graph G, let τ(G): = min{dG(u) + dG(v)|dG(u, v) = 2}. Suppose G is a 3-connected noncomplete graph. Then through each edge of G there passes a cycle of length ≥ min{|V(G)|, τ (G) − 1}. © 1997 John Wiley & Sons, Inc. 相似文献
5.
WANGWEIFAN ZHANGKEMIN 《高校应用数学学报(英文版)》1997,12(4):455-462
A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g. 相似文献
6.
H. J. Broersma J. Den Van Heuvel H. A. Jung H. J. Veldman 《Journal of Graph Theory》1993,17(3):373-385
For a graph G and an integer k, denote by Vk the set {v ∈ V(G) | d(v) ≥ k}. Veldman proved that if G is a 2-connected graph of order n with n ≤ 3k - 2 and |Vk| ≤ k, then G has a cycle containing all vertices of Vk. It is shown that the upper bound k on |Vk| is close to best possible in general. For the special case k = δ(G), it is conjectured that the condition |Vk| ≤ k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n ≤ 2δ(G) + δ(G) + 1. This result is an almost-generalization of Jackson's Theorem that every 2-connected k-regular graph of order n with n ≤ 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented. © 1993 John Wiley & Sons, Inc. 相似文献
7.
Kazuhide Hirohata 《Journal of Graph Theory》1998,29(3):177-184
For a graph G and an integer k ≥ 1, let ςk(G) = dG(vi): {v1, …, vk} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς2(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998 相似文献
8.
David Barnette 《Israel Journal of Mathematics》1973,14(1):1-13
In this paper, we introduce three operations on planar graphs that we call face splitting, double face splitting, and subdivision
of hexagons. We show that the duals of the planar 4-connected graphs can be generated from the graph of the cube by these
three operations. That is, given any graphG that is the dual of a planar 4-connected graph, there is a sequence of duals of planar 4-connected graphsG
0,G
1, …,G
n such thatG
0 is the graph of the cube,G
n=G, and each graph is obtained from its predecessor by one of our three operations.
Research supported by a Sloan Foundation fellowship and by NSF Grant#GP-27963. 相似文献
9.
Closed Separator Sets 总被引:1,自引:0,他引:1
Matthias Kriesell 《Combinatorica》2005,25(5):575-598
A smallest separator in a finite, simple, undirected graph G is a set S ⊆ V (G) such that G–S is disconnected and |S|=κ(G), where κ(G) denotes the connectivity of G.
A set S of smallest separators in G is defined to be closed if for every pair S,T ∈ S, every component C of G–S, and every component S of G–T intersecting C either X(C,D) := (V (C) ∩ T) ∪ (T ∩ S) ∪ (S ∩ V (D)) is in S or |X(C,D)| > κ(G). This leads, canonically, to a closure system on the (closed) set of all smallest separators of G.
A graph H with
is defined to be S-augmenting if no member of S is a smallest separator in G ∪ H:=(V (G) ∪ V (H), E(G) ∪ E(H)). It is proved that if S is closed then every minimally S-augmenting graph is a forest, which generalizes a result of Jordán.
Several applications are included, among them a generalization of a Theorem of Mader on disjoint fragments in critically k-connected graphs, a Theorem of Su on highly critically k-connected graphs, and an affirmative answer to a conjecture of Su on disjoint fragments in contraction critically k-connected graphs of maximal minimum degree. 相似文献
10.
Kewen Zhao 《Monatshefte für Mathematik》2009,20(1):279-293
Let G be a simple graph with n vertices. For any v ? V(G){v \in V(G)} , let N(v)={u ? V(G): uv ? E(G)}{N(v)=\{u \in V(G): uv \in E(G)\}} , NC(G) = min{|N(u) èN(v)|: u, v ? V(G){NC(G)= \min \{|N(u) \cup N(v)|: u, v \in V(G)} and
uv \not ? E(G)}{uv \not \in E(G)\}} , and NC2(G) = min{|N(u) èN(v)|: u, v ? V(G){NC_2(G)= \min\{|N(u) \cup N(v)|: u, v \in V(G)} and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any u, v ? V(G){u, v \in V(G)} , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC
2(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC
2(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC
2(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected. 相似文献
11.
Let G be a graph and S ⊂ V(G). We denote by α(S) the maximum number of pairwise nonadjacent vertices in S. For x, y ∈ V(G), the local connectivity κ(x, y) is defined to be the maximum number of internally-disjoint paths connecting x and y in G. We define . In this paper, we show that if κ(S) ≥ 3 and for every independent set {x
1, x
2, x
3, x
4} ⊂ S, then G contains a cycle passing through S. This degree condition is sharp and this gives a new degree sum condition for a 3-connected graph to be hamiltonian. 相似文献
12.
For a finite poset P = (V, ≤ ), let _s(P){\cal B}_s(P) consist of all triples (x,y,z) ∈ V
3 such that either x < y < z or z < y < x. Similarly, for every finite, simple, and undirected graph G = (V,E), let Bs(G){\cal B}_s(G) consist of all triples (x,y,z) ∈ V
3 such that y is an internal vertex on an induced path in G between x and z. The ternary relations Bs(P){\cal B}_s(P) and Bs(G){\cal B}_s(G) are well-known examples of so-called strict betweennesses. We characterize the pairs (P,G) of posets P and graphs G on the same ground set V which induce the same strict betweenness relation Bs(P)=Bs(G){\cal B}_s(P)={\cal B}_s(G). 相似文献
13.
Let K be a cardinal. If K χ0, define K := K . Otherwise, let K := K + 1. We prove a conjecture of Mader: Every infinite K -connected graph G = (V, E) contains a set S ? V with |S| = |V| such that G/S is K -connected for all S? S. 相似文献
14.
In 1990 G. T. Chen proved that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x) + d(y) ≥ 2n − 1 for each pair of nonadjacent vertices x, y ∈ V (G), then G is Hamiltonian. In this paper we prove that if G is a 2-connected graph of order n and 2|N(x) ∪ N(y)| + d(x)+d(y) ≥ 2n−1 for each pair of nonadjacent vertices x, y ∈ V (G) such that d(x, y) = 2, then G is Hamiltonian. 相似文献
15.
Sparse connectivity certificates via MA orderings in graphs 总被引:1,自引:0,他引:1
Hiroshi Nagamochi 《Discrete Applied Mathematics》2006,154(16):2411-2417
For an undirected multigraph G=(V,E), let α be a positive integer weight function on V. For a positive integer k, G is called (k,α)-connected if any two vertices u,v∈V remain connected after removal of any pair (Z,E′) of a vertex subset Z⊆V-{u,v} and an edge subset E′⊆E such that ∑v∈Zα(v)+|E′|<k. The (k,α)-connectivity is an extension of several common generalizations of edge-connectivity and vertex-connectivity. Given a (k,α)-connected graph G, we show that a (k,α)-connected spanning subgraph of G with O(k|V|) edges can be found in linear time by using MA orderings. We also show that properties on removal cycles and preservation of minimum cuts can be extended in the (k,α)-connectivity. 相似文献
16.
A graph G is (2, 1)-colorable if its vertices can be partitioned into subsets V
1 and V
2 such that each component in G[V
1] contains at most two vertices while G[V
2] is edgeless. We prove that every graph with maximum average degree mad(G) < 7/3 is (2, 1)-colorable. It follows that every planar graph with girth at least 14 is (2, 1)-colorable. We also construct
a planar graph G
n
with mad (G
n
) = (18n − 2)/(7n − 1) that is not (2, 1)-colorable. 相似文献
17.
Július Czap 《Discrete Mathematics》2011,311(21):2570
A proper vertex coloring of a 2-connected plane graph G is a parity vertex coloring if for each face f and each color c, the total number of vertices of color c incident with f is odd or zero. The minimum number of colors used in such a coloring of G is denoted by χp(G).In this paper we prove that χp(G)≤12 for every 2-connected outerplane graph G. We show that there is a 2-connected outerplane graph G such that χp(G)=10. If a 2-connected outerplane graph G is bipartite, then χp(G)≤8, moreover, this bound is best possible. 相似文献
18.
Hong Wang 《Journal of Graph Theory》1999,31(2):101-106
In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V1, V2, E) is a bipartite graph with |V1| = |V2| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V1, V2; E) is a bipartite graph such that |V1| = |V2| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U1, U2; F) with |U1| ≤ n, |U2| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999 相似文献
19.
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
sdgt(G){{\rm sd}_{\gamma_t}(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 total domination number. In this paper, we prove that sdgt(G) £ 2gt(G)-1{{\rm sd}_{\gamma_t}(G)\leq 2\gamma_t(G)-1} for every simple connected graph G of order n ≥ 3. 相似文献
20.
Mark Pankov 《Journal of Algebraic Combinatorics》2011,33(4):555-570
Let V be an n-dimensional vector space (4≤n<∞) and let Gk(V){\mathcal{G}}_{k}(V) be the Grassmannian formed by all k-dimensional subspaces of V. The corresponding Grassmann graph will be denoted by Γ
k
(V). We describe all isometric embeddings of Johnson graphs J(l,m), 1<m<l−1 in Γ
k
(V), 1<k<n−1 (Theorem 4). As a consequence, we get the following: the image of every isometric embedding of J(n,k) in Γ
k
(V) is an apartment of Gk(V){\mathcal{G}}_{k}(V) if and only if n=2k. Our second result (Theorem 5) is a classification of rigid isometric embeddings of Johnson graphs in Γ
k
(V), 1<k<n−1. 相似文献