共查询到20条相似文献，搜索用时 15 毫秒
1.
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 相似文献
2.
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 相似文献
3.
In [2], on page 252 the following logical terminal inexactitude was made: “...the existence of a K4 is the only obstruction. That is, every finite K4‐free graph can be represented by odd‐distances in the plane.” In this note we correct this erroneous claim by showing that W5, the 5‐wheel, see Figure 1, is not a subgraph of . 相似文献
4.
Ya‐Chen Chen 《Journal of Graph Theory》2011,67(1):9-26
A graph is C5‐ saturated if it has no five‐cycle as a subgraph, but does contain a C5 after the addition of any new edge. Extending our previous result, we prove that the minimum number of edges in a C5‐saturated graph on n vertices is sat(n, C5) = ?10(n ? 1)/7? ? 1 for 11≤n≤14, or n = 16, 18, 20, and is ?10(n ? 1)/7? for all other n≥5, and we also prove that the only C5‐saturated graphs with sat(n, C5) edges are the graphs described in Section 2 . © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 9‐26, 2011 相似文献
5.
Ya‐Chen Chen 《Journal of Graph Theory》2009,61(2):111-126
A graph is C5‐saturated if it has no five‐cycle as a subgraph, but does contain a C5 after the addition of any new edge. We prove that the minimum number of edges in a C5 ‐saturated graph on n≥11 vertices is sat(n, C5)=?10(n?1)/7??1 if n∈N0={11, 12, 13, 14, 16, 18, 20} and is ?10(n?1)/7? if n≥11 and n?N0. © 2009 Wiley Periodicals, Inc. J Graph Theory 相似文献
6.
Let be the family of graphs G such that all sufficiently large k ‐connected claw‐free graphs which contain no induced copies of G are subpancyclic. We show that for every k≥3 the family is infinite and make the first step toward the complete characterization of the family . © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 263–278, 2009 相似文献
7.
A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are minimal with this property. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 369–384, 2009 相似文献
8.
Martín D. Safe 《Journal of Graph Theory》2020,93(2):268-298
A graph is concave-round if its vertices can be circularly enumerated so that the closed neighborhood of each vertex is an interval in the enumeration. In this study, we give a minimal forbidden induced subgraph characterization for the class of concave-round graphs, solving a problem posed by Bang-Jensen, Huang, and Yeo [SIAM J. Discrete Math., 13 (2000), pp. 179–193]. In addition, we show that it is possible to find one such forbidden induced subgraph in linear time in any given graph that is not concave-round. As part of the analysis, we obtain characterizations by minimal forbidden submatrices for the circular-ones property for rows and for the circular-ones property for rows and columns and show that, also for both variants of the property, one of the corresponding forbidden submatrices can be found (if present) in any given matrix in linear time. We make some final remarks regarding connections to some classes of circular-arc graphs. 相似文献
9.
A graph G is a quasi‐line graph if for every vertex v, the set of neighbors of v can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. A theorem of Shannon's implies that if G is a line graph, then it can be properly colored using no more than 3/2 ω(G) colors, where ω(G) is the size of the largest clique in G. In this article, we extend this result to all quasi‐line graphs. We also show that this bound is tight. © 2006 Wiley Periodicals, Inc. J Graph Theory 相似文献
10.
A circular‐arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular‐arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to any of the following classes: P4 ‐free graphs, paw‐free graphs, claw‐free chordal graphs and diamond‐free graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 289–306, 2009 相似文献
12.
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 相似文献
13.
Let be a family of n compact connected sets in the plane, whose intersection graph has no complete bipartite subgraph with k vertices in each of its classes. Then has at most n times a polylogarithmic number of edges, where the exponent of the logarithmic factor depends on k. In the case where consists of convex sets, we improve this bound to O(n log n). If in addition k = 2, the bound can be further improved to O(n). © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 205–214, 2008 相似文献
14.
Let S1, S2,…,St be pairwise disjoint non‐empty stable sets in a graph H. The graph H* is obtained from H by: (i) replacing each Si by a new vertex qi; (ii) joining each qi and qj, 1 ≤ i # j ≤ t, and; (iii) joining qi to all vertices in H – (S1 ∪ S2 ∪ ··· ∪ St) which were adjacent to some vertex of Si. A cograph is a P4‐free graph. A graph G is called a cograph contraction if there exist a cograph H and pairwise disjoint non‐empty stable sets in H for which G ? H*. Solving a problem proposed by Le [ 2 ], we give a finite forbidden induced subgraph characterization of cograph contractions. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 217–226, 2004 相似文献
15.
Let G be a connected graph and let eb(G) and λ(G) denote the number of end‐blocks and the maximum number of disjoint 3‐vertex paths Λ in G. We prove the following theorems on claw‐free graphs: (t1) if G is claw‐free and eb(G) ≤ 2 (and in particular, G is 2‐connected) then λ(G) = ⌊| V(G)|/3⌋; (t2) if G is claw‐free and eb(G) ≥ 2 then λ(G) ≥ ⌊(| V(G) | − eb(G) + 2)/3 ⌋; and (t3) if G is claw‐free and Δ*‐free then λ(G) = ⌊| V(G) |/3⌋ (here Δ* is a graph obtained from a triangle Δ by attaching to each vertex a new dangling edge). We also give the following sufficient condition for a graph to have a Λ‐factor: Let n and p be integers, 1 ≤ p ≤ n − 2, G a 2‐connected graph, and |V(G)| = 3n. Suppose that G − S has a Λ‐factor for every S ⊆ V(G) such that |S| = 3p and both V(G) − S and S induce connected subgraphs in G. Then G has a Λ‐factor. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 175–197, 2001 相似文献
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.
Zhi‐Hong Chen Hong‐Jian Lai Xiangwen Li Deying Li Jinzhong Mao 《Journal of Graph Theory》2003,42(4):308-319
In this paper, we show that if G is a 3‐edge‐connected graph with and , then either G has an Eulerian subgraph H such that , or G can be contracted to the Petersen graph in such a way that the preimage of each vertex of the Petersen graph contains at least one vertex in S. If G is a 3‐edge‐connected planar graph, then for any , G has an Eulerian subgraph H such that . As an application, we obtain a new result on Hamiltonian line graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 308–319, 2003 相似文献
18.
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 (other than itself). The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γt(G). We establish bounds on Γt(G) for claw‐free graphs G in terms of the number n of vertices and the minimum degree δ of G. We show that if if , and if δ ≥ 5. The extremal graphs are characterized. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 148–158, 2003 相似文献
19.
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 相似文献
20.
J. Harant M. Voigt S. Jendrol B. Randerath Z. Ryj
ek I. Schiermeyer 《Journal of Graph Theory》2001,36(3):131-143
Let G be a K1,r ‐free graph (r ≥ 3) on n vertices. We prove that, for any induced path or induced cycle on k vertices in G (k ≥ 2r − 1 or k ≥ 2r, respectively), the degree sum of its vertices is at most (2r − 2)(n − α) where α is the independence number of G. As a corollary we obtain an upper bound on the length of a longest induced path and a longest induced cycle in a K1,r ‐free graph. Stronger bounds are given in the special case of claw‐free graphs (i.e., r = 3). Sharpness examples are also presented. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 131–143, 2001 相似文献