Search

Motivated by the counting results for color-critical subgraphs by Mubayi (2010), we study the phenomenon behind Mubayi's theorem from a spectral perspective and start up this problem with the fundamental case of triangles. We prove tight bounds for the number of copies of triangle in a graph of order n and size m with spectral radius λ. Our results extend those of Nosal, who proved there is one triangle if λ > m , and of Rademacher, who proved there are at least ⌊ n 2 ⌋ triangles if the size is more than that of bipartite Turán graph. These results, together with two spectral inequalities due to Bollobás and Nikiforov, can be seen as a solution to the case of triangles of a problem of finding spectral versions of Mubayi's theorem. In addition, we give a short proof of the following inequality due to Bollobás and Nikiforov (2007): the number of copies of triangle t (G) ≥ λ (λ 2 − m) 3 , and characterize the extremal graphs. Some problems are proposed in the end. [ABSTRACT FROM AUTHOR]

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

A graph G is called claw-o-heavy if every induced claw ( $$K_{1,3}$$ ) of G has two end-vertices with degree sum at least | V( G)|. For a given graph S, G is called S-f-heavy if for every induced subgraph H of G isomorphic to S and every pair of vertices $$u,v\in V(H)$$ with $$d_H(u,v)=2,$$ there holds $$\max \{d(u),d(v)\}\ge |V(G)|/2.$$ In this paper, we prove that every 2-connected claw- o-heavy and $$Z_3$$ - f-heavy graph is hamiltonian (with two exceptional graphs), where $$Z_3$$ is the graph obtained by identifying one end-vertex of $$P_4$$ (a path with 4 vertices) with one vertex of a triangle. This result gives a positive answer to a problem proposed Ning and Zhang (Discrete Math 313:1715-1725, ), and also implies two previous theorems of Faudree et al. and Chen et al., respectively. [ABSTRACT FROM AUTHOR]

Let G1 and G2 be two given graphs. The Ramsey number R(G1,G2) is the least integer r such that for every graph G on r vertices, either G contains a G1 or Ḡ contains a G2. Parsons gave a recursive formula to determine the values of R(Pn,K1,m), where Pn is a path on n vertices and K1,m is a star on m+1 vertices. In this note, we study the Ramsey numbers R(Pn,K1,m), where Pn is a linear forest on m vertices. We determine the exact values of R(Pn,K1∨Fm) for the cases m ≤ n and m ≥ 2n, and for the case that Fm has no odd component. Moreover, we give a lower bound and an upper bound for the case n+1 ≤ m ≤ 2n−1 and Fm has at least one odd component. [ABSTRACT FROM AUTHOR]

Let claw be the graph K1,3. A graph G on n ≥ 3 vertices is called o-heavy if each induced claw of G has a pair of end-vertices with degree sum at least n, and called 1-heavy if at least one end-vertex of each induced claw of G has degree at least n/2. In this note, we show that every 2-connected o-heavy or 3-connected 1-heavy graph is Hamiltonian if we restrict Fan-type degree condition or neighborhood intersection condition to certain pairs of vertices in some small induced subgraphs of the graph. Our results improve or extend previous results of Broersma et al., Chen et al., Fan, Goodman and Hedetniemi, Gould and Jacobson, and Shi on the existence of Hamilton cycles in graphs. [ABSTRACT FROM AUTHOR]

Abstract: Bedrossian characterized all pairs of forbidden subgraphs for a 2-connected graph to be Hamiltonian. Instead of forbidding some induced subgraphs, we relax the conditions for graphs to be Hamiltonian by restricting Ore- and Fan-type degree conditions on these induced subgraphs. Let be a graph on vertices and be an induced subgraph of . is called -heavy if there are two nonadjacent vertices in with degree sum at least , and is called -heavy if for every two vertices , implies that . We say that is - -heavy ( - -heavy) if every induced subgraph of isomorphic to is -heavy ( -heavy). In this paper we characterize all connected graphs and other than such that every 2-connected - -heavy and - -heavy ( - -heavy and - -heavy, - -heavy and -free) graph is Hamiltonian. Our results extend several previous theorems on forbidden subgraph conditions and heavy subgraph conditions for Hamiltonicity of 2-connected graphs. [Copyright &y& Elsevier]

A graph is called claw-free if it contains no induced subgraph isomorphic to K. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least (| V( G)| − 2)/3. At the workshop Camp;C (Novy Smokovec, 1993), Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N (the graph obtained from a triangle by adding three disjoint pendant edges). Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z (the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if each end-vertex of every induced copy of H in G has degree at least | V( G)|/3+1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant. [ABSTRACT FROM AUTHOR]

The chromatic polynomial P(G,x) of a graph G of order n can be expressed as ∑i=1n(−1)n−iaixi, where ai is interpreted as the number of broken‐cycle‐free spanning subgraphs of G with exactly i components. The parameter ϵ(G)=∑i=1n(n−i)ai∕∑i=1nai is the mean size of a broken‐cycle‐free spanning subgraph of G. In this article, we confirm and strengthen a conjecture proposed by Lundow and Markström in 2006 that ϵ(Tn)<ϵ(G)<ϵ(Kn) holds for any connected graph G of order n which is neither the complete graph Kn nor a tree Tn of order n. The most crucial step of our proof is to obtain the interpretation of all ai's by the number of acyclic orientations of G. [ABSTRACT FROM AUTHOR]