Equimatchable factor-critical graphs

A simple graph G(X, E) is factor-critical if the induced subgraph 〈X – x〉 admits a perfect matching for every vertex x of G. It is equimatchable if every maximal matching of G is maximum. The equimatchable non-factor-critical graphs have been studied by Lesk, Plummer, and Pulleyblank. In this paper, we study the equimatchable factor-critical graphs; in particular we show that if such a graph is two-connected, it is hamiltonian.     

Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs

A graph is called claw-free if it contains no induced subgraph isomorphic to K1,3. 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 C&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.     

Set graphs. I. Hereditarily finite sets and extensional acyclic orientations

A graph $G$ is said to be a set graph if it admits an acyclic orientation which is also extensional, in the sense that the out-neighborhoods of its vertices are pairwise distinct. Equivalently, a set graph is the underlying graph of the digraph representation of a hereditarily finite set.In this paper, we initiate the study of set graphs. On the one hand, we identify several necessary conditions that every set graph must satisfy. On the other hand, we show that set graphs form a rich class of graphs containing all connected claw-free graphs and all graphs with a Hamiltonian path. In the case of claw-free graphs, we provide a polynomial-time algorithm for finding an extensional acyclic orientation. Inspired by manipulations of hereditarily finite sets, we give simple proofs of two well-known results about claw-free graphs. We give a complete characterization of unicyclic set graphs, and point out two NP-complete problems closely related to the problem of recognizing set graphs. Finally, we argue that these three problems are solvable in linear time on graphs of bounded treewidth.     

3阶幂图的广义导出匹配可扩性

A graph G is induced matching extendable if every induced matching of G is included in a perfect matching of G. A graph G is generalized induced matching extendable if every induced matching of G is included in a maximum matching of G. A graph G is claw-free, if G dose not contain any induced subgraph isomorphic to K1,3. The k-th power of G, denoted by Gu, is the graph with vertex set V（G） in which two vertices are adjacent if and only if the distance between them is at most k in G. In this paper we show that, if the maximum matchings of G and G3 have the same cardinality, then G3 is generalized induced matching extendable. We also show that this result is best possible. As a result, we show that if G is a connected claw-flee graph, then G3 is generalized induced matching extendable.     

Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n ? 2. These conditions are best possible. A related conjecture also is proposed.     

Claw-free graphs. III. Circular interval graphs

Construct a graph as follows. Take a circle, and a collection of intervals from it, no three of which have union the entire circle; take a finite set of points V from the circle; and make a graph with vertex set V in which two vertices are adjacent if they both belong to one of the intervals. Such graphs are “long circular interval graphs,” and they form an important subclass of the class of all claw-free graphs. In this paper we characterize them by excluded induced subgraphs. This is a step towards the main goal of this series, to find a structural characterization of all claw-free graphs.This paper also gives an analysis of the connected claw-free graphs G with a clique the deletion of which disconnects G into two parts both with at least two vertices.     

直径不超过2的2连通无爪图是哈密顿图

不包含2K_2的图是指不包含一对独立边作为导出子图的图.Kriesell证明了所有4连通的无爪图的线图是哈密顿连通的.本文证明了如果图G不包含2K_2并且不同构与K_2,P_3和双星图,那么线图L(G)是哈密顿图,进一步应用由Ryjá(?)ek引入的闭包的概念,给出了直径不超过2的2连通无爪图是哈密顿图这个定理的新的证明方法.     

Equimatchable Regular Graphs

A graph is called equimatchable if all of its maximal matchings have the same size. Kawarabayashi, Plummer, and Saito showed that the only connected equimatchable 3‐regular graphs are K₄ and K_{3, 3}. We extend this result by showing that for an odd positive integer r, if G is a connected equimatchable r‐regular graph, then . Also it is proved that for an even r, a connected triangle‐free equimatchable r‐regular graph is isomorphic to one of the graphs C₅, C₇, and .     

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).     

2-连通无爪图的连通因子

若图G不含有同构于K1,3的导出子图,则称G为一个无爪图.令a和b是两个整数满足2≤a≤b.本文证明了若G是一个含有[a,b]因子的2连通无爪图,则G有一个连通的[a,b 1]因子.     

Closure concept for 2-factors in claw-free graphs

We introduce a closure concept for 2-factors in claw-free graphs that generalizes the closure introduced by the first author. The 2-factor closure of a graph is uniquely determined and the closure operation turns a claw-free graph into the line graph of a graph containing no cycles of length at most 5 and no cycles of length 6 satisfying a certain condition. A graph has a 2-factor if and only if its closure has a 2-factor; however, the closure operation preserves neither the minimum number of components of a 2-factor nor the hamiltonicity or nonhamiltonicity of a graph.     

Almost claw-free graphs

We say that G is almost claw-free if the vertices that are centers of induced claws (K_1,3) in G are independent and their neighborhoods are 2-dominated. Clearly, every claw-free graph is almost claw-free. It is shown that (i) every even connected almost claw-free graph has a perfect matching and (ii) every nontrivial locally connected K_1,4-free almost claw-free graph is fully cycle extendable.     

P3-支配图哈密尔顿性的两个充分条件

在文献[3]中介绍了一个新的图类-P3-支配图.这个图类包含所有的拟无爪图,因此也包含所有的无爪图.在本文中,我们证明了每一个点数至少是3的三角形连通的P3-支配图是哈密尔顿的,但有一个例外图K1,1,3.同时,我们也证明了k-连通的(k≥2)的P3-支配图是哈密尔顿的,如果an(G)≤k,但有两个例外图K1,1,3 and K2,3.     

Bounding the Size of Equimatchable Graphs of Fixed Genus

A graph G is said to be equimatchable if every matching in G extends to (i.e., is a subset of) a maximum matching in G. In an earlier paper with Saito, the authors showed that there are only a finite number of 3-connected equimatchable planar graphs. In the present paper, this result is extended by showing that in a surface of any fixed genus (orientable or non-orientable), there are only a finite number of 3-connected equimatchable graphs having a minimal embedding of representativity at least three. (In fact, if the graphs considered are non-bipartite, the representativity three hypothesis may be dropped.) The proof makes use of the Gallai-Edmonds decomposition theorem for matchings.      

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.     

A new closure concept preserving graph Hamiltonicity and based on neighborhood equivalence

A graph is Hamiltonian if it contains a cycle which goes through all vertices exactly once. Determining if a graph is Hamiltonian is known as an NP-complete problem, and no satisfactory characterization for these graphs has been found.In 1976, Bondy and Chvàtal introduced a way to get round the Hamiltonicity problem complexity by using a closure of the graph. This closure is a supergraph of G which is Hamiltonian iff G is. In particular, if the closure is the complete graph, then G is Hamiltonian. Since this seminal work, several closure concepts preserving Hamiltonicity have been introduced. In particular, in 1997, Ryjá?ek defined a closure concept for claw-free graphs based on local completion.Following a different approach, in 1974, Goodman and Hedetniemi gave a sufficient condition for Hamiltonicity based on the existence of a clique covering of the graph. This condition was recently generalized using the notion of Eulerian clique covering. In this context, closure concepts based on local completion are interesting since the closure of a graph contains more simplicial vertices than the graph itself, making the search for a clique covering easier.In this article, we introduce a new closure concept based on local completion which preserves the Hamiltonicity for every graph. Note that, moreover, the closure may be claw free even when the graph is not.     

导出匹配问题的NP-完全性以及导出匹配可扩问题的CO-NP-完全性

图Ｇ的一个匹配Ｍ是导出的,若Ｍ是图Ｇ的一个导出子图。图Ｇ是导邮匹配可扩的（简记ＩＭ－可扩的）,若图Ｇ的任一导出匹配均含于图Ｇ的一个完美匹配当中。本文我们将证明如下结果。⑴对无爪图而言,问题“给定图Ｇ以及一个正整数ｒ,确定是否存在图Ｇ的一个导出匹配Ｍ使得Ｍ≥ｒ”是ＮＰ－完全的。⑵对直径为２的图以及直径为３的偶图,问题“确定一个给定图是否为导出匹配可扩的”是ＣＯ－ＮＰ完全的;而对完全多部图而言,问题“     

On claw-free t-perfect graphs

A graph is called t-perfect, if its stable set polytope is defined by non-negativity, edge and odd-cycle inequalities. We characterise the class of all claw-free t-perfect graphs by forbidden t-minors, and show that they are 3-colourable. Moreover, we determine the chromatic number of claw-free h-perfect graphs and give a polynomial-time algorithm to compute an optimal colouring.     

Partial Characterizations of Circular-Arc Graphs

A circular-arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular-arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to the following classes: diamond-free graphs, P₄-free graphs, paw-free graphs, and claw-free chordal graphs.