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.      

Perfect Matchings in Total Domination Critical Graphs

A graph is total domination edge-critical if the addition of any edge decreases the total domination number, while a graph with minimum degree at least two is total domination vertex-critical if the removal of any vertex decreases the total domination number. A 3 _t EC graph is a total domination edge-critical graph with total domination number 3 and a 3 _t VC graph is a total domination vertex-critical graph with total domination number 3. A graph G is factor-critical if G − v has a perfect matching for every vertex v in G. In this paper, we show that every 3 _t EC graph of even order has a perfect matching, while every 3 _t EC graph of odd order with no cut-vertex is factor-critical. We also show that every 3 _t VC graph of even order that is K _1,7-free has a perfect matching, while every 3 _t VC graph of odd order that is K _1,6-free is factor-critical. We show that these results are tight in the sense that there exist 3 _t VC graphs of even order with no perfect matching that are K _1,8-free and 3 _t VC graphs of odd order that are K _1,7-free but not factor-critical.     

Factor-Critical Graphs with Given Number of Maximum Matchings

A connected graph G is said to be factor-critical if G − ν has a perfect matching for every vertex ν of G. In this paper, the factor-critical graphs G with |V(G)| maximum matchings and with |V(G)| + 1 ones are characterized, respectively. From this, some special bicritical graphs are characterized. This work is supported by the Ph.D. Programs Foundation of Ministry of Education of China (No.20070574006) and the NNSF(10201019) of China.     

3-Factor-criticality in domination critical graphs

A graph G is said to be k-γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k-1 vertices. The structure of k-γ-critical graphs remains far from completely understood when k?3.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G) and is bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G). More generally, a graph is said to be k-factor-critical if G-S has a perfect matching for every set S of k vertices in G. In three previous papers [N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs, Discrete Math. 272 (2003) 5-15; N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs. II. Utilitas Math. 70 (2006) 11-32], we explored the toughness of 3-γ-critical graphs and some of their matching properties. In particular, we obtained some properties which are sufficient for a 3-γ-critical graph to be factor-critical and, respectively, bicritical. In the present work, we obtain similar results for k-factor-critical graphs when k=3.     

Thomassen's conjecture implies polynomiality of 1‐Hamilton‐connectedness in line graphs

A graph G is 1‐Hamilton‐connected if G?x is Hamilton‐connected for every x∈V(G), and G is 2‐edge‐Hamilton‐connected if the graph G+ X has a hamiltonian cycle containing all edges of X for any X?E⁺(G) = {xy| x, y∈V(G)} with 1≤|X|≤2. We prove that Thomassen's conjecture (every 4‐connected line graph is hamiltonian, or, equivalently, every snark has a dominating cycle) is equivalent to the statements that every 4‐connected line graph is 1‐Hamilton‐connected and/or 2‐edge‐Hamilton‐connected. As a corollary, we obtain that Thomassen's conjecture implies polynomiality of both 1‐Hamilton‐connectedness and 2‐edge‐Hamilton‐connectedness in line graphs. Consequently, proving that 1‐Hamilton‐connectedness is NP‐complete in line graphs would disprove Thomassen's conjecture, unless P = NP. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 241–250, 2012     

On supercompact graphs

A graph G is called a supercompact graph if G is the intersection graph of some family ?? of subsets of a set X such that ?? satisfies the Helly property and for any x≠y in X, there exists S ∈ ?? with x ∈ S, y ? S. Various characterizations of supercompact graphs are given. It is shown that every clique-critical graph is supercompact. Furthermore, for any finite graph, H, there is at most a finite number of different supercompact graphs G such that H is the clique-graph of G.     

Matchings in 3-vertex-critical graphs: The odd case

A subset of vertices D of a graph G is a dominating set for G if every vertex of G not in D is adjacent to one in D. The cardinality of any smallest dominating set in G is denoted by γ(G) and called the domination number of G. Graph G is said to be γ-vertex-critical if γ(G-v)<γ(G), for every vertex v in G. A graph G is said to be factor-critical if G-v has a perfect matching for every choice of v∈V(G).In this paper, we present two main results about 3-vertex-critical graphs of odd order. First we show that any such graph with positive minimum degree and at least 11 vertices which has no induced subgraph isomorphic to the bipartite graph K_1,5 must contain a near-perfect matching. Secondly, we show that any such graph with minimum degree at least three which has no induced subgraph isomorphic to the bipartite graph K_1,4 must be factor-critical. We then show that these results are best possible in several senses and close with a conjecture.     

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.     

On constructible graphs,locally Helly graphs,and convexity

A (finite or infinite) graph G is constructible if there exists a well‐ordering ≤ of its vertices such that for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Particular constructible graphs are Helly graphs and connected bridged graphs. In this paper we study a new class of constructible graphs, the class of locally Helly graphs. A graph G is locally Helly if, for every pair (x,y) of vertices of G whose distance is d ≥ 2, there exists a vertex whose distance to x is d ? 1 and which is adjacent to y and to all neighbors of y whose distance to x is at most d. Helly graphs are locally Helly, and the converse holds for finite graphs. Among different properties we prove that a locally Helly graph is strongly dismantable, hence cop‐win, if and only if it contains no isometric rays. We show that a locally Helly graph G is finitely Helly, that is, every finite family of pairwise non‐disjoint balls of G has a non‐empty intersection. We give a sufficient condition by forbidden subgraphs so that the three concepts of Helly graphs, of locally Helly graphs and of finitely Helly graphs are equivalent. Finally, generalizing different results, in particular those of Bandelt and Chepoi 1 about Helly graphs and bridged graphs, we prove that the Helly number h(G) of the geodesic convexity in a constructible graph G is equal to its clique number ω(G), provided that ω(G) is finite. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 280–298, 2003     

Gromov hyperbolic cubic graphs

If X is a geodesic metric space and x ₁; x ₂; x ₃ ∈ X, a geodesic triangle T = {x ₁; x ₂; x ₃} is the union of the three geodesics [x ₁ x ₂], [x ₂ x ₃] and [x ₃ x ₁] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by δ(X) the sharp hyperbolicity constant of X, i.e., δ(X) = inf {δ ≥ 0: X is δ-hyperbolic}. We obtain information about the hyperbolicity constant of cubic graphs (graphs with all of their vertices of degree 3), and prove that for any graph G with bounded degree there exists a cubic graph G* such that G is hyperbolic if and only if G* is hyperbolic. Moreover, we prove that for any cubic graph G with n vertices, we have δ(G) ≤ min {3n/16 + 1; n/4}. We characterize the cubic graphs G with δ(G) ≤ 1. Besides, we prove some inequalities involving the hyperbolicity constant and other parameters for cubic graphs.     

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.     

Graphs with independent perfect matchings

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3 , we find all the extremal cubic matching covered graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005     

Hamiltonian cycles in n‐extendable graphs

A graph G of order at least 2n+2 is said to be n‐extendable if G has a perfect matching and every set of n independent edges extends to a perfect matching in G. We prove that every pair of nonadjacent vertices x and y in a connected n‐extendable graph of order p satisfy deg_G x+deg_G y ≥ p ? n ? 1, then either G is hamiltonian or G is isomorphic to one of two exceptional graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 75–82, 2002     

Preperfect graphs

We say that a vertexx of a graph is predominant if there exists another vertexy ofG such that either every maximum clique ofG containingy containsx or every maximum stable set containingx containsy. A graph is then called preperfect if every induced subgraph has a predominant vertex. We show that preperfect graphs are perfect, and that several well-known classes of perfect graphs are preperfect. We also derive a new characterization of perfect graphs.     

Minimally non-Pfaffian graphs

We consider the question of characterizing Pfaffian graphs. We exhibit an infinite family of non-Pfaffian graphs minimal with respect to the matching minor relation. This is in sharp contrast with the bipartite case, as Little [C.H.C. Little, A characterization of convertible (0,1)-matrices, J. Combin. Theory Ser. B 18 (1975) 187–208] proved that every bipartite non-Pfaffian graph contains a matching minor isomorphic to K_3,3. We relax the notion of a matching minor and conjecture that there are only finitely many (perhaps as few as two) non-Pfaffian graphs minimal with respect to this notion.We define Pfaffian factor-critical graphs and study them in the second part of the paper. They seem to be of interest as the number of near perfect matchings in a Pfaffian factor-critical graph can be computed in polynomial time. We give a polynomial time recognition algorithm for this class of graphs and characterize non-Pfaffian factor-critical graphs in terms of forbidden central subgraphs.     

Equimatchable Graphs on Surfaces

A graph G is equimatchable if each matching in G is a subset of a maximum‐size matching and it is factor critical if has a perfect matching for each vertex v of G. It is known that any 2‐connected equimatchable graph is either bipartite or factor critical. We prove that for 2‐connected factor‐critical equimatchable graph G the graph is either or for some n for any vertex v of G and any minimal matching M such that is a component of . We use this result to improve the upper bounds on the maximum number of vertices of 2‐connected equimatchable factor‐critical graphs embeddable in the orientable surface of genus g to if and to if . Moreover, for any nonnegative integer g we construct a 2‐connected equimatchable factor‐critical graph with genus g and more than vertices, which establishes that the maximum size of such graphs is . Similar bounds are obtained also for nonorientable surfaces. In the bipartite case for any nonnegative integers g, h, and k we provide a construction of arbitrarily large 2‐connected equimatchable bipartite graphs with orientable genus g, respectively nonorientable genus h, and a genus embedding with face‐width k. Finally, we prove that any d‐degenerate 2‐connected equimatchable factor‐critical graph has at most vertices, where a graph is d‐degenerate if every its induced subgraph contains a vertex of degree at most d.     

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.     

Matching graphs

The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M₁ and M₂ of M(G) are adjacent if and only if |M₁ − M₂| = 1. When M(G) is connected, this graph models a metric space whose metric is defined on the set of maximum matchings in G. Which graphs are matching graphs of some graph is not known in general. We determine several forbidden induced subgraphs of matching graphs and add even cycles to the list of known matching graphs. In another direction, we study the behavior of sequences of iterated matching graphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 73–86, 1998     

Induced Graph Packing Problems

Let H{\mathcal{H}} be a set of undirected graphs. The induced H{\mathcal{H}} -packing problem in an input graph G is to find a subgraph Q of G of maximum size such that each connected component of Q is an induced subgraph of G and is isomorphic to some member of H{\mathcal{H}} . In this paper we focus on the case when H{\mathcal{H}} consists of factor-critical graphs and a certain family of ‘propellers’. Clarifying the methods developed in the related theory of non-induced graph packings, we show a Gallai–Edmonds type structure theorem and a Berge–Tutte type minimax formula. We also give an Edmonds type alternating forest algorithm for the case when H{\mathcal{H}} consists of a sequential set of stars and factor-critical graphs. This simplifies the related result of Egawa, Kano and Kelmans.