The Induced Matching Extendability Of Graphs

Graphs considered in this paper are finite, undirected and simple. Roughly speaking, the problems concerned in this thesis are mainly as follows:1. The induced matching extendability of claw-free graphs of diameter 2.2. The induced matching extendability of the composition of two graphs.3. Characterization of the induced matching extendable graphs with 2n vertices and 3.1 edges.4. Characterization of the induced matching extendable graphs with 2n vertices and 3n edges.5. Characterization of the induced matching extendability of the square of trees.1. Induced Matching Extendability of Claw-free Graphs of Diameter 2A graph C is daw-free, if it does not contain K13 as an induced subgraph. If vertices and are connected in G, the distance between u and v in G, denoted by is the length of a shortest -path in G. We say a graph G is of diameter r if the maximum distance between two vertices of G is r.In this section the sufficiency and necessity condition for a claw-free graph of diameter 2 is characterized, and correspondingly a polynomial-time algorithm to decide whether a claw-free graph of diameter 2 is IM-extendable is given.Step 1 For each M C E(G) with |M| < 3, check whether M is an induced matchin, of G or not, and simultaneously generate the setand turn to step 2.Theorem 1.4 For a given claw-free graph G of diameter 2, the algorithm above can determine whether it is IM-extendable in O(ne3) time, where n = \V(G}\ and e = \E(G}\.2. Induced Matching Extendability of the Composition of Two Graphs3. Characterization of the Induced Matching Extendable Graphs with 2n Vertices and 3n-l EdgesIn this section, the induced matching extendability of the composition of two graphs is studied. It is shown that G\H\ is IM-extendable, if both G and H are nontrivial, G is connected, and G and H satisfy one of the following conditions:The product of two graphs T and H, denoted by T x H is the graph with vertex set4. Characterization of the Induced Matching Extendable Graphs with 2n Vertices and 3n Edges?The product of two graphs T and H, denoted by T x H, is the graph with vertexsetA graph H with In vertices and edges is said to be (-optimal if is isomorphic to where T is an arbitrary tree on n vertices and e is any edg connecting two vertices that lie in different copies of T and has distance 3 between then the graph obtained from K^z by deleting an arbitrary edge.In [33]. Yuan proved that a connected IM-extendable graph on 2n vertices has at least 3n - 2 edges, and the only IM-extendable graph with 2n vertices and 3n ?2 edges is T x K-2, where T is an arbitrary tree on n vertices. We show in this section that the only IM-extendable graph with 2N 6 vertices and 3 ?1 edges is T x + e, where T is an arbitrary tree on n vertices and e is any edge connecting two vertices that lie in different copies of T and have distance 3 between them in T x K.Suppose that G is a connected graph, Q is an induced subgraph of G and are the all components of We call G a joint graph if both of the following conditions are satisfied:Theorem 4.1 Suppose that G is a connected IM-extendable graph with 2n vertices and 3n edges. Then, either G is isomorphic to one of D and E or G has one of the following structures:5. Characterization of the Induced Matching Extendability of the Square of Treesgraph G. denoted by is the graph \vilh vciicx set \ in which two vertices are adjacent if and only if the distance between them in G is at mostIn [32] Qian showed that if connected graph G is locally connected, then G2 is strongly IM-extendable. In [35, 36] Yuan proved that if connected graph G on even vertices has no independent cut, then G2 is strongly IM-extendable.In this section, we give the sufficiency and necessity conditions for the square of trees to be IM-extendable and strongly IM-extendable, respectively.Theorem 5.1 Suppose that T is a tree with | even. Then T2 is IM-extendable if and only if there is no vertex of even degree in T and the diameter of T is no more than 4.The...