Characterizations for co-graphs defined by restricted NLC-width or clique-width operations

In this paper we characterize subclasses of co-graphs defined by restricted NLC-width operations and subclasses of co-graphs defined by restricted clique-width operations.We show that a graph has NLCT-width 1 if and only if it is (C₄,P₄)-free. Since (C₄,P₄)-free graphs are exactly trivially perfect graphs, the set of graphs of NLCT-width 1 is equal to the set of trivially perfect graphs, and a recursive definition for trivially perfect graphs follows. Further we show that a graph has linear NLC-width 1 if and only if is (C₄,P₄,2K₂)-free. This implies that the set of graphs of linear NLC-width 1 is equal to the set of threshold graphs.We also give forbidden induced subgraph characterizations for co-graphs defined by restricted clique-width operations using P₄, 2K₂, and co-2P₃.     

On retracts,absolute retracts,and foldings in cographs

A retract of a graph G is an induced subgraph H of G such that there exists a homomorphism \(\rho :G \rightarrow H\). When both G and H are cographs, we show that the problem to determine whether H is a retract of G is NP-complete; moreover, we show that this problem on cographs is fixed-parameter tractable when parameterized by the size of H. When restricted to the class of threshold graphs or to the class of trivially perfect graphs, the retract problem becomes tractable in polynomial time. The retract problem is also solvable in linear time when one cograph is given as an induced subgraph of the other. We characterize absolute retracts for the class of cographs. Foldings generalize retractions. We show that the problem to fold a trivially perfect graph onto a largest possible clique is NP-complete.     

On forcing matching number of boron-nitrogen fullerene graphs

Let G be a graph that admits a perfect matching M. A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G. The smallest cardinality of forcing sets of M is called the forcing number of M. Computing the minimum forcing number of perfect matchings of a graph is an NP-complete problem. In this paper, we consider boron-nitrogen (BN) fullerene graphs, cubic 3-connected plane bipartite graphs with exactly six square faces and other hexagonal faces. We obtain the forcing spectrum of tubular BN-fullerene graphs with cyclic edge-connectivity 3. Then we show that all perfect matchings of any BN-fullerene graphs have the forcing number at least two. Furthermore, we mainly construct all seven BN-fullerene graphs with the minimum forcing number two.     

New conjectures on perfect matchings in cubic graphs

We propose three new conjectures on perfect matchings in cubic graphs. The weakest conjecture is implied by a well-known conjecture of Berge and Fulkerson. The other two conjectures are a strengthening of the first one. All conjectures are trivially verified for 3-edge-colorable cubic graphs and by computer for all snarks of order at most 34.     

On the Choosability of Claw-Free Perfect Graphs

It has been conjectured that for every claw-free graph G the choice number of G is equal to its chromatic number. We focus on the special case of this conjecture where G is perfect. Claw-free perfect graphs can be decomposed via clique-cutset into two special classes called elementary graphs and peculiar graphs. Based on this decomposition we prove that the conjecture holds true for every claw-free perfect graph with maximum clique size at most 4.     

A new lower bound on the number of trivially noncontractible edges in contraction critical 5-connected graphs

An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. An edge of a k-connected graph is called trivially noncontractible if its two end vertices have a common neighbor of degree k. Ando [K. Ando, Trivially noncontractible edges in a contraction critically 5-connected graph, Discrete Math. 293 (2005) 61-72] proved that a contraction critical 5-connected graph on n vertices has at least n/2 trivially noncontractible edges. Li [Xiangjun Li, Some results about the contractible edge and the domination number of graphs, Guilin, Guangxi Normal University, 2006 (in Chinese)] improved the lower bound to n+1. In this paper, the bound is improved to the statement that any contraction critical 5-connected graph on n vertices has at least trivially noncontractible edges.     

Forcing matching numbers of fullerene graphs

The forcing number or the degree of freedom of a perfect matching M of a graph G is the cardinality of the smallest subset of M that is contained in no other perfect matchings of G. In this paper we show that the forcing numbers of perfect matchings in a fullerene graph are not less than 3 by applying the 2-extendability and cyclic edge-connectivity 5 of fullerene graphs obtained recently, and Kotzig’s classical result about unique perfect matching as well. This lower bound can be achieved by infinitely many fullerene graphs.     

Construction for bicritical graphs and k-extendable bipartite graphs

A graph G is said to be bicritical if G-u-v has a perfect matching for every choice of a pair of points u and v. Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least 2k+2 points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an O(mn) algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G.     

Perfect matchings after vertex deletions

This paper considers some classes of graphs which are easily seen to have many perfect matchings. Such graphs can be considered robust with respect to the property of having a perfect matching if under vertex deletions (with some mild restrictions), the resulting subgraph continues to have a perfect matching. It is clear that you can destroy the property of having a perfect matching by deleting an odd number of vertices, by upsetting a bipartition or by deleting enough vertices to create an odd component. One class of graphs we consider is the m×m lattice graph (or grid graph) for m even. Matchings in such grid graphs correspond to coverings of an m×m checkerboard by dominoes. If in addition to the easy conditions above, we require that the deleted vertices be apart, the resulting graph has a perfect matching. The second class of graphs we consider is a k-fold product graph consisting of k copies of a given graph G with the ith copy joined to the i+1st copy by a perfect matching joining copies of the same vertex. We show that, apart from some easy restrictions, we can delete any vertices from the kth copy of G and find a perfect matching in the product graph with k suitably large.     

Neighborhood perfect graphs

The notion of neighborhood perfect graphs is introduced here as follows. Let G be a graph, α_N(G) denote the maximum number of edges such that no two of them belong to the same subgraph of G induced by the (closed) neighborhood of some vertex; let ϱ_N(G) be the minimum number of vertices whose neighborhood subgraph cover the edge set of G. Then G is called neighborhood perfect if ϱ_N(G′) = α_N(G′) holds for every induced subgraph G′ of G. It is expected that neighborhood perfect graphs are perfect also in the sense of Berge. We characterized here those chordal graphs which are neighborhood perfect. In addition, an algorithm to computer ϱ_N(G) = α_N(G) is given for interval graphs.     

Triangle-free strongly circular-perfect graphs

Zhu [X. Zhu, Circular-perfect graphs, J. Graph Theory 48 (2005) 186-209] introduced circular-perfect graphs as a superclass of the well-known perfect graphs and as an important χ-bound class of graphs with the smallest non-trivial χ-binding function χ(G)≤ω(G)+1. Perfect graphs have been recently characterized as those graphs without odd holes and odd antiholes as induced subgraphs [M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Ann. Math. (in press)]; in particular, perfect graphs are closed under complementation [L. Lovász, Normal hypergraphs and the weak perfect graph conjecture, Discrete Math. 2 (1972) 253-267]. To the contrary, circular-perfect graphs are not closed under complementation and the list of forbidden subgraphs is unknown.We study strongly circular-perfect graphs: a circular-perfect graph is strongly circular-perfect if its complement is circular-perfect as well. This subclass entails perfect graphs, odd holes, and odd antiholes. As the main result, we fully characterize the triangle-free strongly circular-perfect graphs, and prove that, for this graph class, both the stable set problem and the recognition problem can be solved in polynomial time.Moreover, we address the characterization of strongly circular-perfect graphs by means of forbidden subgraphs. Results from [A. Pêcher, A. Wagler, On classes of minimal circular-imperfect graphs, Discrete Math. (in press)] suggest that formulating a corresponding conjecture for circular-perfect graphs is difficult; it is even unknown which triangle-free graphs are minimal circular-imperfect. We present the complete list of all triangle-free minimal not strongly circular-perfect graphs.     

Eliminating graphs by means of parallel knock-out schemes

In 1997 Lampert and Slater introduced parallel knock-out schemes, an iterative process on graphs that goes through several rounds. In each round of this process, every vertex eliminates exactly one of its neighbors. The parallel knock-out number of a graph is the minimum number of rounds after which all vertices have been eliminated (if possible). The parallel knock-out number is related to well-known concepts like perfect matchings, hamiltonian cycles, and 2-factors.We derive a number of combinatorial and algorithmic results on parallel knock-out numbers: for families of sparse graphs (like planar graphs or graphs of bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices; this bound is basically tight for trees. Furthermore, there is a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and we show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach (whereas in general graphs this problem is known to be NP-hard). Finally, we prove that the parallel knock-out number of a claw-free graph is either infinite or less than or equal to 2.     

Bounds on the forcing numbers of bipartite graphs

The forcing number of a perfect matching M of a graph G is the cardinality of the smallest subset of M that is contained in no other perfect matching of G. In this paper, we demonstrate several techniques to produce upper bounds on the forcing number of bipartite graphs. We present a simple method of showing that the maximum forcing number on the 2m×2n rectangle is mn, and show that the maximum forcing number on the 2m×2n torus is also mn. Further, we investigate the lower bounds on the forcing number and determine the conditions under which a previously formulated lower bound is sharp; we provide an example of a family of graphs for which it is arbitrarily weak.     

Matchings in regular graphs

We consider k-regular graphs with specified edge connectivity and show how some classical theorems and some new results concerning the existence of matchings in such graphs can be proved by using the polyhedral characterization of Edmonds. In addition, we show that lower bounds of Lovász and Plummer on the number of perfect matchings in bicritical graphs can be improved for cubic bicritical graphs.     

Claw-free graphs with strongly perfect complements. Fractional and integral version. Part I. Basic graphs

Strongly perfect graphs have been studied by several authors (e.g. Berge and Duchet (1984) [1], Ravindra (1984) [12] and Wang (2006) [14]). In a series of two papers, the current paper being the first one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free graphs that are fractionally strongly perfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [14] gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.     

Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs

A graph is clique-perfect if the cardinality of a maximum clique-independent set equals the cardinality of a minimum clique-transversal, for all its induced subgraphs. A graph G is coordinated if the chromatic number of the clique graph of H equals the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of cliqueperfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem,W₄,bull}-free, two superclasses of triangle-free graphs.     

On classes of minimal circular-imperfect graphs

Circular-perfect graphs form a natural superclass of perfect graphs: on the one hand due to their definition by means of a more general coloring concept, on the other hand as an important class of χ-bound graphs with the smallest non-trivial χ-binding function χ(G)?ω(G)+1.The Strong Perfect Graph Conjecture, recently settled by Chudnovsky et al. [The strong perfect graph theorem, Ann. of Math. 164 (2006) 51-229], provides a characterization of perfect graphs by means of forbidden subgraphs. It is, therefore, natural to ask for an analogous conjecture for circular-perfect graphs, that is for a characterization of all minimal circular-imperfect graphs.At present, not many minimal circular-imperfect graphs are known. This paper studies the circular-(im)perfection of some families of graphs: normalized circular cliques, partitionable graphs, planar graphs, and complete joins. We thereby exhibit classes of minimal circular-imperfect graphs, namely, certain partitionable webs, a subclass of planar graphs, and odd wheels and odd antiwheels. As those classes appear to be very different from a structural point of view, we infer that formulating an appropriate conjecture for circular-perfect graphs, as analogue to the Strong Perfect Graph Theorem, seems to be difficult.     

Graphs with integral spectrum

It is shown that only a fraction of 2^-Ω(n) of the graphs on n vertices have an integral spectrum. Although there are several explicit constructions of such graphs, no upper bound for their number has been known. Graphs of this type play an important role in quantum networks supporting the so-called perfect state transfer.     

Matching preclusion and conditional matching preclusion for regular interconnection networks

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices and neither perfect matchings nor almost-perfect matchings. In this paper, we prove general results regarding the matching preclusion number and the conditional matching preclusion number as well as the classification of their respective optimal sets for regular graphs. We then use these general results to study the problems for Cayley graphs generated by 2-trees and the hyper Petersen networks.