Super-connectivity of Kronecker products of split graphs, powers of cycles, powers of paths and complete graphs
type: Item
instance of: scholarly article
title: Super-connectivity of Kronecker products of split graphs, powers of cycles, powers of paths and complete graphs
zbMATH Open document ID: 1259.05099
author: Litao Guo
author: Weihua Yang
author: Xiaofeng Guo
published in: Applied Mathematics Letters
publication date: 2012-11-15T00:00:00Z
review text: For a graph \(G\), let \(\kappa(G)\) and \(\delta(G)\) be the connectivity of \(G\) and the minimum degree of \(G\), respectively. A graph \(G\) is called maximally connected if \(\kappa(G)=\delta(G)\). The Kronecker product of two connected graphs \(G_1, G_2\) denoted by \(G_1\times G_2\), is the graph with vertex set \[ V(G_1\times G_2)=V(G_1)\times V(G_2) \] and edge set \[ E(G_1\times G_2)=\{(u_1,v_1)(u_2,v_2): u_1u_2\in E(G_1), v_1v_2\in E(G_2)\}. \] The \(k\)th power \(G^k\) of \(G\) is the graph with vertex set \(V(G)\) such that two distinct vertices are adjacent in \(G^k\) if and only if their distance apart in \(G\) is at most \(k\). A maximally connected graph \(G\) is called super-connected if every minimal vertex cut of \(G\) is the set of neighbors of some vertex in \(G\). A graph \(G=(V,E)\) is called a split graph if \(V\) can be partitioned into a clique \(C\) and an independent set \(I\). For a split graph \(G\), write \(G=(C,I,E)\). In this paper, the authors consider the super-connectivity of the Kronecker products of several kinds of graphs and complete graphs. Their main results are the following. {\parindent=7mm \begin{itemize}\item[(i)]For a split graph \(G=(C,I,E)\) with \(|C|\geq 4\), \(\kappa(G \times K_m)=\delta(G)(m-1)\) for \(m\geq 3\). \item[(ii)]For a non-complete split graph \(G=(C,I,E)\) with \(|C|\geq 5\), \(G\times K_m\) is super-connected, where \(m\geq 3\). \item[(iii)]For \(n\geq 2k+1, m\geq 3\), \(K_m\times P_n^k\) is maximally connected. \end{itemize}}
reviewed by: Shinya Fujita
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C76
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 6107007
zbMATH Keywords: Kronecker product
zbMATH Keywords: super-connectivity
zbMATH Keywords: cut set
MaRDI profile type: Publication
full work available at URL: j.aml.2012.04.006
OpenAlex ID: W1980305443
DOI: 10.1016/J.AML.2012.04.006
description: scientific article; zbMATH DE number 6107007