![Sample our Computer Science journals, sign in here to start your access, latest two full volumes FREE to you for 14 days]({"type":"image" , "src" : "/sda/5928/TOC-Subject-Sample-2021-Computer-Science.jpg"})
Abstract
Strong product G 1⊠ G 2 of two graphs G 1 and G 2 has a vertex set V(G 1)×V(G 2) and two vertices (u 1, v 1) and (u 2, v 2) are adjacent whenever u 1=u 2 and v 1 is adjacent to v 2 or u 1 is adjacent to u 2 and v 1=v 2, or u 1 is adjacent to u 2 and v 1 is adjacent to v 2. We investigate the factor-criticality of G 1⊠ G 2 and obtain the following. Let G 1 and G 2 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. | ||||
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.