Acta mathematica scientia,Series B
• Articles • Next Articles
Yuan Jinjiang
Received:
Revised:
Online:
Published:
Contact:
Abstract:
It is said that a graph G is independent-set-deletable factor-critical (in short, ID-factor-critical), if, for every independent set I which has the same parity as |V(G)|, G-I has a perfect matching. A graph G is strongly IM-extendable, if for every spanning supergraph H of G, every induced matching of H is included in a perfect matching of H. The k-th power of G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if they have distance at most k in G. ID-factor-criticality and IM-extendability of power graphs are discussed in this article. The author shows that, if G is a connected graph, then G3 and T(G) (the total graph of G) are ID-factor-critical, and G4 (when |V(G)| is even) is strongly IM-extendable; if G is 2-connected, then D2 is ID-factor-critical.
Key words: Independent set, perfect matching, induced matching, ID-factor-critical, IM-extendable, power of a graph
CLC Number:
Yuan Jinjiang. INDEPENDENT-SET-DELETABLE FACTOR-CRITICAL POWER GRAPHS[J].Acta mathematica scientia,Series B, 2006, 26(4): 577-584.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: http://121.43.60.238/sxwlxbB/EN/10.1016/S0252-9602(06)60083-0
http://121.43.60.238/sxwlxbB/EN/Y2006/V26/I4/577
Cited