論文

The connected graph of degree sequence 3, 3, 3, 1, 1, 1 is called a net, and the vertices of degree 1 in a net are called its endvertices. Broersma conjectured in 1993 that a 2-connected graph G with no induced K1 , 3 is hamiltonian if every endvertex of each induced net of G has degree at least (| V(G) | - 2) / 3. In this paper we prove this conjecture in the affirmative.

Bondy (1980) generalized the well-known Ore’s Theorem by using the degree sum of vertices in independent sets while (Fan, 1984) generalized it in terms of pairs of vertices at distance 2 (that is, non-adjacent vertices with a common neighbor). Chen et al. (1996) gave a unified view to these two generalizations by introducing the notion of an essential independent set, which is an independent set containing a pair of vertices at distance 2. In this paper, we prove that the assumption of the result of Chen et al. is decomposed into two assumptions of Fan’s result and an extension of Bondy’s result proved by Song and Zhang (1994). This shows that an essential independent set does not play an essential role in Chen et al. (1996). We also apply our decomposition to several other statements.

A graph G is said to be distanced matchable if, for any matching M of G in which edges are pairwise at least distance d apart, there exists a perfect matching M∗ of G which contains M. In this paper, we prove the following results: (i) if G is a cubic bipartite graph in which, for each e∈ E(G) , there exist two cycles C1, C2 of length at most d such that E(C1) ∩ E(C2) = { e} , then G is distance d- 1 matchable, and (ii) if G is a planar or projective planar cubic bipartite graph in which, for each e∈ E(G) , there exist two cycles C1, C2 of length at most 6 such that e∈ E(C1) ∩ E(C2) , then G is distance 6 matchable.

Let G be a balanced bipartite graph of order 2n with partite sets X and Y, and M be a matching of k edges in G. Let σ1,1(G)=min⁡{dG(x)+dG(y):x∈X,y∈Y,xy∉E(G)}. Conditions on σ1,1(G) for the existence of a Hamilton cycle passing through M have been studied by many researchers, but the threshold is not known to be sharp for [Formula presented]. In this paper we prove that G has a Hamilton cycle passing through all the edges of M if σ1,1(G)≥2n−k and k≤n−2. Moreover, we show that the lower bound on σ1,1(G) is sharp for every k with [Formula presented].

A fullerene graph is a 3-connected plane cubic graph in which every face is pentagonal or hexagonal. A set of hexagons H of G is called a resonant pattern if there exists a perfect matching M of G such that exactly three edges of H is contained in M for each member H of H. In this paper we prove for any natural number k that almost all of the family of k disjoint hexagons are resonant patterns in sufficiently large fullerene graphs.

Let (Formula presented.) be the Euler characteristic of a surface (Formula presented.). We characterize the set of graphs (Formula presented.) of order at most 6 which satisfies the following: If (Formula presented.) is a 5-connected graph embedded in a surface (Formula presented.) of face-width at least (Formula presented.) and (Formula presented.) is a subgraph of (Formula presented.) isomorphic to (Formula presented.) such that (Formula presented.) has even order, then (Formula presented.) has a perfect matching. An analogous result on near-perfect matching is given as well. Moreover, we show the following result. Let (Formula presented.) be a 5-connected graph embedded in a surface (Formula presented.) and let (Formula presented.) be connected subgraphs of (Formula presented.) of size at most (Formula presented.) which lie pairwise sufficiently far apart in the face-subdivision of (Formula presented.). We prove that, if the face-width of (Formula presented.) is at least (Formula presented.) and (Formula presented.) satisfies (Formula presented.) for each (Formula presented.) with (Formula presented.), then (Formula presented.) satisfies (Formula presented.) as well, where (Formula presented.) is said to satisfy (Formula presented.) if (Formula presented.) has at most (Formula presented.) components for every (Formula presented.). It is also shown that the distance condition can be considerably weakened when (Formula presented.) triangulates the surface. All of these results generalize previous studies on matching extension in graphs on surfaces.

The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths.