首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
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 γ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  相似文献   

2.
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  相似文献   

3.
A subset S of vertices of a graph G is called cyclable in G if there is in G some cycle containing all the vertices of S. We denote by α(S, G) the number of vertices of a maximum independent set of G[S]. We prove that if G is a 3‐connected graph or order n and if S is a subset of vertices such that the degree sum of any four independent vertices of S is at least n + 2α(S, G) −2, then S is cyclable. This result implies several known results on cyclability or Hamiltonicity. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 191–203, 2000  相似文献   

4.
An edge‐colored graph Gis rainbow edge‐connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make Grainbow edge‐connected. We prove that if Ghas nvertices and minimum degree δ then rc(G)<20n/δ. This solves open problems from Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster (Electron J Combin 15 (2008), #R57) and S. Chakrborty, E. Fischer, A. Matsliah, and R. Yuster (Hardness and algorithms for rainbow connectivity, Freiburg (2009), pp. 243–254). A vertex‐colored graph Gis rainbow vertex‐connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex‐connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make Grainbow vertex‐connected. One cannot upper‐bound one of these parameters in terms of the other. Nevertheless, we prove that if Ghas nvertices and minimum degree δ then rvc(G)<11n/δ. We note that the proof in this case is different from the proof for the edge‐colored case, and we cannot deduce one from the other. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 185–191, 2010  相似文献   

5.
We prove that if G is a 5‐connected graph embedded on a surface Σ (other than the sphere) with face‐width at least 5, then G contains a subdivision of K5. This is a special case of a conjecture of P. Seymour, that every 5‐connected nonplanar graph contains a subdivision of K5. Moreover, we prove that if G is 6‐connected and embedded with face‐width at least 5, then for every vV(G), G contains a subdivision of K5 whose branch vertices are v and four neighbors of v.  相似文献   

6.
Suppose G is a graph, k is a non‐negative integer. We say G is k‐antimagic if there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . We say G is weighted‐k‐antimagic if for any vertex weight function w: V→?, there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . A well‐known conjecture asserts that every connected graph GK2 is 0‐antimagic. On the other hand, there are connected graphs GK2 which are not weighted‐1‐antimagic. It is unknown whether every connected graph GK2 is weighted‐2‐antimagic. In this paper, we prove that if G has a universal vertex, then G is weighted‐2‐antimagic. If G has a prime number of vertices and has a Hamiltonian path, then G is weighted‐1‐antimagic. We also prove that every connected graph GK2 on n vertices is weighted‐ ?3n/2?‐antimagic. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory  相似文献   

7.
We conjecture that, for each tree T, there exists a natural number kT such that the following holds: If G is a kT‐edge‐connected graph such that |E(T)| divides |E(G)|, then the edges of G can be divided into parts, each of which is isomorphic to T. We prove that for T = K1,3 (the claw), this holds if and only if there exists a (smallest) natural number kt such that every kt‐edge‐connected graph has an orientation for which the indegree of each vertex equals its outdegree modulo 3. Tutte's 3‐flow conjecture says that kt = 4. We prove the weaker statement that every 4$\lceil$ log n$\rceil$ ‐edge‐connected graph with n vertices has an edge‐decomposition into claws provided its number of edges is divisible by 3. We also prove that every triangulation of a surface has an edge‐decomposition into claws. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 135–146, 2006  相似文献   

8.
Suppose G is a simple connected n‐vertex graph. Let σ3(G) denote the minimum degree sum of three independent vertices in G (which is ∞ if G has no set of three independent vertices). A 2‐trail is a trail that uses every vertex at most twice. Spanning 2‐trails generalize hamilton paths and cycles. We prove three main results. First, if σ3G)≥ n ‐ 1, then G has a spanning 2‐trail, unless G ? K1,3. Second, if σ3(G) ≥ n, then G has either a hamilton path or a closed spanning 2‐trail. Third, if G is 2‐edge‐connected and σ3(G) ≥ n, then G has a closed spanning 2‐trail, unless G ? K2,3 or K (the 6‐vertex graph obtained from K2,3 by subdividing one edge). All three results are sharp. These results are related to the study of connected and 2‐edge‐connected factors, spanning k‐walks, even factors, and supereulerian graphs. In particular, a closed spanning 2‐trail may be regarded as a connected (and 2‐edge‐connected) even [2,4]‐factor. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 298–319, 2004  相似文献   

9.
A graph G = (V, E) is called weakly four‐connected if G is 4‐edge‐connected and G ? x is 2‐edge‐connected for all xV. We give sufficient conditions for the existence of ‘splittable’ vertices of degree four in weakly four‐connected graphs. By using these results we prove that every minimally weakly four‐connected graph on at least four vertices contains at least three ‘splittable’ vertices of degree four, which gives rise to an inductive construction of weakly four‐connected graphs. Our results can also be applied in the problem of finding 2‐connected orientations of graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 217–229, 2006  相似文献   

10.
An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K4?‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2n/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009  相似文献   

11.
A graph G of order at least 2n+2 is said to be n‐extendable if G has a perfect matching and every set of n independent edges extends to a perfect matching in G. We prove that every pair of nonadjacent vertices x and y in a connected n‐extendable graph of order p satisfy degG x+degG yp ? n ? 1, then either G is hamiltonian or G is isomorphic to one of two exceptional graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 75–82, 2002  相似文献   

12.
An antimagic labelling of a graph G with m edges and n vertices is a bijection from the set of edges of G to the set of integers {1,…,m}, such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with that vertex. A graph is called antimagic if it admits an antimagic labelling. In N. Hartsfield and G. Ringle, Pearls in Graph Theory, Academic Press, Inc., Boston, 1990, Ringel has conjectured that every simple connected graph, other than K2, is antimagic. In this article, we prove a special case of this conjecture. Namely, we prove that if G is a graph on n=pk vertices, where p is an odd prime and k is a positive integer that admits a Cp‐factor, then it is antimagic. The case p=3 was proved in D. Hefetz, J Graph Theory 50 (2005), 263–272. Our main tool is the combinatorial Nullstellensatz [N. Alon, Combin Probab Comput 8(1–2) (1999), 7–29]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 70–82, 2010.  相似文献   

13.
Under what conditions is it true that if there is a graph homomorphism GHGT, then there is a graph homomorphism HT? 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 ?: GHST is a graph homomorphism, then either ? maps G□{h} to S□{th} for all hV(H) where thV(T) depends on h; or ? maps G□{h} to {sh}□ T for all hV(H) where shV(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  相似文献   

14.
For a graph G, let σk(G) be the minimum degree sum of an independent set of k vertices. Ore showed that if G is a graph of order n?3 with σ2(G)?n then G is hamiltonian. Let κ(G) be the connectivity of a graph G. Bauer, Broersma, Li and Veldman proved that if G is a 2-connected graph on n vertices with σ3(G)?n+κ(G), then G is hamiltonian. On the other hand, Bondy showed that if G is a 2-connected graph on n vertices with σ3(G)?n+2, then each longest cycle of G is a dominating cycle. In this paper, we prove that if G is a 3-connected graph on n vertices with σ4(G)?n+κ(G)+3, then G contains a longest cycle which is a dominating cycle.  相似文献   

15.
An overlap representation of a graph G assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The overlap number φ(G) (introduced by Rosgen) is the minimum size of the union of the sets in such a representation. We prove the following: (1) An optimal overlap representation of a tree can be produced in linear time, and its size is the number of vertices in the largest subtree in which the neighbor of any leaf has degree 2. (2) If δ(G)?2 and GK3, then φ(G)?|E(G)| ? 1, with equality when G is connected and triangle‐free and has no star‐cutset. (3) If G is an n‐vertex plane graph with n?5, then φ(G)?2n ? 5, with equality when every face has length 4 and there is no star‐cutset. (4) If G is an n‐vertex graph with n?14, then φ(G)?n2/4 ? n/2 ? 1, with equality for even n when G arises from Kn/2, n/2 by deleting a perfect matching. © 2011 Wiley Periodicals, Inc. J Graph Theory  相似文献   

16.
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  相似文献   

17.
Let G be a finite simple graph. Let SV(G), its closed interval I[S] is the set of all vertices lying on shortest paths between any pair of vertices of S. The set S is convex if I[S]=S. In this work we define the concept of a convex partition of graphs. If there exists a partition of V(G) into p convex sets we say that G is p-convex. We prove that it is NP-complete to decide whether a graph G is p-convex for a fixed integer p≥2. We show that every connected chordal graph is p-convex, for 1≤pn. We also establish conditions on n and k to decide if the k-th power of a cycle Cn is p-convex. Finally, we develop a linear-time algorithm to decide if a cograph is p-convex.  相似文献   

18.
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.  相似文献   

19.
In this article, we consider the following problem. Given four distinct vertices v1,v2,v3,v4. How many edges guarantee the existence of seven connected disjoint subgraphs Xi for i = 1,…, 7 such that Xj contains vj for j = 1, 2, 3, 4 and for j = 1, 2, 3, 4, Xj has a neighbor to each Xk with k = 5, 6, 7. This is the so called “rooted K3, 4‐minor problem.” There are only few known results on rooted minor problems, for example, [15,6]. In this article, we prove that a 4‐connected graph with n vertices and at least 5n ? 14 edges has a rooted K3,4‐minor. In the proof we use a lemma on graphs with 9 vertices, proved by computer search. We also consider the similar problems concerning rooted K3,3‐minor problem, and rooted K3,2‐minor problem. More precisely, the first theorem says that if G is 3‐connected and e(G) ≥ 4|G| ? 9 then G has a rooted K3,3‐minor, and the second theorem says that if G is 2‐connected and e(G) ≥ 13/5|G| ? 17/5 then G has a rooted K3,2‐minor. In the second case, the extremal function for the number of edges is best possible. These results are then used in the proof of our forthcoming articles 7 , 8 . © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 191–207, 2007  相似文献   

20.
Let G be a connected graph with odd girth 2κ+1. Then G is a (2κ+1)‐angulated graph if every two vertices of G are connected by a path such that each edge of the path is in some (2κ+1)‐cycle. We prove that if G is (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+3, then any retract of the box (or Cartesian) product GH is ST where S is a retract of G and T is a connected subgraph of H. A graph G is strongly (2κ+1)‐angulated if any two vertices of G are connected by a sequence of (2κ+1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+1, then any retract of GH is ST where S is a retract of G and T is a connected subgraph of H or |V(S)|=1 and T is a retract of H. These two results improve theorems on weakly and strongly triangulated graphs by Nowakowski and Rival [Disc Math 70 ( 13 ), 169–184]. As a corollary, we get that the core of the box product of two strongly (2κ+1)‐angulated cores must be either one of the factors or the box product itself. Furthermore, if G is a strongly (2κ+1)‐angulated core, then either Gn is a core for all positive integers n, or the core of Gn is G for all positive integers n. In the latter case, G is homomorphically equivalent to a normal Cayley graph [Larose, Laviolette, Tardiff, European J Combin 19 ( 12 ), 867–881]. In particular, let G be a strongly (2κ+1)‐angulated core such that either G is not vertex‐transitive, or G is vertex‐transitive and any two maximum independent sets have non‐empty intersection. Then Gn is a core for any positive integer n. On the other hand, let Gi be a (2κi+1)‐angulated core for 1 ≤ in where κ1 < κ2 < … < κn. If Gi has a vertex that is fixed under any automorphism for 1 ≤ in‐1, or Gi is vertex‐transitive such that any two maximum independent sets have non‐empty intersection for 1 ≤ in‐1, then □i=1n Gi is a core. We then apply the results to construct cores that are box products with Mycielski construction factors or with odd graph factors. We also show that K(r,2r+1) □ C2l+1 is a core for any integers lr ≥ 2. It is open whether K(r,2r+1) □ C2l+1 is a core for r > l ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号