文档介绍：
On the Connectivity of Strong Product of Graphs#
5
10
15
LV Min*
(School puter Science and Technology, University of Science and Technology of China,
Hefei, Anhui,230027)
Abstract: For a connected graph G, connectivity is the minimum cardinality of an vertex-cut S in G
such that G-S is disconnected or trivial(a graph is trivial if it contains only one vertex). This paper deals
with the connectivity of strong product graphs and gives the lower bound for it.
Key words: Networks; strong Product graph; connectivity
0 Introduction
For the graph theoretical terminology and notation not defined here, we refer the reader to [1].
Throughout this paper, a graph G= (V, E) always means a finite undirected simple graph. The
set of adjacent vertices to v is denoted by NG (v) or N(v) for simplicity. The degree of v is
vÎV
vertices of G. A path from u to v, also called an uv-path, is a subgraph P with
V(P) = {u = x0 , x1,K,xr = v} , and E(P) = {x0 x1, x1x2 L, xr-1 xr} . This path is
usually denoted by P = x 0x1 K x r , r
is the length of
P and P(x i , x j ) is the section of
20
the path P
from x i to x j . Two uv-paths P and Q are said to be internally disjoint if
V(P) I V(Q) = {u, v} .
A vertex-cut of a connected graph G is a set S of edges such that G-S is not connected. The
connectivity of a graph G, denoted by
k (G) , is the smallest number of vertices w