Restricted connectivity for some interconnection networks (Q497373)

From MaRDI portal
Revision as of 02:49, 9 December 2024 by Import241208021249 (talk | contribs) (Normalize DOI.)
scientific article
Language Label Description Also known as
English
Restricted connectivity for some interconnection networks
scientific article

    Statements

    Restricted connectivity for some interconnection networks (English)
    0 references
    0 references
    0 references
    24 September 2015
    0 references
    This paper studies restricted connectivity and super connectivity of a connected graph \(G\). A vertex-cut \(S\subseteq G\) is called restricted if there is no vertex \(v\in G\), whose neighborhood is contained in \(S\). The restricted connectivity \(\kappa^\prime(G)\) is defined as the order of a minimum restricted vertex-cut in the graph. A vertex-cut is called a super vertex-cut if \(G-S\) contains no isolated vertices. The super connectivity \(\kappa_1(G)\) is defined as the order of a minimum super vertex-cut in \(G\). It is well known that \(\kappa_1(G)\leq\kappa^\prime(G)\). Among other things, the authors prove that \(\kappa_1(K_m\times G_2)=\kappa^\prime(K_m\times G_2)=2k_2+m-2\), where \(G_2\) is a \(k_2 (\geq2)\)-regular and maximally connected graph with girth \(g(G_2)\geq 4\); and \(\kappa_1(G_1\times G_2)=\kappa^\prime(G_1\times G_2)=2(k_1+k_2-1)\), where \(G_i\) is a \(k_i(\geq2)\)-regular and maximally connected graph with girth \(g(G_i)\geq4\) for \(i=1,2\).
    0 references
    0 references
    restricted connectivity
    0 references
    super connectivity
    0 references
    Cartesian product
    0 references
    minimal abelian Cayley graph
    0 references

    Identifiers