Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 52 min ago
Peer-reviewedCC BY-NC-ND 4.0Journal of Computer and System Sciences

On the g-extra connectivity of graphs products

  • Zhao Wang
  • Yaping Mao
  • Sun-Yuan Hsieh
  • Ralf Klasing
  • Yuzhi Xiao
Open at sourcePDFDOICite

Abstract

Connectivity is one of important parameters for the fault tolerant of an interconnection network. In 1996, Fàbrega and Fiol proposed the concept of g-extra connectivity. A subset of vertices S is said to be a cutset if G -S is not connected. A cutset S is called an R g -cutset, where g is a non-negative integer, if every component of G -S has at least g + 1 vertices. If G has at least one R g -cutset, the g-extra connectivity of G, denoted by κ g (G), is then defined as the minimum cardinality over all R g -cutsets of G. In this paper, we first obtain the exact value of g-extra connectivity for the lexicographic product of two general graphs. Next, the upper and lower sharp bounds of g-extra connectivity for the Cartesian product of two genaral graphs are given. In the end, we apply our results on grid graphs and 2-dimensional generalized hypercubes.

Related

  1. Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
    Jia Wei, Muhuo Liu, Zhifu You +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The Connectivity Threshold for Friends and Strangers graphs
    Bruno Baldissera, Gabriel Dias do Couto, Simon Griffiths +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Independence number, essential connectivity and the distance spectral radius of graphs
    Shuang Ding, Dan Li, Yuanyuan Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. A linear bound for a connectivity partition in graphs
    Jia Zhou, Jin Yan, Yunshu Gao
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Maximum degree for random geometric graphs in the connectivity regime and beyond
    Junpei Otsuka
    arXivPreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@article{wang2026gextra,
  title = {{On the g-extra connectivity of graphs products}},
  author = {Zhao Wang and Yaping Mao and Sun-Yuan Hsieh and Ralf Klasing and Yuzhi Xiao},
  journal = {Journal of Computer and System Sciences},
  year = {2026},
  month = sep,
  doi = {10.1016/j.jcss.2026.103772},
  url = {https://hal.science/hal-05747471v1},
  note = {CC BY-NC-ND 4.0},
}
RIS
TY  - JOUR
TI  - On the g-extra connectivity of graphs products
AU  - Zhao Wang
AU  - Yaping Mao
AU  - Sun-Yuan Hsieh
AU  - Ralf Klasing
AU  - Yuzhi Xiao
PY  - 2026
DA  - 2026/09/11
JO  - Journal of Computer and System Sciences
DO  - 10.1016/j.jcss.2026.103772
UR  - https://hal.science/hal-05747471v1
AB  - Connectivity is one of important parameters for the fault tolerant of an interconnection network. In 1996, Fàbrega and Fiol proposed the concept of g-extra connectivity. A subset of vertices S is said to be a cutset if G -S is not connected. A cutset S is called an R g -cutset, where g is a non-negative integer, if every component of G -S has at least g + 1 vertices. If G has at least one R g -cutset, the g-extra connectivity of G, denoted by κ g (G), is then defined as the minimum cardinality over all R g -cutsets of G. In this paper, we first obtain the exact value of g-extra connectivity for the lexicographic product of two general graphs. Next, the upper and lower sharp bounds of g-extra connectivity for the Cartesian product of two genaral graphs are given. In the end, we apply our results on grid graphs and 2-dimensional generalized hypercubes.
SN  - 0022-0000
SN  - 1090-2724
ER  -