首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献，搜索用时 14 毫秒
1.
    
For an oriented graph G $$ G $$ , let β ( G ) $$ beta (G) $$ denote the size of a minimum feedback arc set, a smallest edge subset whose deletion leaves an acyclic subgraph. Berger and Shor proved that any m $$ m $$ -edge oriented graph G $$ G $$ satisfies β ( G ) = m / 2 − Ω ( m 3 / 4 ) $$ beta (G)=m/2-Omega left({m}^{3/4}right) $$ . We observe that if an oriented graph G $$ G $$ has a fixed forbidden subgraph B $$ B $$ , the bound β ( G ) = m / 2 − Ω ( m 3 / 4 ) $$ beta (G)=m/2-Omega left({m}^{3/4}right) $$ is sharp as a function of m $$ m $$ if B $$ B $$ is not bipartite, but the exponent 3 / 4 $$ 3/4 $$ in the lower order term can be improved if B $$ B $$ is bipartite. Using a result of Bukh and Conlon on Turán numbers, we prove that any rational number in [ 3 / 4 , 1 ] $$ left[3/4,1right] $$ is optimal as an exponent for some finite family of forbidden subgraphs. Our upper bounds come equipped with randomized linear-time algorithms that construct feedback arc sets achieving those bounds. We also characterize directed quasirandomness via minimum feedback arc sets.  相似文献   

2.
    
We show that the minimum set of unordered graphs that must be forbidden to get the same graph class characterized by forbidding a single ordered graph is infinite. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 71–76, 1999  相似文献   

3.
    
We consider those graphs G that admit decompositions into copies of a fixed graph F, each copy being an induced subgraph of G. We are interested in finding the extremal graphs with this property, that is, those graphs G on n vertices with the maximum possible number of edges. We discuss the cases where F is a complete equipartite graph, a cycle, a star, or a graph on at most four vertices.  相似文献   

4.
All bipartite graphs whose third largest Laplacian eigenvalue is less than 3 have been characterized by Zhang. In this paper, all connected non-bipartite graphs with third largest Laplacian eigenvalue less than three are determined.  相似文献   

5.
    
Let H be a given graph. A graph G is said to be H‐free if G contains no induced copies of H. For a class of graphs, the graph G is ‐free if G is H‐free for every . Bedrossian characterized all the pairs of connected subgraphs such that every 2‐connected ‐free graph is hamiltonian. Faudree and Gould extended Bedrossian's result by proving the necessity part of the result based on infinite families of non‐hamiltonian graphs. In this article, we characterize all pairs of (not necessarily connected) graphs such that there exists an integer n0 such that every 2‐connected ‐free graph of order at least n0 is hamiltonian.  相似文献   

6.
    
An old problem of Erd?s, Fajtlowicz, and Staton asks for the order of a largest induced regular subgraph that can be found in every graph on vertices. Motivated by this problem, we consider the order of such a subgraph in a typical graph on vertices, i.e., in a binomial random graph . We prove that with high probability a largest induced regular subgraph of has about vertices. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 235–250, 2011  相似文献   

7.
Broersma and Veldman proved that every 2-connected claw-free and P 6-free graph is hamiltonian. Chen et al. extended this result by proving every 2-connected claw-heavy and P 6-free graph is hamiltonian. On the other hand, Li et al. constructed a class of 2-connected graphs which are claw-heavy and P 6-o-heavy but not hamiltonian. In this paper, we further give some Ore-type degree conditions restricting to induced copies of P 6 of a 2-connected claw-heavy graph that can guarantee the graph to be hamiltonian. This improves some previous related results.  相似文献   

8.
    
  相似文献   

9.
    
We look at several saturation problems in complete balanced blow‐ups of graphs. We let denote the blow‐up of H onto parts of size n and refer to a copy of H in as partite if it has one vertex in each part of . We then ask how few edges a subgraph G of can have such that G has no partite copy of H but such that the addition of any new edge from creates a partite H. When H is a triangle this value was determined by Ferrara, Jacobson, Pfender, and Wenger in  5 . Our main result is to calculate this value for when n is large. We also give exact results for paths and stars and show that for 2‐connected graphs the answer is linear in n whilst for graphs that are not 2‐connected the answer is quadratic in n. We also investigate a similar problem where G is permitted to contain partite copies of H but we require that the addition of any new edge from creates an extra partite copy of H. This problem turns out to be much simpler and we attain exact answers for all cliques and trees.  相似文献   

10.
    
Given a family and a host graph H, a graph is ‐saturated relative to H if no subgraph of G lies in but adding any edge from to G creates such a subgraph. In the ‐saturation game on H, players Max and Min alternately add edges of H to G, avoiding subgraphs in , until G becomes ‐saturated relative to H. They aim to maximize or minimize the length of the game, respectively; denotes the length under optimal play (when Max starts). Let denote the family of odd cycles and the family of n‐vertex trees, and write F for when . Our results include , for , for , and for . We also determine ; with , it is n when n is even, m when n is odd and m is even, and when is odd. Finally, we prove the lower bound . The results are very similar when Min plays first, except for the P4‐saturation game on .  相似文献   

11.
    
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.
    
A graph is H‐free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique‐width. Brandstädt, Le, and Mosca erroneously claimed that the gem and co‐gem are the only two 1‐vertex P4‐extensions H for which the class of H‐free chordal graphs has bounded clique‐width. In fact we prove that bull‐free chordal and co‐chair‐free chordal graphs have clique‐width at most 3 and 4, respectively. In particular, we find four new classes of H‐free chordal graphs of bounded clique‐width. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H‐free chordal graphs has bounded clique‐width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of ‐free graphs has bounded clique‐width via a reduction to K4‐free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique‐width of H‐free weakly chordal graphs.  相似文献   

13.
    
Let k be a fixed integer at least 3. It is proved that every graph of order (2k ? 1 ? 1/k)n + O(1) contains n vertex disjoint induced subgraphs of order k such that these subgraphs are equivalent to each other and they are equivalent to one of four graphs: a clique, an independent set, a star, or the complement of a star. In particular, by substituting 3 for k, it is proved that every graph of order 14n/3 + O(1) contains n vertex disjoint induced subgraphs of order 3 such that they are equivalent to each other. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 159–166, 2007  相似文献   

14.
    
Let be a family of connected graphs. A graph G is said to be ‐free if G is H‐free for every graph H in . We study the relation between forbidden subgraphs in a connected graph G and the resulting toughness of G. In particular, we consider the problem of characterizing the graph families such that every large enough connected ‐free graph is t‐tough. In this article, we solve this problem for every real positive number t. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 191–202, 2013  相似文献   

15.
  相似文献   

16.
    
A book of size b in a graph is an edge that lies in b triangles. Consider a graph G with n vertices and ?n2/4?; + 1 edges. Rademacher proved that G contains at least ?n/2?; triangles, and several authors proved that G contains a book of size at least n/6. We prove the following “linear combination” of these two results. Suppose that and the maximum size of a book in G is less than αn/2. Then G contains at least triangles as n→?. This is asymptotically sharp. On the other hand, for every , there exists β>0 such that G contains at least βn3 triangles. It remains an open problem to determine the largest possible β in terms of α. Our short proof uses the triangle removal lemma, although there is another approach which avoids this. © 2011 Wiley Periodicals, Inc. J Graph Theory  相似文献   

17.
    
Given a class of graphs and a fixed graph , the online Ramsey game for H on is a game between two players Builder and Painter as follows: an unbounded set of vertices is given as an initial state, and on each turn Builder introduces a new edge with the constraint that the resulting graph must be in , and Painter colors the new edge either red or blue. Builder wins the game if Painter is forced to make a monochromatic copy of at some point in the game. Otherwise, Painter can avoid creating a monochromatic copy of forever, and we say Painter wins the game. We initiate the study of characterizing the graphs such that for a given graph , Painter wins the online Ramsey game for on -free graphs. We characterize all graphs such that Painter wins the online Ramsey game for on the class of -free graphs, except when is one particular graph. We also show that Painter wins the online Ramsey game for on the class of -minor-free graphs, extending a result by Grytczuk, Hałuszczak, and Kierstead [Electron. J. Combin. 11 (2004), p. 60].  相似文献   

18.
    
《Journal of Graph Theory》2018,88(3):411-427
Let be a graph of density p on n vertices. Following Erdős, Łuczak, and Spencer, an m‐vertex subgraph H of G is called full if H has minimum degree at least . Let denote the order of a largest full subgraph of G. If is a nonnegative integer, define Erdős, Łuczak, and Spencer proved that for , In this article, we prove the following lower bound: for , Furthermore, we show that this is tight up to a multiplicative constant factor for infinitely many p near the elements of . In contrast, we show that for any n‐vertex graph G, either G or contains a full subgraph on vertices. Finally, we discuss full subgraphs of random and pseudo‐random graphs, and several open problems.  相似文献   

19.
Komlós [Komlós: Tiling Turán Theorems, Combinatorica, 2000] determined the asymptotically optimal minimum-degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph H, thus essentially extending the Hajnal–Szemerédi theorem that deals with the case when H is a clique. We give a proof of a graphon version of Komlós's theorem. To prove this graphon version, and also to deduce from it the original statement about finite graphs, we use the machinery introduced in [Hladký, Hu, Piguet: Tilings in graphons, arXiv:1606.03113]. We further prove a stability version of Komlós's theorem.  相似文献   

20.
    
Let be a set of connected graphs, each of which has order at least three, and suppose that there exist infinitely many connected -free graphs of minimum degree at least  two and all except for finitely many of them have a 2-factor. In [J. Graph Theory, 64 (2010), 250–266], we proved that if , then one of the members in is a star. In this article, we determine the remaining members of and hence give a complete characterization of the pairs and triples of forbidden subgraphs.  相似文献   

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

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