Search

Let G be a graph. A vertex-cut S of G is said to be k-restricted if every component of G − S has at least k vertices, and cyclic if G − S has at least two components which contain a cycle. The minimum cardinality over all k -restricted vertex-cuts of G is called the k-restricted connectivity of G and is denoted by κ k (G). Also the minimum cardinality over all cyclic vertex-cuts of G is called the cyclic connectivity of graph G and is denoted by κ c (G). In this paper, the k -restricted connectivity and cyclic connectivity of the direct product of two graphs G 1 and G 2 is obtained for some k ≥ 2 , where G 1 is a complete graph, and G 2 is a complete graph, a complete bipartite graph or a cycle. [ABSTRACT FROM AUTHOR]

For a group G and a subset S of G the bi-Cayley graph BCay (G , S) of G with respect to S is the bipartite graph with vertex set G × { 0 , 1 } and edge set { { (x , 0) , (s x , 1) } | x ∈ G , s ∈ S }. A bi-Cayley graph BCay (G , S) is called a BCI-graph if for any bi-Cayley graph BCay (G , T) , BCay (G , S) ≅ BCay (G , T) implies that T = g S α for some g ∈ G and α ∈ Aut (G). A group G is called a m -BCI-group if all bi-Cayley graphs of G with valency at most m are BCI-graphs. In this paper, we characterize the m -BCI dihedral groups for m ≤ 3. Also, we show that the dihedral group D 2 p (p is prime) is a 4 -BCI-group. [ABSTRACT FROM AUTHOR]