On the Strong Product of a k-Extendable and an l-Extendable Graph |
| |
Authors: | Ervin Győri Wilfried Imrich |
| |
Institution: | Rényi Institute of Mathematics, Hungarian Academy of Sciences, Reáltanoda u. 13-15, H-1053 Budapest, Hungary. e-mail: ervin@renyi.hu, HU Montanuniversit?t Leoben, A-8700 Leoben, Austria. e-mail: imrich@unileoben.ac.at, AT
|
| |
Abstract: | Let G
1⊗G
2 be the strong product of a k-extendable graph G
1 and an l-extendable graph G
2, and X an arbitrary set of vertices of G
1⊗G
2 with cardinality 2(k+1)(l+1)/2]. We show that G
1⊗G
2−X contains a perfect matching. It implies that G
1⊗G
2 is (k+1)(l+1)/2]-extendable, whereas the Cartesian product of G
1 and G
2 is only (k+l+1)-extendable. As in the case of the Cartesian product, the proof is based on a lemma on the product of a k-extendable graph G and K
2. We prove that G⊗K
2 is (k+1)-extendable, and, a bit surprisingly, it even remains (k+1)-extendable if we add edges to it.
Received: February 17, 1997 Final version received: June 14, 2000 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|