DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

T. Paj Erker

Tjaša Paj Erker

.

email: tjasa.paj@um.si

S. Špacapan

Simon Špacapan

University of Maribor, FME, and IMFM

email: simon.spacapan@um.si

Title:

Separation of Cartesian products of graphs into several connected components by the removal of vertices

PDF

Source:

Discussiones Mathematicae Graph Theory 42(3) (2022) 905-920

Received: 2019-10-17 , Revised: 2020-03-12 , Accepted: 2020-03-13 , Available online: 2020-04-14 , https://doi.org/10.7151/dmgt.2315

Abstract:

A set $S\subseteq V(G)$ is a vertex $k$-cut in a graph $G=(V(G),E(G))$ if $G-S$ has at least $k$ connected components. The $k$-connectivity of $G$, denoted as $\kappa_k(G)$, is the minimum cardinality of a vertex $k$-cut in $G$. We give several constructions of a set $S$ such that $(G\Box H)-S$ has at least three connected components. Then we prove that for any 2-connected graphs $G$ and $H$, of order at least six, one of the defined sets $S$ is a minimum vertex 3-cut in $G\Box H$. This yields a formula for $\kappa_3(G\Box H)$.

Keywords:

$k$-connectivity, Cartesian product

References:

  1. D. Bauer, H. Broersma and E. Schmeichel, Toughness in graphs–-A survey, Graphs Combin. 22 (2006) 1–35.
    https://doi.org/10.1007/s00373-006-0649-0
  2. G. Chartrand, S.F. Kapoor, L. Lesniak and D.R. Lick, Generalized connectivity in graphs, Bull. Bombay Math. Colloq. 2 (1984) 1–6.
  3. V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228.
    https://doi.org/10.1016/0012-365X(73)90138-6
  4. D.P. Day, O.R. Oellermann and H.C. Swart, The $\ell$-connectivity function of trees and complete multipartite graphs, J. Combin. Math. Combin. Comput. 10 (1991) 183–192.
  5. J. Govorčin, and R. Škrekovski, On the connectivity of Cartesian product of graphs, Ars Math. Contemp. 7 (2014) 293–297.
    https://doi.org/10.26493/1855-3974.313.e10
  6. O.R. Oellermann, On the $\ell$-connectivity of a graph, Graphs Combin. 3 (1987) 285–291.
    https://doi.org/10.1007/BF01788551
  7. G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canad. J. Math. 9 (1957) 515–525.
    https://doi.org/10.4153/CJM-1957-060-7
  8. Y. Sun and X. Li, On the difference of two generalized connectivities of a graph, J. Comb. Optim. 33 (2017) 283–291.
    https://doi.org/10.1007/s10878-015-9956-9
  9. Y. Sun, F. Li and Z. Jin, On two generalized connectivities of graphs, Discuss. Math. Graph Theory 38 (2018) 245–261.
    https://doi.org//10.7151/dmgt.1987
  10. Y. Sun, On the maximum and minimum sizes of a graph with given k-connectivity, Discuss. Math. Graph Theory 37 (2017) 623–632.
    https://doi.org/10.7151/dmgt.1941
  11. S. Špacapan, Connectivity of Cartesian products of graphs, Appl. Math. Lett. 21 (2008) 682–685.
    https://doi.org/10.1016/j.aml.2007.06.010
  12. J.M. Xu and C. Yang, Connectivity and super-connectivity of Cartesian product graphs, Ars Combin. 95 (2010) 235–245.
  13. C. Yang and J.M. Xu, Reliability of interconnection networks modeled by Cartesian product digraphs, Networks 52 (2008) 202–205.
    https://doi.org/10.1002/net.20231
Close