Strong product of factor-critical graphs

Autor: Xu Yang, Qinglin Yu, Zefang Wu
Rok vydání: 2011
Předmět:
Zdroj: International Journal of Computer Mathematics. 88:2685-2696
ISSN: 1029-0265
0020-7160
DOI: 10.1080/00207160.2011.564276
Popis: Strong product G1⊠ G2 of two graphs G1 and G2 has a vertex set V(G1)×V(G2) and two vertices (u1, v1) and (u2, v2) are adjacent whenever u1=u2 and v1 is adjacent to v2 or u1 is adjacent to u2 and v1=v2, or u1 is adjacent to u2 and v1 is adjacent to v2. We investigate the factor-criticality of G1⊠ G2 and obtain the following. Let G1 and G2 be connected m-factor-critical and n-factor-critical graphs, respectively. Then if m≥ 0, n=0, |V(G1)|≥ 2m+2 and |V(G2)|≥ 4, then G1⊠ G2 is (2m+2)-factor-critical; if n=1, |V(G1)|≥ 2m+3 and either m≥ 3 or |V(G2)|≥ 5, then G1⊠ G2 is (2m+4-e)-factor-critical, where e=0 if m is even, otherwise e=1; if m+2 ≤ |V(G1)|≤ 2m+2, or n+2≤ |V(G2)|≤ 2n+2, then G1⊠ G2 is mn-factor-critical; if |V(G1)|≥ 2m+3 and |V(G2)|≥ 2n+3, then G1⊠ G2 is (mn-min{[3m/2]2, [3n/2]2})-factor-critical.
Databáze: OpenAIRE
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje