Search

In 2012, Leveque, Maffray and Trotignon conjectured that if a graph does not contain an induced subdivision of $$K_4$$, then it is 4-colorable. Recently, Le showed that every such graph is 24-colorable. In this paper, we improve the upper bound to 8.

For two graphs A and B, a graph G is called $$\{A,B\}$$-free if G contains neither A nor B as an induced subgraph. Let $$P_{n}$$ denote the path of order n. For nonnegative integers k, $$\ell $$ and m, let $$N_{k,\ell ,m}$$ be the graph obtained from $$K_{3}$$ and three vertex-disjoint paths $$P_{k+1}$$, $$P_{\ell +1}$$, $$P_{m+1}$$ by identifying each of the vertices of $$K_{3}$$ with one endvertex of one of the paths. Let $$Z_{k}=N_{k,0,0}$$ and $$B_{k,\ell }=N_{k,\ell ,0}$$. Bedrossian characterized all pairs $$\{A,B\}$$ of connected graphs such that every 2-connected $$\{A,B\}$$-free graph is Hamiltonian. All pairs appearing in the characterization involve the claw ($$K_{1,3}$$) and one of $$N_{1,1,1}$$, $$P_{6}$$ and $$B_{1,2}$$. In this paper, we characterize connected graphs that are (i) $$\{K_{1,3},Z_{2}\}$$-free but not $$B_{1,1}$$-free, (ii) $$\{K_{1,3},B_{1,1}\}$$-free but not $$P_{5}$$-free, or (iii) $$\{K_{1,3},B_{1,2}\}$$-free but not $$P_{6}$$-free. The third result is closely related to Bedrossian’s characterization. Furthermore, we apply our characterizations to some forbidden pair problems.

A family of finite sets is called union-closed if it contains the union of any two sets in it. The Union-Closed Sets Conjecture of Frankl from 1979 states that each union-closed family contains an element that belongs to at least half of the members of the family. In this paper, we study structural properties of union-closed families. It is known that under the inclusion relation, every union-closed family forms a lattice. We call two union-closed families isomorphic if their corresponding lattices are isomorphic. Let $${{\mathcal {F}}}$$ be a union-closed family and $$\bigcup _{F\in {\mathcal {F}}} F$$ be the universe of $${\mathcal {F}}$$. Among all union-closed families isomorphic to $${{\mathcal {F}}}$$, we develop an algorithm to find one with a maximum universe, and an algorithm to find one with a minimum universe. We also study properties of these two extremal union-closed families in connection with the Union-Closed Set Conjecture. More specifically, a lower bound of sizes of sets of a minimum counterexample to the dual version of the Union-Closed Sets Conjecture is obtained.

A Halin graph is constructed from a plane embedding of a tree with no vertices of degree 2 by adding a cycle through its leaves in the natural order determined by the embedding. Halin graphs satisfy interesting properties. However, to our knowledge, there are no results giving a positive answer for “spanning Halin subgraph problem” (i.e., which graph has a Halin graph as a spanning subgraph) except for a conjecture by Lovasz and Plummer which states that every 4-connected plane triangulation contains a spanning Halin subgraph. In this paper, we investigate the characterization of forbidden pairs guaranteeing the existence of a spanning Halin subgraph. In particular, we show that the set of such pairs is a very small class. Also, we show that $$\{ K_{1,3}, P_5 \}$$ belongs to the set, but neither $$\{ K_{1,4}, P_5 \}$$ nor $$\{ K_{1,3}, P_6 \}$$ belongs to the set.

A graph is called $$2K_2$$ -free if it does not contain two independent edges as an induced subgraph. Gao and Pasechnik conjectured that every $$\frac{3}{2}$$ -tough $$2K_2$$ -free graph with at least three vertices has a spanning trail with maximum degree at most 4. In this paper, we confirm this conjecture. We also provide examples for all $$t < \frac{5}{4}$$ of t-tough graphs that do not have a spanning trail with maximum degree at most 4.

Chvatal and Erd?s proved a well-known result that the graph $$G$$G with connectivity $$\kappa (G)$$?(G) not less than its independence number $$\alpha (G)$$?(G) [$$\alpha (G)+1$$?(G)+1, $$\alpha (G)-1$$?(G)-1, respectively] is Hamiltonian (traceable, Hamiltonian-connected, respectively). In this paper, we strengthen the Chvatal---Erd?s theorem to the following: Let $$G$$G be a simple 2-connected graph of order large enough such that $$\alpha (G)\le \kappa (G)+1$$?(G)≤?(G)+1 [$$\alpha (G)\le \kappa (G)+2$$?(G)≤?(G)+2, $$\alpha (G)\le \kappa (G),$$?(G)≤?(G), respectively] and such that the number of maximum independent sets of cardinality $$\kappa (G)+1$$?(G)+1 [$$\kappa (G)+2$$?(G)+2, $$\kappa (G)$$?(G), respectively] is at most $$n-2\kappa (G)$$n-2?(G) [$$n-2\kappa (G)-1$$n-2?(G)-1, $$n-2\kappa (G)+1$$n-2?(G)+1, respectively]. Then $$G$$G is either Hamiltonian (traceable, Hamiltonian-connected, respectively) or a subgraph of $$K_{k}+((kK_1)\cup K_{n-2k})$$Kk+((kK1)?Kn-2k) [$$K_{k}+((k+1)K_1\cup K_{n-2k-1})$$Kk+((k+1)K1?Kn-2k-1), $$K_{k}+((k-1)K_1\cup K_{n-2k+1})$$Kk+((k-1)K1?Kn-2k+1), respectively].

Let G be an infinite graph embedded in a closed 2-manifold, such that each open face of the embedding is homeomorphic to an open disk and is bounded by finite number of edges. For each vertex x of G, define the combinatorial curvature $$\Phi_G(x) = 1 - \frac{d(x)}{2} + \sum_{\sigma \in F(x)} \frac{1}{|\sigma|}$$ as that of [8], where d(x) is the degree of x, F(x) is the multiset of all open faces σ in the embedding such that the closure $$\bar\sigma$$ contains x (the multiplicity of σ is the number of times that x is visited along ∂σ), and |σ| is the number of sides of edges bounding the face σ. In this paper, we first show that if the absolute total curvature ∑ x∈V(G) |Φ G (x)| is finite, then G has only finite number of vertices of non-vanishing curvature. Next we present a Gauss-Bonnet formula for embedded infinite graphs with finite number of accumulation points. At last, for a finite simple graph G with 3 ≤ d G (x) 0 for every x ∈ V(G), we have (i) if G is embedded in a projective plane and #(V(G)) = n ≥ 1722, then G is isomorphic to the projective wheel P n ; (ii) if G is embedded in a sphere and #(V(G)) = n ≥ 3444, then G is isomorphic to the sphere annulus either A n or B n ; and (iii) if d G (x) = 5 for all x ∈ V(G), then there are only 49 possible embedded plane graphs and 16 possible embedded projective plane graphs.

A sign pattern matrix is a matrix whose entries are from the set {+,−,0}. The purpose of this paper is to obtain bounds on the minimum rank of any symmetric sign pattern matrix A whose graph is a tree T (possibly with loops). In the special case when A is nonnegative with positive diagonal and the graph of A is “star-like”, the exact value of the minimum rank of A is obtained. As a result, it is shown that the gap between the symmetric minimal and maximal ranks can be arbitrarily large for a symmetric tree sign pattern A.

Let G and H be graphs. G is said to be degree-light H-free if G is either H-free or, for every induced subgraph K of G with K≅H, and every {u,v}⊆K, dist K (u,v)=2 implies max {d(u),d(v)}≥|V(G)|/2. In this paper, we will show that every 2-connected graph with either degree-light {K1,3, P6}-free or degree-light {K1,3, Z}-free is hamiltonian (with three exceptional graphs), where P6 is a path of order 6 and Z is obtained from P6 by adding an edge between the first and the third vertex of P6 (see Figure 1).

In the study of hamiltonian graphs, many well known results use degree conditions to ensure sufficient edge density for the existence of a hamiltonian cycle. Recently it was shown that the classic degree conditions of Dirac and Ore actually imply far more than the existence of a hamiltonian cycle in a graph G, but also the existence of a 2-factor with exactly k cycles, where . In this paper we continue to study the number of cycles in 2-factors. Here we consider the well-known result of Moon and Moser which implies the existence of a hamiltonian cycle in a balanced bipartite graph of order 2n. We show that a related degree condition also implies the existence of a 2-factor with exactly k cycles in a balanced bipartite graph of order 2n with .

One of the earliest results about hamiltonian graphs was given by Dirac. He showed that if a graph G has order p and minimum degree at least $$\frac{p} {2}$$ then G is hamiltonian. Moon and Moser showed that if G is a balanced bipartite graph (the two partite sets have the same order) with minimum degree more than $$\frac{p} {4}$$ then G is hamiltonian. Recently their idea is generalized to k-partite graphs by Chen, Faudree, Gould, Jacobson, and Lesniak in terms of minimum degrees. In this paper, we generalize this result in terms of degree sum and the following result is obtained: Let G be a balanced k-partite graph with order kn. If for every pair of nonadjacent vertices u and v which are in different parts $$d(u) + d(v) > \left\{ {\begin{array}{*{20}c} {\left( {k - \frac{2} {{k + 1}}} \right)n} & {if k is odd} \\ {\left( {k - \frac{4} {{k + 2}}} \right)n} & {if k is even} \\ \end{array} } \right.,$$ then G is hamiltonian.

One of the earliest results about hamiltonian graphs was given by Dirac. He showed that if a graphG has orderp and minimum degree at least $$\frac{p}{2}$$ thenG is hamiltonian. Moon and Moser showed that a balanced bipartite graph (the two partite sets have the same order)G has orderp and minimum degree more than $$\frac{p}{4}$$ thenG is hamiltonian. In this paper, their idea is generalized tok-partite graphs and the following result is obtained: LetG be a balancedk-partite graph with orderp = kn. If the minimum degree $$\delta (G) > \left\{ {\begin{array}{*{20}c} {\left( {\frac{k}{2} - \frac{1}{{k + 1}}} \right)n if k is odd } \\ {\left( {\frac{k}{2} - \frac{2}{{k + 2}}} \right)n if k is even} \\ \end{array} } \right.$$ thenG is hamiltonian. The result is best possible.