Two lower bounds for generalized 3-connectivity of Cartesian product graphs

DOI10.1016/J.AMC.2018.04.007MaRDI QIDQ2335758zbMATH OpenOpenAlexWikidataFDO

Authors Hui Gao, Benjian Lv, Kaishun Wang

Publication date 15 November 2019

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.08087

zbMATH Keywords

Cartesian productconnectivitygeneralized connectivity

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Abstract: The generalized $k$-connectivity $kapp{a}_k(G)$ of a graph $G$, which was introduced by Chartrand et al.(1984) is a generalization of the concept of vertex connectivity. Let $G$ and $H$ be nontrivial connected graphs. Recently, Li et al. gave a lower bound for the generalized $3$-connectivity of the Cartesian product graph $GsquareH$ and proposed a conjecture for the case that $H$ is $3$-connected. In this paper, we give two different forms of lower bounds for the generalized $3$-connectivity of Cartesian product graphs. The first lower bound is stronger than theirs, and the second confirms their conjecture.

Recommendations

• The generalized 3-connectivity of graph products
• Generalized 3-edge-connectivity of Cartesian product graphs.
• The generalized 3-connectivity of Cartesian product
• Generalized 3-connectivity and 3-edge-connectivity for the Cartesian products of some graph classes
• The generalized 3-connectivity of lexicographic product graphs

Cites work

• Generalized Connectivity of Graphs
• Graph theory
• scientific article; zbMATH DE number 1321108 (Why is no real title available?)
• Note on the hardness of generalized connectivity
• On minimally 2-connected graphs with generalized connectivity \(\kappa_3=2\)
• On the generalized (edge-)connectivity of graphs
• Rainbow trees in graphs and generalized connectivity
• Sharp bounds for the generalized connectivity \(\kappa _{3}(G)\)
• The generalized 3-connectivity of Cartesian product
• The generalized 3-connectivity of Cayley graphs on symmetric groups generated by trees and cycles
• The generalized 3-connectivity of graph products
• The generalized 3-connectivity of lexicographic product graphs
• The generalized 3-connectivity of star graphs and bubble-sort graphs
• The generalized connectivity of complete bipartite graphs.
• The generalized connectivity of complete equipartition 3-partite graphs
• The minimal size of a graph with generalized connectivity _3=2
• Tree connectivities of Cayley graphs on abelian groups with small degrees

Cited in

(12)

• On two generalized connectivities of graphs
• The generalized 3-connectivity of graph products
• A sharp lower bound for the generalized 3-edge-connectivity of strong product graphs
• Generalized 3-connectivity and 3-edge-connectivity for the Cartesian products of some graph classes
• Sharp upper bounds for generalized edge-connectivity of product graphs
• The generalized 3-connectivity of lexicographic product graphs
• Generalized 3-edge-connectivity of Cartesian product graphs.
• The generalized 3-connectivity of Cartesian product
• The generalized 4-connectivity of locally twisted cubes
• The lower bounds of 4-tree connectivity of Cartesian product graphs
• The generalized 3-connectivity and 4-connectivity of crossed cube
• The generalized 4-connectivity of bubble-sort graphs

This page was built for publication: Two lower bounds for generalized 3-connectivity of Cartesian product graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2335758)