Strong product of factor-critical graphs

Abstract

Strong product G ₁⊠ G ₂ of two graphs G ₁ and G ₂ has a vertex set V(G ₁)×V(G ₂) and two vertices (u ₁, v ₁) and (u ₂, v ₂) are adjacent whenever u ₁=u ₂ and v ₁ is adjacent to v ₂ or u ₁ is adjacent to u ₂ and v ₁=v ₂, or u ₁ is adjacent to u ₂ and v ₁ is adjacent to v ₂. We investigate the factor-criticality of G ₁⊠ G ₂ and obtain the following. Let G ₁ and G ₂ be connected m-factor-critical and n-factor-critical graphs, respectively. Then

i.	if m⩾ 0, n=0, |V(G 1)|⩾ 2m+2 and |V(G 2)|⩾ 4, then G 1⊠ G 2 is (2m+2)-factor-critical;
ii.	if n=1, |V(G 1)|⩾ 2m+3 and either m⩾ 3 or |V(G 2)|⩾ 5, then G 1⊠ G 2 is (2m+4−ϵ)-factor-critical, where ϵ=0 if m is even, otherwise ϵ=1;
iii.	if m+2 ⩽ |V(G 1)|⩽ 2m+2, or n+2⩽ |V(G 2)|⩽ 2n+2, then G 1⊠ G 2 is mn-factor-critical;
iv.	if |V(G 1)|⩾ 2m+3 and |V(G 2)|⩾ 2n+3, then G 1⊠ G 2 is (mn−min{[3m/2]2, [3n/2]2})-factor-critical.

Keywords:

• factor-criticality
• product graph
• strong product
• perfect matching
• T-join

2000 AMS Subject Classifications :

• 05C70
• 05C76

Acknowledgements

This work is supported in part by 973 Project of Ministry of Science and Technology of China and Natural Sciences and Engineering Research Council of Canada.