A Min–Max Property of Chordal Bipartite Graphs with Applications

We show that if G is a bipartite graph with no induced cycles on exactly 6 vertices, then the minimum number of chain subgraphs of G needed to cover E(G) equals the chromatic number of the complement of the square of line graph of G. Using this, we establish that for a chordal bipartite graph G, the minimum number of chain subgraphs of G needed to cover E(G) equals the size of a largest induced matching in G, and also that a minimum chain subgraph cover can be computed in polynomial time. The problems of computing a minimum chain cover and a largest induced matching are NP-hard for general bipartite graphs. Finally, we show that our results can be used to efficiently compute a minimum chain subgraph cover when the input is an interval bigraph.     

Linear-time computation of optimal subgraphs of decomposable graphs

A general problem in computational graph theory is that of finding an optimal subgraph H of a given weighted graph G. The matching problem (which is easy) and the traveling salesman problem (which is not) are well-known examples of this general problem. In the literature one can also find a variety of ad hoc algorithms for solving certain special cases in linear time. We suggest a general approach for constructing linear-time algorithms in the case where the graph G is defined by certain rules of composition (as are trees, series-parallel graphs, and outerplanar graphs) and the desired subgraph H satisfies a property that is “regular” with respect to these rules of composition (as do matchings, dominating sets, and independent sets for all the classes just mentioned). This approach is applied to obtain a linear-time algorithm for computing the irredundance number of a tree, a problem for which no polynomial-time algorithm was previously known.     

On distance-3 matchings and induced matchings

For a finite undirected graph G=(V,E) and positive integer k≥1, an edge set M⊆E is a distance-k matching if the pairwise distance of edges in M is at least k in G. For k=1, this gives the usual notion of matching in graphs, and for general k≥1, distance-k matchings were called k-separated matchings by Stockmeyer and Vazirani. The special case k=2 has been studied under the names induced matching (i.e., a matching which forms an induced subgraph in G) by Cameron and strong matching by Golumbic and Laskar in various papers.Finding a maximum induced matching is NP-complete even on very restricted bipartite graphs and on claw-free graphs but it can be done efficiently on various classes of graphs such as chordal graphs, based on the fact that an induced matching in G corresponds to an independent vertex set in the square L(G)² of the line graph L(G) of G which, by a result of Cameron, is chordal for any chordal graph G.We show that, unlike for k=2, for a chordal graph G, L(G)³ is not necessarily chordal, and finding a maximum distance-3 matching, and more generally, finding a maximum distance-(2k+1) matching for k≥1, remains NP-complete on chordal graphs. For strongly chordal graphs and interval graphs, however, the maximum distance-k matching problem can be solved in polynomial time for every k≥1. Moreover, we obtain various new results for maximum induced matchings on subclasses of claw-free graphs.     

Distance-restricted matching extension in planar triangulations

A graph G is said to have property E(m,n) if it contains a perfect matching and for every pair of disjoint matchings M and N in G with |M|=m and |N|=n, there is a perfect matching F in G such that M⊆F and N∩F=0?. In a previous paper (Aldred and Plummer 2001) [2], an investigation of the property E(m,n) was begun for graphs embedded in the plane. In particular, although no planar graph is E(3,0), it was proved there that if the distance among the three edges is at least two, then they can always be extended to a perfect matching. In the present paper, we extend these results by considering the properties E(m,n) for planar triangulations when more general distance restrictions are imposed on the edges to be included and avoided in the extension.     

A linear algorithm for the domination number of a series-parallel graph

A vertex u in an undirected graph G = (V, E) is said to dominate all its adjacent vertices and itself. A subset D of V is a dominating set in G if every vertex in G is dominated by a vertex in D, and is a minimum dominating set in G if no other dominating set in G has fewer vertices than D. The domination number of G is the cardinality of a minimum dominating set in G.The problem of determining, for a given positive integer k and an undirected graph G, whether G has a dominating set D in G satisfying ¦D¦ ≤ k, is a well-known NP-complete problem. Cockayne have presented a linear time algorithm for finding a minimum dominating set in a tree. In this paper, we will present a linear time algorithm for finding a minimum dominating set in a series-parallel graph.     

Weighted inverse maximum perfect matching problems under the Hamming distance

Given an undirected network G(V, E, c) and a perfect matching M ⁰, the inverse maximum perfect matching problem is to modify the cost vector as little as possible such that the given perfect matching M ⁰ can form a maximum perfect matching. The modification can be measured by different norms. In this paper, we consider the weighted inverse maximum perfect matching problems under the Hamming distance, where we use the weighted Hamming distance to measure the modification of the edges. We consider both of the sum-type and the bottleneck-type problems. For the general case of the sum-type case, we show it is NP-hard. For the bottleneck-type, we present a strongly polynomial algorithm which can be done in O(m · n ³).     

Restricted matching in graphs of small genus

A graph G with at least 2n+2 vertices is said to be n-extendable if every set of n disjoint edges in G extends to (i.e., is a subset of) a perfect matching. More generally, a graph is said to have property E(m,n) if, for every matching M of size m and every matching N of size n in G such that M∩N=0?, there is a perfect matching F in G such that M⊆F, but F∩N=0?. G is said to have property E(0,0) if it has a perfect matching. The study of the properties E(m,n) is referred to as the study of restricted matching extension.In [M. Porteous, R. Aldred, Matching extensions with prescribed and forbidden edges, Australas. J. Combin. 13 (1996) 163-174; M. Porteous, Generalizing matching extensions, M.A. Thesis, University of Otago, 1995; A. McGregor-Macdonald, The E(m,n) property, M.Sc. Thesis, University of Otago, 2000], Porteous and Aldred, Porteous and McGregor-Macdonald, respectively, studied the possible implications among the properties E(m,n) for various values of m and n. In an earlier paper [R.E.L. Aldred, Michael D. Plummer, On restricted matching extension in planar graphs, in: 17th British Combinatorial Conference (Canterbury 1999), Discrete Math. 231 (2001) 73-79], the present authors completely determined which of the various properties E(m,n) always hold, sometimes hold and never hold for graphs embedded in the plane. In the present paper, we do the same for embeddings in the projective plane, the torus and the Klein bottle.     

The Feasible Matching Problem

Let G = (V, E) be a graph and ${R\subseteq E}$ . A matching M in G is called R-feasible if the subgraph induced by the M-saturated vertices does not have an edge of R. We show that the general problem of finding a maximum size R-feasible matching in G is NP-hard and identify several natural applications of this new concept. In particular, we use R-feasible matchings to give a necessary and sufficient condition for the existence of a systems of disjoint representatives in a family of hypergraphs. This provides another Hall-type theorem for hypergraphs. We also introduce the concept of R-feasible (vertex) cover and combine it with the concept of R-feasible matching to provide a new formulation and approach to Ryser’s conjecture.     

2-Connected factor-critical graphs <Emphasis Type="Italic">G</Emphasis> with exactly |<Emphasis Type="Italic">E</Emphasis>(<Emphasis Type="Italic">G</Emphasis>)| + 1 maximum matchings

A connected graph G is said to be a factor-critical graph if G ?v has a perfect matching for every vertex v of G. In this paper, the 2-connected factor-critical graph G which has exactly |E(G)| + 1 maximum matchings is characterized.     

On the chordality of a graph

The chordality of a graph G = (V, E) is defined as the minimum k such that we can write E = E₁ ∩ … ∩ E_k with each (V, E_i) a chordal graph. We present several results bounding the value of this generalization of boxicity. Our principal result is that the chordality of a graph is at most its tree width. In particular, series-parallel graphs have chordality at most 2. Potential strengthenings of this statement fail in that there are planar graphs with chordality 3 and series-parallel graphs with boxicity 3. © 1993 John Wiley & Sons, Inc.     

A commutative analogue of the group ring

Throughout, all rings R will be commutative with identity element. In this paper we introduce, for each finite group G, a commutative graded Z-algebra R_G. This classifies the G-invariant commutative R-algebra multiplications on the group algebra R[G] which are cocycles (in fact coboundaries) with respect to the standard “direct sum” multiplication and have the same identity element.In the case when G is an elementary Abelian p-group it turns out that R_G is closely related to the symmetric algebra over F_p of the dual of G. We intend in subsequent papers to explore the close relationship between G and R_G in the case of a general (possibly non-Abelian) group G.Here we show that the Krull dimension of R_G is the maximal rank r of an elementary Abelian subgroup E of G unless either E is cyclic or for some such E its normalizer in G contains a non-trivial cyclic group which acts faithfully on E via “scalar multiplication” in which case it is r+1.     

Linearization of proper group actions

We prove that if G is a locally compact group acting properly (in the sense of R. Palais) on a space X that is metrizable by a G-invariant metric, then X can be embedded equivariantly into a normed linear G-space E endowed with a linear isometric G-action which is proper on the complement E?{0}. If, in addition, G is a Lie group then E?{0} is a G-equivariant absolute extensor. One can make this equivariant embedding even closed, but in this case the non-proper part of the linearizing G-space E may be an entire subspace instead of {0}.     

On matching and total domination in graphs

A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every k-regular graph with k?3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.     

Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

Given an undirected graph G=(V,E) with matching number ν(G), a d-blocker is a subset of edges B such that ν((V,E?B))≤ν(G)−d and a d-transversal T is a subset of edges such that every maximum matching M has |M∩T|≥d. While the associated decision problem is NP-complete in bipartite graphs we show how to construct efficiently minimum d-transversals and minimum d-blockers in the special cases where G is a grid graph or a tree.     

A characterization of maximal non-k-factor-critical graphs

A graph G of order p is k-factor-critical,where p and k are positive integers with the same parity, if the deletion of any set of k vertices results in a graph with a perfect matching. G is called maximal non-k-factor-critical if G is not k-factor-critical but G+e is k-factor-critical for every missing edge e∉E(G). A connected graph G with a perfect matching on 2n vertices is k-extendable, for 1?k?n-1, if for every matching M of size k in G there is a perfect matching in G containing all edges of M. G is called maximal non-k-extendable if G is not k-extendable but G+e is k-extendable for every missing edge e∉E(G) . A connected bipartite graph G with a bipartitioning set (X,Y) such that |X|=|Y|=n is maximal non-k-extendable bipartite if G is not k-extendable but G+xy is k-extendable for any edge xy∉E(G) with x∈X and y∈Y. A complete characterization of maximal non-k-factor-critical graphs, maximal non-k-extendable graphs and maximal non-k-extendable bipartite graphs is given.     

On removable even circuits in graphs

Let G be a connected graph with minimum degree at least 3. We prove that there exists an even circuit C in G such that G−E(C) is either connected or contains precisely two components one of which is isomorphic to a 1-bond. We further prove sufficient conditions for there to exist an even circuit C in a 2-connected simple graph G such that G−E(C) is 2-connected. As a consequence of this, we obtain sufficient conditions for there to exist an even circuit C in a 2-connected graph G for which G−E(C) is 2-connected.     

The edge nucleus of a point-determining graph

In this paper we investigate the edge nucleus E⁰(G) of a point-determining graph G. We observe several relationships between E⁰(G) and the nucleus G⁰ = {v ∈ V(G)∣ G ? v is point determining} and use these relationships to prove several properties of E⁰(G). In particular, we show that there are only a finite number of graphs with a given edge nucleus and we determine those graphs G for which |E⁰(G)| ≤ 2. We also show that an n-clique of a point-determining graph G contains at least n?2 edges of E⁰(G) and if G is totally point determining, then every odd cycle of G meets E⁰(G).     

Coherent orientations and series-parallel networks

Let p be an edge of the graph G. An orientation of G is p-coherent if the set of directed circuits is exactly the set of circuits containing the edge p. Theorem: A matroidally connected graph G is a series-parallel network if and only if for every edge p of G, there exists a p-coherent orientation.     

The Linear Arboricity of Series-Parallel Graphs

 The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. A graph is called series-parallel if it contains no subgraphs homeomorphic to K ₄. In this paper, we prove that for any series-parallel graph G having Δ (G)≥3. Since an outerplanar graph is a series-parallel graph, this is also true for any outerplanar graph. Received: August 20, 1997 Revised: March 12, 1999     

Blockers and transversals

Given an undirected graph G=(V,E) with matching number ν(G), we define d-blockers as subsets of edges B such that ν((V,E?B))≤ν(G)−d. We define d-transversals T as subsets of edges such that every maximum matching M has |M∩T|≥d. We explore connections between d-blockers and d-transversals. Special classes of graphs are examined which include complete graphs, regular bipartite graphs, chains and cycles and we construct minimum d-transversals and d-blockers in these special graphs. We also study the complexity status of finding minimum transversals and blockers in arbitrary graphs.