On Perfect Matchings And 1-toughness Of Jump Graphs

Line graphs are an important class of transformation graphs, and they are widely studied. The complement of a line graph is called a jump graph. Compared with the rich theory of line graphs, the known results of jump graphs are poor. For a simple graph G, Wu and Wang (Graph Theory Notes of New York 39 (2000) 23-25) gave a necessary and sufficient condition for a jump graph J(G) to have a perfect matching. In this thesis, we generalize the result to all loopless graphs (may have parallel edges) by applying Tutte's theorem. The proof of the result is based on the complete characterization for the structure of the underlying simple graph of G when J(G) is not connected.A graph G is said to be 1-tough if ω(G - S) ≤ |S| for every nonempty proper subset S of V(G), where ω(G- S) is the number of components of the graph G - S. We also give a necessary and sufficient condition for a jump graph J(G) to be 1-tough in this thesis.Before stating our main results, we need some notations. Let G be a loopless graph . ε(G) denotes the number of edges of G, â–³(G) denotes the maximum degree of G. H C G represents that H is a subgraph of G. (?)(G) = max{ε(H) | H (?) G and H (?) K₃} if G contains a triangle, otherwise (?)(G) = 0. For a graph G, an edge e is called a dominating edge if it is adjacent to every other edge of G. D(G) denotes the number of dominating edges in G. (?)(G) = max{d(u) + d(v)|u and v are taken over any pair of adjacent vertices in G}. K₄^- denotes the graph obtained from K₄ by deleting an edge, K_1,r + e denotes the graph obtained from K_1,r by adding an edge between two vertices of degrees one. For any two graphs G and H, if V(G) ∩ V(H) = (?), G + H denotes the disjoint union of G and H. The following are our main results:(1) Let G be a loopless graph. Then J(G) has a perfect matching if and onlyif e(G) is an even number not less than 2 max{â–³(G), (?)(G)}.(2) Let G be a loopless graph of order n and size q. Then J(G) is 1-tough...