2-factors in claw-free graphs

Guantao Chen; Jill R. Faudree; Ronald J. Gould; Akira Saito

Displaying similar documents to “2-factors in claw-free graphs”

On traceability and 2-factors in claw-free graphs

Dalibor Fronček, Zdeněk Ryjáček, Zdzisław Skupień (2004)

Discussiones Mathematicae Graph Theory

Similarity:

If G is a claw-free graph of sufficiently large order n, satisfying a degree condition σₖ > n + k² - 4k + 7 (where k is an arbitrary constant), then G has a 2-factor with at most k - 1 components. As a second main result, we present classes of graphs ₁,...,₈ such that every sufficiently large connected claw-free graph satisfying degree condition σ₆(k) > n + 19 (or, as a corollary, δ(G) > (n+19)/6) either belongs to $⋃ ⁸_{i = 1} i$ or is traceable.

On graphs G for which both g and G̅ are claw-free

Shinya Fujita (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph with |V(G)| ≥ 10. We prove that if both G and G̅ are claw-free, then minΔ(G), Δ(G̅) ≤ 2. As a generalization of this result in the case where |V(G)| is sufficiently large, we also prove that if both G and G̅ are $K_{1, t}$ -free, then minΔ(G),Δ(G̅) ≤ r(t- 1,t)-1 where r(t-1,t) is the Ramsey number.

A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs

Wojciech Wideł (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies [...] min⁡dG(u),dG(v)≥n+12 $min {d_{G} (u), d_{G} (v)} \geq \frac{n + 1}{2}$ . In this paper we prove that every 2-connected K1,3, P5-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying...

The structure and existence of 2-factors in iterated line graphs

Michael Ferrara, Ronald J. Gould, Stephen G. Hartke (2007)

Discussiones Mathematicae Graph Theory

Similarity:

We prove several results about the structure of 2-factors in iterated line graphs. Specifically, we give degree conditions on G that ensure L²(G) contains a 2-factor with every possible number of cycles, and we give a sufficient condition for the existence of a 2-factor in L²(G) with all cycle lengths specified. We also give a characterization of the graphs G where $L^{k} (G)$ contains a 2-factor.

Remarks on partially square graphs, hamiltonicity and circumference

Hamamache Kheddouci (2001)

Discussiones Mathematicae Graph Theory

Similarity:

Given a graph G, its partially square graph G* is a graph obtained by adding an edge (u,v) for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition $N_{G} (x) \subseteq N_{G} [u] \cup N_{G} [v]$ , where $N_{G} [x] = N_{G} (x) \cup x$ . In the case where G is a claw-free graph, G* is equal to G². We define $σ ° ₜ = m i n \sum_{x \in S} d_{G} (x) : S i s a n i n d e p e n d e n t s e t i n G * a n d | S | = t$ . We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.

Colouring graphs with prescribed induced cycle lengths

Bert Randerath, Ingo Schiermeyer (2001)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we study the chromatic number of graphs with two prescribed induced cycle lengths. It is due to Sumner that triangle-free and P₅-free or triangle-free, P₆-free and C₆-free graphs are 3-colourable. A canonical extension of these graph classes is $^{I} (4, 5)$ , the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of $^{I} (4, 5)$ are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind,...

On perfect and unique maximum independent sets in graphs

Lutz Volkmann (2004)

Mathematica Bohemica

Similarity:

A perfect independent set $I$ of a graph $G$ is defined to be an independent set with the property that any vertex not in $I$ has at least two neighbors in $I$ . For a nonnegative integer $k$ , a subset $I$ of the vertex set $V (G)$ of a graph $G$ is said to be $k$ -independent, if $I$ is independent and every independent subset $I^{'}$ of $G$ with $| I^{'} | \geq | I | - (k - 1)$ is a subset of $I$ . A set $I$ of vertices of $G$ is a super $k$ -independent set of $G$ if $I$ is $k$ -independent in the graph $G [I, V (G) - I]$ , where $G [I, V (G) - I]$ is the bipartite graph obtained from $G$ by deleting...

4-cycle properties for characterizing rectagraphs and hypercubes

Khadra Bouanane, Abdelhafid Berrachedi (2017)

Czechoslovak Mathematical Journal

Similarity:

A $(0, 2)$ -graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of $(0, λ)$ -graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free $(0, 2)$ -graph. $(0, 2)$ -graphs include hypercubes, folded cube graphs and some particular graphs such as icosahedral graph, Shrikhande graph, Klein graph, Gewirtz graph, etc. In this paper, we give some local properties of 4-cycles in $(0, λ)$ -graphs and more specifically...

Stable sets for $(P ₆, K_{2, 3})$ -free graphs

Raffaele Mosca (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for $(P ₆, K_{2, 3})$ -free graphs in polynomial time, extending some known results.

Pairs of forbidden class of subgraphs concerning $K_{1, 3}$ and P₆ to have a cycle containing specified vertices

Takeshi Sugiyama, Masao Tsugaki (2009)

Discussiones Mathematicae Graph Theory

Similarity:

In [3], Faudree and Gould showed that if a 2-connected graph contains no $K_{1, 3}$ and P₆ as an induced subgraph, then the graph is hamiltonian. In this paper, we consider the extension of this result to cycles passing through specified vertices. We define the families of graphs which are extension of the forbidden pair $K_{1, 3}$ and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.

Chvátal's Condition cannot hold for both a graph and its complement

Alexandr V. Kostochka, Douglas B. West (2006)

Discussiones Mathematicae Graph Theory

Similarity:

Chvátal’s Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that $d_{i} > i$ or $d_{n - i} \geq n - i$ . We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.

Variations on a sufficient condition for Hamiltonian graphs

Ahmed Ainouche, Serge Lapiquonne (2007)

Discussiones Mathematicae Graph Theory

Similarity:

Given a 2-connected graph G on n vertices, let G* be its partially square graph, obtained by adding edges uv whenever the vertices u,v have a common neighbor x satisfying the condition $N_{G} (x) \subseteq N_{G} [u] \cup N_{G} [v]$ , where $N_{G} [x] = N_{G} (x) \cup x$ . In particular, this condition is satisfied if x does not center a claw (an induced $K_{1, 3}$ ). Clearly G ⊆ G* ⊆ G², where G² is the square of G. For any independent triple X = x,y,z we define σ̅(X) = d(x) + d(y) + d(z) - |N(x) ∩ N(y) ∩ N(z)|. Flandrin et al. proved that a 2-connected graph G is hamiltonian...

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by $γ_{r} (G)$ , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then $γ_{r} (U) \geq ⎡ n / 3 ⎤$ , and provide a characterization of graphs achieving this bound.

An upper bound on the basis number of the powers of the complete graphs

Salar Y. Alsardary (2001)

Czechoslovak Mathematical Journal

Similarity:

The basis number of a graph $G$ is defined by Schmeichel to be the least integer $h$ such that $G$ has an $h$ -fold basis for its cycle space. MacLane showed that a graph is planar if and only if its basis number is $\leq 2$ . Schmeichel proved that the basis number of the complete graph $K_{n}$ is at most $3$ . We generalize the result of Schmeichel by showing that the basis number of the $d$ -th power of $K_{n}$ is at most $2 d + 1$ .

Counterexample to a conjecture on the structure of bipartite partitionable graphs

Richard G. Gibson, Christina M. Mynhardt (2007)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is called a prism fixer if γ(G×K₂) = γ(G), where γ(G) denotes the domination number of G. A symmetric γ-set of G is a minimum dominating set D which admits a partition D = D₁∪ D₂ such that $V (G) - N [D_{i}] = D_{j}$ , i,j = 1,2, i ≠ j. It is known that G is a prism fixer if and only if G has a symmetric γ-set. Hartnell and Rall [On dominating the Cartesian product of a graph and K₂, Discuss. Math. Graph Theory 24 (2004), 389-402] conjectured that if G is a connected, bipartite graph such that V(G) can...