共查询到20条相似文献，搜索用时 15 毫秒
1.
It is easy to characterize chordal graphs by every k‐cycle having at least f(k) = k ? 3 chords. I prove new, analogous characterizations of the house‐hole‐domino‐free graphs using f(k) = 2?(k ? 3)/2?, and of the graphs whose blocks are trivially perfect using f(k) = 2k ? 7. These three functions f(k) are optimum in that each class contains graphs in which every k‐cycle has exactly f(k) chords. The functions 3?(k ? 3)/3? and 3k ? 11 also characterize related graph classes, but without being optimum. I consider several other graph classes and their optimum functions, and what happens when k‐cycles are replaced with k‐paths. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:137‐147, 2011 相似文献
2.
We consider the existence of several different kinds of factors in 4‐connected claw‐free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4‐connected line graph is hamiltonian, i.e., has a connected 2‐factor. Conjecture 2 (Matthews and Sumner): Every 4‐connected claw‐free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass‐free graphs, i.e., graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjectures 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 125–136, 2001 相似文献
3.
We introduce a closure concept that turns a claw‐free graph into the line graph of a multigraph while preserving its (non‐)Hamilton‐connectedness. As an application, we show that every 7‐connected claw‐free graph is Hamilton‐connected, and we show that the well‐known conjecture by Matthews and Sumner (every 4‐connected claw‐free graph is hamiltonian) is equivalent with the statement that every 4‐connected claw‐free graph is Hamilton‐connected. Finally, we show a natural way to avoid the non‐uniqueness of a preimage of a line graph of a multigraph, and we prove that the closure operation is, in a sense, best possible. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:152‐173, 2011 相似文献
4.
A graph G is 1‐Hamilton‐connected if is Hamilton‐connected for every vertex . In the article, we introduce a closure concept for 1‐Hamilton‐connectedness in claw‐free graphs. If is a (new) closure of a claw‐free graph G, then is 1‐Hamilton‐connected if and only if G is 1‐Hamilton‐connected, is the line graph of a multigraph, and for some , is the line graph of a multigraph with at most two triangles or at most one double edge. As applications, we prove that Thomassen's Conjecture (every 4‐connected line graph is hamiltonian) is equivalent to the statement that every 4‐connected claw‐free graph is 1‐Hamilton‐connected, and we present results showing that every 5‐connected claw‐free graph with minimum degree at least 6 is 1‐Hamilton‐connected and that every 4‐connected claw‐free and hourglass‐free graph is 1‐Hamilton‐connected. 相似文献
5.
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 相似文献
6.
Florian Pfender 《Journal of Graph Theory》2005,49(4):262-272
Let T be the line graph of the unique tree F on 8 vertices with degree sequence (3,3,3,1,1,1,1,1), i.e., T is a chain of three triangles. We show that every 4‐connected {T, K1,3}‐free graph has a hamiltonian cycle. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 262–272, 2005 相似文献
7.
We show that every 3‐connected claw‐free graph which contains no induced copy of P11 is hamiltonian. Since there exist non‐hamiltonian 3‐connected claw‐free graphs without induced copies of P12 this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 111–121, 2004 相似文献
8.
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 相似文献
9.
The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that if G is a connected claw‐free circular‐perfect graph with χ(G)>ω(G), then min{α(G), ω(G)}=2. We use this result to design a polynomial time algorithm that computes the circular chromatic number of claw‐free circular‐perfect graphs. A consequence of the strong perfect graph theorem is that minimal imperfect graphs G have min{α(G), ω(G)}=2. In contrast to this result, it is shown in Z. Pan and X. Zhu [European J Combin 29(4) (2008), 1055–1063] that minimal circular‐imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. In this article, we prove that claw‐free minimal circular‐imperfect graphs G have min{α(G), ω(G)}≤3. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 163–172, 2010 相似文献
10.
We introduce a closure concept in the class of line graphs and claw‐free graphs based on contractibility of certain subgraphs in the line graph preimage. The closure can be considered as a common generalization and strengthening of the reduction techniques of Catlin and Veldman and of the closure concept introduced by the first author. We show that the closure is uniquely determined and the closure operation preserves the circumference of the graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 37–48, 2003 相似文献
11.
Hajo Broersma Ralph J. Faudree Andreas Huck Huib Trommel Henk Jan Veldman 《Journal of Graph Theory》2002,40(2):104-119
It is proven that if G is a 3‐connected claw‐free graph which is also H1‐free (where H1 consists of two disjoint triangles connected by an edge), then G is hamiltonian‐connected. Also, examples will be described that determine a finite family of graphs such that if a 3‐connected graph being claw‐free and L‐free implies G is hamiltonian‐connected, then L . © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 104–119, 2002 相似文献
12.
In the class of k‐connected claw‐free graphs, we study the stability of some Hamiltonian properties under a closure operation introduced by the third author. We prove that (i) the properties of pancyclicity, vertex pancyclicity and cycle extendability are not stable for any k (i.e., for any of these properties there is an infinite family of graphs Gk of arbitrarily high connectivity k such that the closure of Gk has the property while the graph Gk does not); (ii) traceability is a stable property even for k = 1; (iii) homogeneous traceability is not stable for k = 2 (although it is stable for k = 7). The article is concluded with several open questions concerning stability of homogeneous traceability and Hamiltonian connectedness. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 30–41, 2000 相似文献
13.
14.
Let n≥2 be an integer. The complete graph Kn with a 1‐factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that Kn−F has a decomposition into Hamilton cycles which are symmetric with respect to the 1‐factor F if and only if n≡2, 4 mod 8. We also show that the complete bipartite graph Kn, n has a symmetric Hamilton cycle decomposition if and only if n is even, and that if F is a 1‐factor of Kn, n, then Kn, n−F has a symmetric Hamilton cycle decomposition if and only if n is odd. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:1‐15, 2010 相似文献
15.
Polarity and monopolarity are properties of graphs defined in terms of the existence of certain vertex partitions; graphs with polarity and monopolarity are respectively called polar and monopolar graphs. These two properties commonly generalize bipartite and split graphs, but are hard to recognize in general. In this article we identify two classes of graphs, triangle‐free graphs and claw‐free graphs, restricting to which provide novel impact on the complexity of the recognition problems. More precisely, we prove that recognizing polarity or monopolarity remains NP‐complete for triangle‐free graphs. We also show that for claw‐free graphs the former is NP‐complete and the latter is polynomial time solvable. This is in sharp contrast to a recent result that both polarity and monopolarity can be recognized in linear time for line graphs. Our proofs for the NP‐completeness are simple reductions. The polynomial time algorithm for recognizing the monopolarity of claw‐free graphs uses a subroutine similar to the well‐known breadth‐first search algorithm and is based on a new structural characterization of monopolar claw‐free graphs, a generalization of one for monopolar line graphs obtained earlier. 相似文献
16.
A graph G is N2‐locally connected if for every vertex ν in G, the edges not incident with ν but having at least one end adjacent to ν in G induce a connected graph. In 1990, Ryjá?ek conjectured that every 3‐connected N2‐locally connected claw‐free graph is Hamiltonian. This conjecture is proved in this note. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 142–146, 2005 相似文献
17.
Darryn Bryant 《组合设计杂志》2004,12(2):147-155
For all integers n ≥ 5, it is shown that the graph obtained from the n‐cycle by joining vertices at distance 2 has a 2‐factorization is which one 2‐factor is a Hamilton cycle, and the other is isomorphic to any given 2‐regular graph of order n. This result is used to prove several results on 2‐factorizations of the complete graph Kn of order n. For example, it is shown that for all odd n ≥ 11, Kn has a 2‐factorization in which three of the 2‐factors are isomorphic to any three given 2‐regular graphs of order n, and the remaining 2‐factors are Hamilton cycles. For any two given 2‐regular graphs of even order n, the corresponding result is proved for the graph Kn ‐ I obtained from the complete graph by removing the edges of a 1‐factor. © 2004 Wiley Periodicals, Inc. 相似文献
18.
The second author's (B.A.R.) ω, Δ, χ conjecture proposes that every graph satisfies . In this article, we prove that the conjecture holds for all claw‐free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way, we discuss a stronger local conjecture, and prove that it holds for claw‐free graphs with a three‐colorable complement. To prove our results, we introduce a very useful χ‐preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so‐called skeletal graphs. 相似文献
19.
邻接树图是哈密尔顿图猜想的一个等价命题 总被引：1，自引：0，他引：1
本文给出了简单图的邻接树图是哈密尔顿图”猜想的等价命题,阐明只需证明该猜想对2－连通图成立即可,另外,我们给出了该猜想一种特殊情形的构造性证明。 相似文献
20.
We prove that the strong product of any at least non‐trivial connected graphs of maximum degree at most Δ is pancyclic. The obtained result is asymptotically best possible since the strong product of ?(ln 2)D? stars K1,D is not even hamiltonian. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 314–328, 2008 相似文献