| INDEPENDENT-SET-DELETABLE FACTOR-CRITICAL POWER GRAPHS |
| |
| 作者姓名： | 原晋江 |
| |
| 作者单位： | Department of |
| |
| 基金项目： | Project supported by NSFC(10371112)，NSFHN (0411011200)，SRF for ROCS,SEM |
| |
| 摘 要： | It is said that a graph G is independent-set-deletable factor-critical (in short, ID-factor-critical), if, for every independent set 7 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.
|
| 关 键 词： | 理想匹配 感应匹配 IM可扩展 功率图 |
| 收稿时间： | 2003-12-20 |
INDEPENDENT-SET-DELETABLE FACTOR-CRITICAL POWER GRAPHS |
| |
| Jinjiang Yuan,.INDEPENDENT-SET-DELETABLE FACTOR-CRITICAL POWER GRAPHS[J].Acta Mathematica Scientia,2006,26(4):577-584. |
| |
| Authors: | Jinjiang Yuan |
| |
| Institution: | aDepartment of Mathematics, Zhengzhou University, Zhengzhou 450052, China |
| |
| Abstract: | It is said that a graph G is independent-set-deletable factor-critical (in short, ID-factor-critical), if, for every independent set 7 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. |
| |
| Keywords: | Independent set perfect matching induced matching ID-factor-critical IM-extendable power of a graph |
| 本文献已被 CNKI 维普 万方数据 ScienceDirect 等数据库收录！ |
|
