Path factors and parallel knock-out schemes of almost claw-free graphs

An H₁,{H₂}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H₁ and all other components (if there are any) isomorphic to the graph H₂. We completely characterise the class of connected almost claw-free graphs that have a P₇,{P₂}-factor, where P₇ and P₂ denote the paths on seven and two vertices, respectively. We apply this result to parallel knock-out schemes for almost claw-free graphs. These schemes proceed in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is reducible if such a scheme eliminates every vertex in the graph. Using our characterisation, we are able to classify all reducible almost claw-free graphs, and we can show that every reducible almost claw-free graph is reducible in at most two rounds. This leads to a quadratic time algorithm for determining if an almost claw-free graph is reducible (which is a generalisation and improvement upon the previous strongest result that showed that there was a O(n^5.376) time algorithm for claw-free graphs on n vertices).     

Connected even factors in claw-free graphs

A connected even [2,2s]-factor of a graph G is a connected factor with all vertices of degree i (i=2,4,…,2s), where s?1 is an integer. In this paper, we show that every supereulerian K_1,s-free graph (s?2) contains a connected even [2,2s-2]-factor, hereby generalizing the result that every 4-connected claw-free graph has a connected [2,4]-factor by Broersma, Kriesell and Ryjacek.     

Independent domination in triangle-free graphs

Let G be a simple graph of order n and minimum degree δ. The independent domination numberi(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. We establish upper bounds, as functions of n and δ?n/2, for the independent domination number of triangle-free graphs, and over part of the range achieve best possible results.     

Characterization of self-complementary graphs with 2-factors

Let G be a self-complementary graph (s.c.) and π its degree sequence. Then G has a 2-factor if and only if π - 2 is graphic. This is achieved by obtaining a structure theorem regarding s.c. graphs without a 2-factor. Another interesting corollary of the structure theorem is that if G is a s.c. graph of order p?8 with minimum degree at least $\text{p}\text{4}$, then G has a 2-factor and the result is the best possible.     

Closure, stability and iterated line graphs with a 2-factor

We consider 2-factors with a bounded number of components in the n-times iterated line graph Lⁿ(G). We first give a characterization of graph G such that Lⁿ(G) has a 2-factor containing at most k components, based on the existence of a certain type of subgraph in G. This generalizes the main result of [L. Xiong, Z. Liu, Hamiltonian iterated line graphs, Discrete Math. 256 (2002) 407-422]. We use this result to show that the minimum number of components of 2-factors in the iterated line graphs Lⁿ(G) is stable under the closure operation on a claw-free graph G. This extends results in [Z. Ryjá?ek, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217-224; Z. Ryjá?ek, A. Saito, R.H. Schelp, Closure, 2-factors and cycle coverings in claw-free graphs, J. Graph Theory 32 (1999) 109-117; L. Xiong, Z. Ryjá?ek, H.J. Broersma, On stability of the hamiltonian index under contractions and closures, J. Graph Theory 49 (2005) 104-115].     

The structure of even factors in claw-free graphs

Recently, Jackson and Yoshimoto proved that every bridgeless simple graph G with δ(G)≥3 has an even factor in which every component has order at least four, which strengthens a classical result of Petersen. In this paper, we give a strengthening of the above result and show that the above graphs have an even factor in which every component has order at least four that does not contain any given edge. We also extend the above result to the graphs with minimum degree at least three such that all bridges lie in a common path and to the bridgeless graphs that have at most two vertices of degree two respectively. Finally we use this extended result to show that every simple claw-free graph G of order n with δ(G)≥3 has an even factor with at most components. The upper bound is best possible.     

Computing sharp 2-factors in claw-free graphs

In a previous paper we obtained an upper bound for the minimum number of components of a 2-factor in a claw-free graph. This bound is sharp in the sense that there exist infinitely many claw-free graphs for which the bound is tight. In this paper we extend these results by presenting a polynomial algorithm that constructs a 2-factor of a claw-free graph with minimum degree at least four whose number of components meets this bound. As a byproduct we show that the problem of obtaining a minimum 2-factor (if it exists) is polynomially solvable for a subclass of claw-free graphs. As another byproduct we give a short constructive proof for a result of Ryjá?ek, Saito and Schelp.     

Even subgraphs of bridgeless graphs and 2-factors of line graphs

By Petersen's theorem, a bridgeless cubic multigraph has a 2-factor. Fleischner generalised this result to bridgeless multigraphs of minimum degree at least three by showing that every such multigraph has a spanning even subgraph. Our main result is that every bridgeless simple graph with minimum degree at least three has a spanning even subgraph in which every component has at least four vertices. We deduce that if G is a simple bridgeless graph with n vertices and minimum degree at least three, then its line graph has a 2-factor with at most max{1,(3n-4)/10} components. This upper bound is best possible.     

Closure, 2-factors,and cycle coverings in claw-free graphs

In this article, we study cycle coverings and 2-factors of a claw-free graph and those of its closure, which has been defined by the first author (On a closure concept in claw-free graphs, J Combin Theory Ser B 70 (1997), 217–224). For a claw-free graph G and its closure cl(G), we prove: (1) V(G) is covered by k cycles in G if and only if V(cl(G)) is covered by k cycles of cl(G); and (2) G has a 2-factor with at most k components if and only if cl(G) has a 2-factor with at most k components. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 109–117, 1999     

Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs

A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. The clique-transversal number and clique-independence number of G are the sizes of a minimum clique-transversal and a maximum clique-independent set of G, respectively. A graph G is clique-perfect if these two numbers are equal for every induced subgraph of G. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. In this paper, we present a partial result in this direction; that is, we characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs.     

Sharp Upper Bounds on the Minimum Number of Components of 2-factors in Claw-free Graphs

Let G be a claw-free graph with order n and minimum degree δ. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If δ = 4, then G has a 2-factor with at most (5n − 14)/18 components, unless G belongs to a finite class of exceptional graphs. If δ ≥ 5, then G has a 2-factor with at most (n − 3)/(δ − 1) components, unless G is a complete graph. These bounds are best possible in the sense that we cannot replace 5/18 by a smaller quotient and we cannot replace δ − 1 by δ, respectively.     

Closure operation for even factors on claw-free graphs

Ryjá?ek (1997) [6] defined a powerful closure operation on claw-free graphs G. Very recently, Ryjá?ek et al. (2010) [8] have developed the closure operation on claw-free graphs which preserves the (non)-existence of a 2-factor. In this paper, we introduce a closure operation on claw-free graphs that generalizes the above two closure operations. The closure of a graph is unique determined and the closure turns a claw-free graph into the line graph of a graph containing no cycle of length at most 5 and no cycles of length 6 satisfying a certain condition and no induced subgraph being isomorphic to the unique tree with a degree sequence 111133. We show that these closure operations on claw-free graphs all preserve the minimum number of components of an even factor. In particular, we show that a claw-free graph G has an even factor with at most k components if and only if (, respectively) has an even factor with at most k components. However, the closure operation does not preserve the (non)-existence of a 2-factor.     

Paired-Domination in Claw-Free Graphs

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number, denoted by γ _pr (G), is the minimum cardinality of a paired-dominating set in G. In this paper we investigate the paired-domination number in claw-free graphs. Specifically, we show that γ _pr (G) ≤ (3n ? 1)/5 if G is a connected claw-free graph of order n with minimum degree at least three and that this bound is sharp.     

On 2-factors with k components

In this paper we study the minimum degree condition for a Hamiltonian graph to have a 2-factor with k components. By proving a conjecture of Faudree et al. [A note on 2-factors with two components, Discrete Math. 300 (2005) 218-224] we show the following. There exists a real number ε>0 such that for every integer k?2 there exists an integer n₀=n₀(k) such that every Hamiltonian graph G of order n?n₀ with has a 2-factor with k components.     

Minimum degree, leaf number and traceability

Let G be a finite connected graph with minimum degree δ. The leaf number L(G) of G is defined as the maximum number of leaf vertices contained in a spanning tree of G. We prove that if δ ? 1/2 (L(G) + 1), then G is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if δ ? 1/2 (L(G) + 1), then G contains a spanning path. This provides a partial solution to a conjecture of the computer program Graffiti.pc [DeLaViña and Waller, Spanning trees with many leaves and average distance, Electron. J. Combin. 15 (2008), 1–16]. For G claw-free, we show that if δ ? 1/2 (L(G) + 1), then G is Hamiltonian. This again confirms, and even improves, the conjecture of Graffiti.pc for this class of graphs.     

Bounds on total domination in claw-free cubic graphs

A set S of vertices in a graph G is a total dominating set, denoted by TDS, of G if every vertex of G is adjacent to some vertex in S (other than itself). The minimum cardinality of a TDS of G is the total domination number of G, denoted by γ_t(G). If G does not contain K_1,3 as an induced subgraph, then G is said to be claw-free. It is shown in [D. Archdeacon, J. Ellis-Monaghan, D. Fischer, D. Froncek, P.C.B. Lam, S. Seager, B. Wei, R. Yuster, Some remarks on domination, J. Graph Theory 46 (2004) 207-210.] that if G is a graph of order n with minimum degree at least three, then γ_t(G)?n/2. Two infinite families of connected cubic graphs with total domination number one-half their orders are constructed in [O. Favaron, M.A. Henning, C.M. Mynhardt, J. Puech, Total domination in graphs with minimum degree three, J. Graph Theory 34(1) (2000) 9-19.] which shows that this bound of n/2 is sharp. However, every graph in these two families, except for K₄ and a cubic graph of order eight, contains a claw. It is therefore a natural question to ask whether this upper bound of n/2 can be improved if we restrict G to be a connected cubic claw-free graph of order at least 10. In this paper, we answer this question in the affirmative. We prove that if G is a connected claw-free cubic graph of order n?10, then γ_t(G)?5n/11.     

Tank-Ring Factors in Supereulerian Claw-Free Graphs

A graph G has a tank-ring factor F if F is a connected spanning subgraph with all vertices of degree 2 or 4 that consists of one cycle C and disjoint triangles attaching to exactly one vertex of C such that every component of G ? C contains exactly two vertices. In this paper, we show the following results. (1) Every supereulerian claw-free graph G with 1-hourglass property contains a tank-ring factor. (2) Every supereulerian claw-free graph with 2-hourglass property is Hamiltonian.     

Upper bounds for independent domination in regular graphs

Let G be a regular graph of order n and degree δ. The independent domination numberi(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. We establish upper bounds, as functions of n and δ, for the sum and product of the independent domination numbers of a regular graph and its complement.     

Total domination in claw-free graphs with minimum degree 2

A set S of vertices in a graph G is a total dominating set (TDS) of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a TDS of G is the total domination number of G, denoted by γ_t(G). A graph is claw-free if it does not contain K_1,3 as an induced subgraph. It is known [M.A. Henning, Graphs with large total domination number, J. Graph Theory 35(1) (2000) 21-45] that if G is a connected graph of order n with minimum degree at least two and G∉{C₃,C₅, C₆, C₁₀}, then γ_t(G)?4n/7. In this paper, we show that this upper bound can be improved if G is restricted to be a claw-free graph. We show that every connected claw-free graph G of order n and minimum degree at least two satisfies γ_t(G)?(n+2)/2 and we characterize those graphs for which γ_t(G)=⌊(n+2)/2⌋.     

2‐ and 3‐factors of graphs on surfaces

It has been conjectured that any 5‐connected graph embedded in a surface Σ with sufficiently large face‐width is hamiltonian. This conjecture was verified by Yu for the triangulation case, but it is still open in general. The conjecture is not true for 4‐connected graphs. In this article, we shall study the existence of 2‐ and 3‐factors in a graph embedded in a surface Σ. A hamiltonian cycle is a special case of a 2‐factor. Thus, it is quite natural to consider the existence of these factors. We give an evidence to the conjecture in a sense of the existence of a 2‐factor. In fact, we only need the 4‐connectivity with minimum degree at least 5. In addition, our face‐width condition is not huge. Specifically, we prove the following two results. Let G be a graph embedded in a surface Σ of Euler genus g.

• (1) If G is 4‐connected and minimum degree of G is at least 5, and furthermore, face‐width of G is at least 4g?12, then G has a 2‐factor.
• (2) If G is 5‐connected and face‐width of G is at least max{44g?117, 5}, then G has a 3‐factor.

The connectivity condition for both results are best possible. In addition, the face‐width conditions are necessary too. Copyright © 2010 Wiley Periodicals, Inc. J Graph Theory 67:306‐315, 2011