共查询到20条相似文献，搜索用时 15 毫秒
1.
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 相似文献
2.
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 相似文献
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.
A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,?1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, ?1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore's characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of G. Using the concept of biclique matrices, we describe a Krausz‐type characterization of biclique graphs. Finally, we show that every induced P3 of a biclique graph must be included in a diamond or in a 3‐fan and we also characterize biclique graphs of bipartite graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 1–16, 2010 相似文献
8.
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 相似文献
9.
It is well known that any finite simple graph Γ is an induced subgraph of some exponentially larger strongly regular graph Γ (e.g., [2, 8]). No general polynomial‐size construction has been known. For a given finite simple graph Γ on υ vertices, we present a construction of a strongly regular graph Γ on O(υ4) vertices that contains Γ as its induced subgraph. A discussion is included of the size of the smallest possible strongly regular graph with this property. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 1–8, 2000 相似文献
10.
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 相似文献
11.
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 相似文献
12.
Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005 相似文献
13.
14.
Circular graphs are intersection graphs of arcs on a circle. These graphs are reported to have been studied since 1964, and they have been receiving considerable attention since a series of papers by Tucker in the 1970s. Various subclasses of circular-arc graphs have also been studied. Among these are the proper circular-arc graphs, unit circular-arc graphs, Helly circular-arc graphs and co-bipartite circular-arc graphs. Several characterizations and recognition algorithms have been formulated for circular-arc graphs and its subclasses. In particular, it should be mentioned that linear time algorithms are known for all these classes of graphs. In the present paper, we survey these characterizations and recognition algorithms, with emphasis on the linear time algorithms. 相似文献
15.
The vertices of the flag graph Φ(P) of a graded poset P are its maximal chains. Two vertices are adjacent whenever two maximal chains differ in exactly one element. In this paper
we characterize induced subgraphs of Cartesian product graphs and flag graphs of graded posets. The latter class of graphs
lies between isometric and induced subgraphs of Cartesian products in the embedding structure theory. Both characterization
use certain edge-labelings of graphs. 相似文献
16.
17.
We solve a problem proposed by Jacobson, Kézdy, and Lehel [4] concerning the existence of forbidden induced subgraph characterizations of line graphs of linear k-uniform hypergraphs with sufficiently large minimal edge-degree. Actually, we prove that for each k3 there is a finite set Z(k) of graphs such that each graph G with minimum edge-degree at least 2k2–3k+1 is the line graph of a linear k-uniform hypergraph if and only if G is a Z(k)-free graph.Acknowledgments. We thank the anonymous referees, whose suggestions helped to improve the presentation of the paper.Winter 2002/2003 DIMACS Award is gratefully acknowledged2000 Mathematics Subject Classification: 05C65 (05C75, 05C85) 相似文献
18.
A subgraph of a graph G is called trivial if it is either a clique or an independent set. Let q(G) denote the maximum number of vertices in a trivial subgraph of G. Motivated by an open problem of Erd?s and McKay we show that every graph G on n vertices for which q(G)≤ C log n contains an induced subgraph with exactly y edges, for every y between 0 and nδ (C). Our methods enable us also to show that under much weaker assumption, i.e., q(G) ≤ n/14, G still must contain an induced subgraph with exactly y edges, for every y between 0 and . © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 239–251, 2003 相似文献
19.
Jill R. Faudree Ralph J. Faudree Zdeněk Ryjáček Petr Vrána 《Journal of Graph Theory》2013,72(3):327-345
Let X, Y be connected graphs. A graph G is ‐free if G contains a copy of neither X nor Y as an induced subgraph. Pairs of connected graphs such that every 3‐connected ‐free graph is Hamilton connected have been investigated most recently in (Guantao Chen and Ronald J. Gould, Bull. Inst. Combin. Appl., 29 (2000), 25–32.) [8] and (H. Broersma, R. J. Faudree, A. Huck, H. Trommel, and H. J. Veldman, J. Graph Theory, 40(2) (2002), 104–119.) [5]. This paper improves those results. Specifically, it is shown that every 3‐connected ‐free graph is Hamilton connected for and or N1, 2, 2 and the proof of this result uses a new closure technique developed by the third and fourth authors. A discussion of restrictions on the nature of the graph Y is also included. 相似文献
20.
Flavia Bonomo 《Discrete Mathematics》2006,306(6):595-597
A clique in a graph is a complete subgraph maximal under inclusion. The clique graph of a graph is the intersection graph of its cliques. A graph is self-clique when it is isomorphic to its clique graph. A circular-arc graph is the intersection graph of a family of arcs of a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. In this note, we describe all the self-clique Helly circular-arc graphs. 相似文献