共查询到20条相似文献,搜索用时 33 毫秒
1.
Let G be a graph and let V0 = {ν∈ V(G): dG(ν) = 6}. We show in this paper that: (i) if G is a 6‐connected line graph and if |V0| ≤ 29 or G[V0] contains at most 5 vertex disjoint K4's, then G is Hamilton‐connected; (ii) every 8‐connected claw‐free graph is Hamilton‐connected. Several related results known before are generalized. © 2005 Wiley Periodicals, Inc. J Graph Theory 相似文献
2.
Jinquan Dong 《Journal of Graph Theory》1999,30(3):235-241
A graph G is said to be Pt‐free if it does not contain an induced path on t vertices. The i‐center Ci(G) of a connected graph G is the set of vertices whose distance from any vertex in G is at most i. Denote by I(t) the set of natural numbers i, ⌊t/2⌋ ≤ i ≤ t − 2, with the property that, in every connected Pt‐free graph G, the i‐center Ci(G) of G induces a connected subgraph of G. In this article, the sharp upper bound on the diameter of G[Ci(G)] is established for every i ∈ I(t). The sharp lower bound on I(t) is obtained consequently. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 235–241, 1999 相似文献
3.
Matthias Kriesell 《Journal of Graph Theory》2001,36(1):35-51
A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K2k + 2 − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001 相似文献
4.
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 相似文献
5.
Let C be a longest cycle in the 3‐connected graph G and let H be a component of G ? V(C) such that |V(H)| ≥ 3. We supply estimates of the form |C| ≥ 2d(u) + 2d(v) ? α(4 ≤ α ≤ 8), where u,v are suitably chosen non‐adjacent vertices in G. Also the exceptional classes for α = 6,7,8 are characterized. © 2005 Wiley Periodicals, Inc. J Graph Theory 相似文献
6.
The average distance μ(G) of a graph G is the average among the distances between all pairs of vertices in G. For n ≥ 2, the average Steiner n-distance μn(G) of a connected graph G is the average Steiner distance over all sets of n vertices in G. It is shown that for a connected weighted graph G, μn(G) ≤ μk(G) + μn+1−k(G) where 2 ≤ k ≤ n − 1. The range for the average Steiner n-distance of a connected graph G in terms of n and |V(G)| is established. Moreover, for a tree T and integer k, 2 ≤ k ≤ n − 1, it is shown that μn(T) ≤ (n/k)μk(T) and the range for μn(T) in terms of n and |V(T)| is established. Two efficient algorithms for finding the average Steiner n-distance of a tree are outlined. © 1996 John Wiley & Sons, Inc. 相似文献
7.
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 相似文献
8.
Anders Yeo 《Journal of Graph Theory》2007,55(4):325-337
A total dominating set, S, in a graph, G, has the property that every vertex in G is adjacent to a vertex in S. The total dominating number, γt(G) of a graph G is the size of a minimum total dominating set in G. Let G be a graph with no component of size one or two and with Δ(G) ≥ 3. In 6 , it was shown that |E(G)| ≤ Δ(G) (|V(G)|–γt(G)) and conjectured that |E(G)| ≤ (Δ(G)+3) (|V(G)|–γt(G))/2 holds. In this article, we prove that holds and that the above conjecture is false as there for every Δ exist Δ‐regular bipartite graphs G with |E(G)| ≥ (Δ+0.1 ln(Δ)) (|V(G)|–γt(G))/2. The last result also disproves a conjecture on domination numbers from 8 . © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 325–337, 2007 相似文献
9.
Let G = (V,E) be an undirected weighted graph on |V | = n vertices and |E| = m edges. A t‐spanner of the graph G, for any t ≥ 1, is a subgraph (V,ES), ES ⊆ E, such that the distance between any pair of vertices in the subgraph is at most t times the distance between them in the graph G. Computing a t‐spanner of minimum size (number of edges) has been a widely studied and well‐motivated problem in computer science. In this paper we present the first linear time randomized algorithm that computes a t‐spanner of a given weighted graph. Moreover, the size of the t‐spanner computed essentially matches the worst case lower bound implied by a 43‐year old girth lower bound conjecture made independently by Erdős, Bollobás, and Bondy & Simonovits. Our algorithm uses a novel clustering approach that avoids any distance computation altogether. This feature is somewhat surprising since all the previously existing algorithms employ computation of some sort of local or global distance information, which involves growing either breadth first search trees up to θ(t)‐levels or full shortest path trees on a large fraction of vertices. The truly local approach of our algorithm also leads to equally simple and efficient algorithms for computing spanners in other important computational environments like distributed, parallel, and external memory. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007 相似文献
10.
For a graph G, we denote by i(G) the number of isolated vertices of G. We prove that for a connected graph G of order at least five, if i(G–S) < |S| for all ?? ≠ S ? V(G), then G has a spanning tree T such that the distance in T between any two leaves of T is at least four. This result was conjectured by Kaneko in “Spanning trees with constrains on the leaf degree”, Discrete Applied Math, 115 (2001), 73–76. Moreover, the condition in the result is sharp in a sense that the condition i(G–S) < |S| cannot be replaced by i(G–S) ≤ |S|. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 83–90, 2007 相似文献
11.
Mark V. Barovich 《Journal of Graph Theory》2000,33(2):55-65
Let G be a 2‐connected graph, let u and v be distinct vertices in V(G), and let X be a set of at most four vertices lying on a common (u, v)‐path in G. If deg(x) ≥ d for all x ∈ V(G) \ {u, v}, then there is a (u, v)‐path P in G with X ⊂ V(P) and |E(P)| ≥ d. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 55–65, 2000 相似文献
12.
For a connected graph the restricted edge‐connectivity λ′(G) is defined as the minimum cardinality of an edge‐cut over all edge‐cuts S such that there are no isolated vertices in G–S. A graph G is said to be λ′‐optimal if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree in G defined as ξ(G) = min{d(u) + d(v) ? 2:uv ∈ E(G)}, d(u) denoting the degree of a vertex u. A. Hellwig and L. Volkmann [Sufficient conditions for λ′‐optimality in graphs of diameter 2, Discrete Math 283 (2004), 113–120] gave a sufficient condition for λ′‐optimality in graphs of diameter 2. In this paper, we generalize this condition in graphs of diameter g ? 1, g being the girth of the graph, and show that a graph G with diameter at most g ? 2 is λ′‐optimal. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 73–86, 2006 相似文献
13.
Florian Pfender 《Journal of Graph Theory》2010,64(3):206-209
For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t3(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceilFor a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t3(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceil$, improving a recent result by Fox, Loh and Sudakov. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 206–209, 2010 相似文献
14.
Zhiquan Hu Feng Tian Bing Wei Yoshimi Egawa Kazuhide Hirohata 《Journal of Graph Theory》2002,39(4):265-282
For a connected noncomplete graph G, let μ(G):=min{max {dG(u), dG(v)}:dG(u, v)=2}. A well‐known theorem of Fan says that every 2‐connected noncomplete graph has a cycle of length at least min{|V(G)|, 2μ(G)}. In this paper, we prove the following Fan‐type theorem: if G is a 3‐connected noncomplete graph, then each pair of distinct vertices of G is joined by a path of length at least min{|V(G)|?1, 2μ(G)?2}. As consequences, we have: (i) if G is a 3‐connected noncomplete graph with , then G is Hamilton‐connected; (ii) if G is a (s+2)‐connected noncomplete graph, where s≥1 is an integer, then through each path of length s of G there passes a cycle of length≥min{|V(G)|, 2μ(G)?s}. Several results known before are generalized and a conjecture of Enomoto, Hirohata, and Ota is proved. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 265–282, 2002 DOI 10.1002/jgt.10028 相似文献
15.
Daniel W. Cranston Anja Pruchnewski Zsolt Tuza Margit Voigt 《Journal of Graph Theory》2012,71(1):18-30
The following question was raised by Bruce Richter. Let G be a planar, 3‐connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), 6} for all v∈V(G)? More generally, we ask for which pairs (r, k) the following question has an affirmative answer. Let r and k be the integers and let G be a K5‐minor‐free r‐connected graph that is not a Gallai tree (i.e. at least one block of G is neither a complete graph nor an odd cycle). Is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), k} for all v∈V(G)? We investigate this question by considering the components of G[Sk], where Sk: = {v∈V(G)|d(v)8k} is the set of vertices with small degree in G. We are especially interested in the minimum distance d(Sk) in G between the components of G[Sk]. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:18–30, 2012 相似文献
16.
A graph G is k‐choosable if its vertices can be colored from any lists L(ν) of colors with |L(ν)| ≥ k for all ν ∈ V(G). A graph G is said to be (k,?)‐choosable if its vertices can be colored from any lists L(ν) with |L(ν)| ≥k, for all ν∈ V(G), and with . For each 3 ≤ k ≤ ?, we construct a graph G that is (k,?)‐choosable but not (k,? + 1)‐choosable. On the other hand, it is proven that each (k,2k ? 1)‐choosable graph G is O(k · ln k · 24k)‐choosable. © 2005 Wiley Periodicals, Inc. J Graph Theory 相似文献
17.
Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{th} for all h∈V(H) where th∈V(T) depends on h; or ? maps G□{h} to {sh}□ T for all h∈V(H) where sh∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008 相似文献
18.
Let cl(G) denote Ryjá?ek's closure of a claw‐free graph G. In this article, we prove the following result. Let G be a 4‐connected claw‐free graph. Assume that G[NG(T)] is cyclically 3‐connected if T is a maximal K3 in G which is also maximal in cl(G). Then G is hamiltonian. This result is a common generalization of Kaiser et al.'s theorem [J Graph Theory 48(4) (2005), 267–276] and Pfender's theorem [J Graph Theory 49(4) (2005), 262–272]. © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
19.
Yuan Jinjiang 《Journal of Graph Theory》1998,28(4):203-213
We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph G with |V(G)| ≥ 4, the girth g(G) ≤ 4. (2) If G is a connected IM-extendable graph, then |E(G)| ≥ ${3\over 2}|V(G)| - 2$; the equality holds if and only if G ≅ T × K2, where T is a tree. (3) The only 3-regular connected IM-extendable graphs are Cn × K2, for n ≥ 3, and C2n(1, n), for n ≥ 2, where C2n(1, n) is the graph with 2n vertices x0, x1, …, x2n−1, such that xixj is an edge of C2n(1, n) if either |i − j| ≡ 1 (mod 2n) or |i − j| ≡ n (mod 2n). © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 203–213, 1998 相似文献
20.
Odile Favaron Michael A. Henning Christina M. Mynhart Joël Puech 《Journal of Graph Theory》2000,34(1):9-19
A set S of vertices of a graph G is a total dominating set, if every vertex of V(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. We prove that, if G is a graph of order n with minimum degree at least 3, then γt(G) ≤ 7n/13. © 2000 John Wiley & Sons, Inc. J Graph Theory 34:9–19, 2000 相似文献