The maximum weight independent set problem (WIS), which is known to be generally NP-hard, admits polynomial-time solutions when restricted to graphs in some special classes. In particular, due to the celebrated Edmonds' matching algorithm , WIS is solvable in polynomial time in the class of line graphs. This solution was extended to claw-free graphs and then further to fork-free graphs and to t claw-free graphs, where t claw is the graph consisting of t disjoint copies of the claw. The solution for t claw-free graphs was obtained by generalizing Farber's approach to solve the problem for t K 2 -free graphs. In the present paper, we elaborate this approach further to develop a polynomial-time algorithm to solve the problem in the class of fork+ t claw-free graphs, generalizing both fork-free graphs and t claw-free graphs, and in the class of P 5 + t claw-free graphs. We then apply the latter result to solve the more general problem of finding a d -regular induced subgraph of maximum weight in the class of P 5 + t P 3 -free graphs in polynomial time for any natural d and t , extending some of the previously known solutions.

Let G=(V,E) be a finite undirected graph. An edge set E′⊆E is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of E′. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G; this problem is also known as the Efficient Edge Domination problem; it is the Efficient Domination problem for line graphs. The DIM problem is NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but is solvable in polynomial time for P9-free graphs [and in linear time for P7-free graphs] as well as for S1,2,4-free, for S2,2,2-free, and for S2,2,3-free graphs. In this paper, combining two distinct approaches, we solve it in polynomial time for P10-free graphs and introduce a partial result for the general case.

In a finite undirected graph $G=(V,E)$, a vertex $v \in V$ dominates itself and its neighbors in $G$. A vertex set $D \subseteq V$ is an efficient dominating set (e.d.s. for short) of $G$ if every $v \in V$ is dominated in $G$ by exactly one vertex of $D$. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in $G$, is known to be NP-complete for $P_7$-free graphs and solvable in polynomial time for $P_5$-free graphs. The $P_6$-free case was the last open question for the complexity of ED on $F$-free graphs. Recently, Lokshtanov, Pilipczuk, and van Leeuwen showed that weighted ED is solvable in polynomial time for $P_6$-free graphs, based on their quasi-polynomial algorithm for the Maximum Weight Independent Set problem for $P_6$-free graphs. Independently, by a direct approach which is simpler and faster, we found an ${\cal O}(n^5 m)$ time solution for weighted ED on $P_6$-free graphs. Moreover, we show that weighted ED is solvable in linear time for $P_5$-free graphs which solves another open question for the complexity of (weighted) ED. The result for $P_5$-free graphs is based on modular decomposition.

We present the first polynomial-time algorithm to solve the maximum weight independent set problem for apple-free graphs, which is a common generalization of several important classes where the problem can be solved efficiently, such as claw-free graphs, chordal graphs, and cographs. Our solution is based on a combination of two algorithmic techniques (modular decomposition and decomposition by clique separators) and a deep combinatorial analysis of the structure of apple-free graphs. Our algorithm is robust in the sense that it does not require the input graph G to be apple-free; the algorithm either finds an independent set of maximum weight in G or reports that G is not apple-free.

A graph G is the k-leaf power of a tree T if its vertices are leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most k . Then T is a k-leaf root of G . This notion was introduced and studied by Nishimura, Ragde, and Thilikos [2002], motivated by the search for underlying phylogenetic trees. Their results imply an O ( n 3 )-time recognition algorithm for 4-leaf powers. Recently, Rautenbach [2006] as well as Dom et al. [2005] characterized 4-leaf powers without true twins in terms of forbidden subgraphs. We give new characterizations for 4-leaf powers and squares of trees by a complete structural analysis. As a consequence, we obtain a conceptually simple linear-time recognition of 4-leaf powers.

Two graphs G and H with the same vertex set Vare P 4 -isomorphic if every four vertices {a,b,c,d} \subseteq V$ induce a chordless path (denoted by P 4 ) in G if and only if they induce a P 4 in H. We call a graph split-perfect if it is P 4 -isomorphic to a split graph (i.e., a graph being partitionable into a clique and a stable set). This paper characterizes the new class of split-perfect graphs using the concepts of homogeneous sets and p-connected graphs and leads to a linear time recognition algorithm for split-perfect graphs, as well as efficient algorithms for classical optimization problems on split-perfect graphs based on the primeval decomposition of graphs. The optimization results considerably extend previous ones on smaller classes such as P 4 --sparse graphs, P 4 -lite graphs, P 4 --laden graphs, and (7,3)-graphs. Moreover, split-perfect graphs form a new subclass of brittle graphs containing the superbrittle graphs for which a new characterization is obtained leading to linear time recognition.

We prove that claw-free graphs, containing an induced dominating path, have a Hamiltonian path, and that 2-connected claw-free graphs, containing an induced doubly dominating cycle or a pair of vertices such that there exist two internally disjoint induced dominating paths connecting them, have a Hamiltonian cycle. As a consequence, we obtain linear time algorithms for both problems if the input is restricted to (claw,net)-free graphs. These graphs enjoy those interesting structural properties.

It is well known that chordal graphs can be characterized via m-convexity. In this paper we introduce the notion of m 3 -convexity (a relaxation of m-convexity) which is closely related to semisimplicial ordering of graphs. We present new characterizations of HHD-free graphs via m 3 -convexity and obtain some results known from [B. Jamison and S. Olariu, Adv. Appl. Math., 9 (1988), pp. 364--376] as corollaries. Moreover, we characterize weak bipolarizable graphs as the graphs for which the family of all m 3 -convex sets is a convex geometry. As an application of our results we present a simple efficient criterion for deciding whether a HHD-free graph contains a r-dominating clique with respect to a given vertex radius function r.

A distance-hereditary graph is a connected graph in which every induced path is isometric, i.e., the distance of any two vertices in an induced path equals their distance in the graph. We present a linear time labeling algorithm for the minimum cardinality connected r-dominating set and Steiner tree problems on distance-hereditary graphs. © 1998 John Wiley & Sons, Inc. Networks 31: 177–182, 1998

Recently in several papers, graphs with maximum neighborhood orderings were characterized and turned out to be algorithmically useful. This paper gives a unified framework for characterizations of those graphs in terms of neighborhood and clique hypergraphs which have the Helly property and whose line graph is chordal. These graphs are dual (in the sense of hypergraphs) to chordal graphs. By using the hypergraph approach in a systematical way new results are obtained, some of the old results are generalized, and some of the proofs are simplified.

Let $\cal C$ be a family of cliques of a graph G=(V,E). Suppose that each clique C of $\cal C$ is associated with an integer r(C)$, where $r(C) \ge 0$. A vertex vr-dominates a clique C of G if $d(v,x) \le r(C)$ for all $x \in C$, where d(v,x) is the standard graph distance. A subset $D \subseteq V$ is a clique r-dominating set of G if for every clique $C \in \cal C$ there is a vertex $u \in D$ which r-dominates C. A clique r-packing set is a subset $P \subseteq \cal C$ such that there are no two distinct cliques $C',C'\in P$ r-dominated by a common vertex of G. The clique r-domination problem is to find a clique r-dominating set with minimum size and the clique r-packing problem is to find a clique r-packing set with maximum size. The formulated problems include many domination and clique-transversal-related problems as special cases. In this paper an efficient algorithm is proposed for solving these problems on dually chordal graphswhich are a natural generalization of strongly chordal graphs. The efficient algorithm is mainly based on the tree structure and special vertex elimination orderings of dually chordal graphs. In some important particular cases where the algorithm works in linear time the obtained results generalize and improve known results on strongly chordal graphs.