論文

Let H be a family of connected graphs. A graph G is said to be H-free if G does not contain any members of H as an induced subgraph. Let F(H) be the family of connected H-free graphs. In this context, the members of H are called forbidden subgraphs. In this paper, we focus on two pairs of forbidden subgraphs containing a com- mon graph, and compare the classes of graphs satisfying each of the two forbidden subgraph conditions. Our main result is the following: Let H1;H2;H3be connected graphs of order at least three, and suppose that H1 is twin-less. If the symmetric difference of F(fH1;H2g) and F(fH1;H3g) is finite and the tuple (H1;H2;H3) is non-trivial in a sense, then H2and H3are obtained from the same vertex-transitive graph by successively replacing a vertex with a clique and joining the neighbors of the original vertex and the clique. Furthermore, we refine a result in [Combin. Probab. Comput. 22 (2013) 733-748] concerning forbidden pairs.

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.

© 2018 Wiley Periodicals, Inc. Let H be a set of connected graphs, each of which has order at least three, and suppose that there exist infinitely many connected H-free graphs of minimum degree at least two and all except for finitely many of them have a 2-factor. In [J. Graph Theory, 64 (2010), 250–266], we proved that if |H| ≤ 3, then one of the members in H is a star. In this article, we determine the remaining members of H and hence give a complete characterization of the pairs and triples of forbidden subgraphs.

© 2018, Springer Japan KK, part of Springer Nature. A graph G is said to be 1-planar if it can be drawn on the sphere or plane so that any edge of G has at most one crossing point with another edge. Moreover, G is called an optimal 1-planar graph if | E(G) | = 4 | V(G) | - 8. In this paper, we investigate the matching extendability of optimal 1-planar graphs. It is shown that every optimal 1-planar graph G of even order is 2-extendable unless G contains a 4-cycle C which separates the graph into two odd components. Moreover, for any 5-connected optimal 1-planar graph, we characterize a matching with three edges which is not extendable.

In this note, we consider triangulations of the plane. Ozeki and the second author asked whether there are non-hamiltonian 1-tough triangulations in which every two separating triangles are disjoint. We answer this question in the affirmative and strengthen a result of Nishizeki by proving that there are infinitely many non-hamiltonian 1-tough triangulations with pairwise disjoint separating triangles.

© 2019 Wiley Periodicals, Inc. A matching M in a graph G is said to be extendable if there exists a perfect matching of G containing M. Also, M is said to be a distance d matching if the shortest distance between a pair of edges in M is at least d. A graph G is distance d matchable if every distance d matching is extendable in G, regardless of its size. In this paper, we study the class of distance d matchable graphs. In particular, we prove that for every integer K with k ≥ 3, there exists a positive integer d such that every connected, locally (k − 1)-connected K1,k-free graph of even order is distance d matchable. We also prove that every connected, locally K-connected K1,f-free graph of even order is distance 3 matchable. Furthermore, we make more detailed analysis of K1,4-free graphs and study their distance matching extension properties.

© 2020 Wiley Periodicals, Inc. 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 M 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 3 7-extendable for any m.

Kaiser and Vrana [European J. Combin. 33 (2012), 924-947] showed that every 5-connected line graph of minimum degree at least 6 is hamiltonian, which gives a partial solution to Thomassen’s Conjecture on hamiltonicity of line graphs [J. Graph Theory 10 (1986), 309-324]. In this paper, we prove that every 5-connected line graph of sufficiently large order compared with a given positive integer k and of minimum degree at least 6 also has a 2-factor with exactly k cycles. In order to show this result, we investigate minimum degree conditions for the existence of such a 2-factor in hamiltonian line graphs.