Separation of Cartesian products of graphs on several connected components by the removal of edges

Applicable Analysis and Discrete Mathematics

article

Simon Špacapan¹ 

[1] University of Maribor

关键词: Cartesian products;    Generalized connectivity;   

DOI  :  10.2298/AADM160719018S

学科分类：社会科学、人文和艺术（综合）

来源: Univerzitet u Beogradu * Elektrotehnicki Fakultet / University of Belgrade, Faculty of Electrical Engineering

【 摘 要 】

Let G = (V (G), E(G)) be a graph. A set SE(G) is an edge k-cut in G ifthe graph G − S = (V (G), E(G) \ S) has at least k connected components.The generalized k-edge connectivity of a graph G, denoted as λk(G), is theminimum cardinality of an edge k-cut in G. In this article we determinegeneralized 3-edge connectivity of Cartesian product of connected graphs Gand H and describe the structure of any minimum edge 3-cut in G✷H. Thegeneralized 3-edge connectivity λ3(G✷H) is given in terms of λ3(G) andλ3(H) and in terms of other invariants of factors G and H.

【 授权许可】

Unknown