On strong connectivity and cycles in graphs.

摘要

We consider the notions of H-linked graphs and H-immersions, which generalize the ideas of k-linked and weakly k-linked graphs. Then we prove a result about disjoint hamiltonian cycles in bipartite graphs.; Let H be a multigraph, let G be a simple graph, and let P (G) denote the set of paths in G. An H-subdivision in G is a pair of mappings f1 : V(H) → V(G) and f2 : E(H) → P (G) such that: (i) f1 is injective; (ii) for every edge xy ∈ E(H), f2(xy ) is an f1(x) - f1(y) path in G, and distinct edges of H map to internally disjoint paths in G.; A graph G is H-linked if every injective map f1 : V(H) → V(G) can be extended to an H-subdivision. This notion of an H-linked graph generalizes both k-linked and k-ordered graphs. We prove a minimum degree condition that guarantees a graph G is H-linked.; An H-immersion in G is similar to an H-subdivision, except paths in the image of f 2 need only be edge-disjoint. We prove a minimum degree condition that is sufficient to show that every injective map f1 : V(H) → V( G) can be extended to an H-immersion.; Finally, we give a minimum degree sum condition that guarantees a balanced bipartite graph contains k-edge disjoint hamiltonian cycles. This result extends a theorem of Moon and Moser.