Edge proximity and matching extension in punctured planar triangulations

A matching $M$ in a graph $G$ is said to be extendable if there exists a perfect matching of $G$ containing $M$. In 1989, it was shown that every connected planar graph with at least $8$ vertices has a matching of size three which is not extendable. In contrast, the study of extending certain matchings of size three or more has made progress in the past decade when the given graph is $5$-connected planar triangulation or $5$-connected plane graphs with few non-triangular faces.In this paper, we prove that if $G$ is a $5$-connected plane graph of even order in which at most two faces are not triangular and $M$ is a matching of size four in which the edges lie pairwise distance at least three apart, then $M$ is extendable. A related result concerning perfect matching with proscribed edges is shown as well.     

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.     

Toughness,binding number and restricted matching extension in a graph

A connected graph $G$ with at least $2m+2n+2$ vertices is said to satisfy the property $E(m,n)$ if $G$ contains a perfect matching and for any two sets of independent edges $M$ and $N$ with $\left|M\right|=m$ and $\left|N\right|=n$ with $M\cap N=?$, there is a perfect matching $F$ in $G$ such that $M?F$ and $N\cap F=?$. In particular, if $G$ is $E(m,0)$, we say that $G$ is $m$-extendable. One of the authors has proved that every $m$-tough graph of even order at least $2m+2$ is $m$-extendable (Plummer, 1988). Chen (1995) and Robertshaw and Woodall (2002) gave sufficient conditions on binding number for $m$-extendability. In this paper, we extend these results and give lower bounds on toughness and binding number which guarantee $E(m,n)$.     

Distance matching extension and local structure of graphs

A matching in a graph is said to be extendable if there exists a perfect matching of containing . Also, is said to be a distance matching if the shortest distance between a pair of edges in is at least . A graph is distance matchable if every distance matching is extendable in , regardless of its size. In this paper, we study the class of distance matchable graphs. In particular, we prove that for every integer with , there exists a positive integer such that every connected, locally -connected -free graph of even order is distance matchable. We also prove that every connected, locally -connected -free graph of even order is distance matchable. Furthermore, we make more detailed analysis of -free graphs and study their distance matching extension properties.     

Edge proximity and matching extension in projective planar graphs

A graph $G$ with at least $2m+2$ vertices is said to be distance $d$ $m$-extendable if, for any matching $M$ of $G$ with $m$ edges in which the edges lie at distance at least $d$ pairwise, there exists a perfect matching of $G$ containing $M$. In this paper we prove that every 5-connected triangulation on the projective plane of even order is distance 3 7-extendable and distance 4 $m$-extendable for any $m$.     

Generating even triangulations of the projective plane

We shall determine the 20 families of irreducible even triangulations of the projective plane. Every even triangulation of the projective plane can be obtained from one of them by a sequence of even‐splittings and attaching octahedra, both of which were first given by Batagelj 2 . © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 333–349, 2007     

On the number of hamiltonian cycles in triangulations with few separating triangles

In this article, we investigate the number of hamiltonian cycles in triangulations. We improve a lower bound of for the number of hamiltonian cycles in triangulations without separating triangles (4‐connected triangulations) by Hakimi, Schmeichel, and Thomassen to a linear lower bound and show that a linear lower bound even holds in the case of triangulations with one separating triangle. We confirm their conjecture about the number of hamiltonian cycles in triangulations without separating triangles for up to 25 vertices and give computational results and constructions for triangulations with a small number of hamiltonian cycles and 1–5 separating triangles.     

On the existence of strongly regular families of triangulations for domains with a piecewise smooth boundary

In this note we present an algorithm for a construction of strongly regular families of triangulations for planar domains with a piecewise curved boundary. Some additional properties of the resulting triangulations are considered.     

Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465-473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245-256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217-228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74-87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434-438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k?5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K₆. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K₆ by a number of θ⁺-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either K_k+1 or the graph H_k/2+1 obtained from K_k+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to K_k+1.     

The number of vertices of degree 5 in a contraction-critically 5-connected graph

An edge of a 5-connected graph is said to be 5-contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no 5-contractible edge is said to be contraction-critically 5-connected. Let V(G) and V₅(G) denote the vertex set of a graph G and the set of degree 5 vertices of G, respectively. We prove that each contraction-critically 5-connected graph G has at least |V(G)|/2 vertices of degree 5. We also show that there is a sequence of contraction-critically 5-connected graphs {G_i} such that lim_i→∞|V₅(G_i)|/|V(G_i)|=1/2.     

Graphs in which some and every maximum matching is uniquely restricted

A matching M in a graph G is uniquely restricted if there is no matching in G that is distinct from M but covers the same vertices as M. Solving a problem posed by Golumbic, Hirst, and Lewenstein, we characterize the graphs in which some maximum matching is uniquely restricted. Solving a problem posed by Levit and Mandrescu, we characterize the graphs in which every maximum matching is uniquely restricted. Both our characterizations lead to efficient recognition algorithms for the corresponding graphs.     

Subgraph induced by the set of degree 5 vertices in a contraction critically 5-connected graph

An edge of a 5-connected graph is said to be contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no contractible edge is said to be contraction critically 5-connected. Let G be a contraction critically 5-connected graph and let H be a component of the subgraph induced by the set of degree 5 vertices of G. Then it is known that |V(H)|≥4. We prove that if |V(H)|=4, then , where stands for the graph obtained from K₄ by deleting one edge. Moreover, we show that either |N_G(V(H))|=5 or |N_G(V(H))|=6 and around H there is one of two specified structures called a -configuration and a split -configuration.     

On the maximum number of edges in a hypergraph with a unique perfect matching

In this note, we determine the maximum number of edges of a k-uniform hypergraph, k≥3, with a unique perfect matching. This settles a conjecture proposed by Snevily.