Constructing edge-disjoint Steiner trees in Cartesian product networks

Rui Li; Gregory Gutin; He Zhang; Zhao Wang; Xiaoyan Zhang; Yaping Mao

doi:10.46298/dmtcs.10921

Article

Constructing edge-disjoint Steiner trees in Cartesian product networks

Rui Li⁽¹⁾, Gregory Gutin

⁽²⁾, He Zhang⁽³⁾, Zhao Wang⁽⁴⁾, Xiaoyan Zhang⁽⁵⁾, Yaping Mao

⁽³⁾

(1) Xidian University

(2) University of London

(3) Qinghai Normal University [QHNU]

(4) China Jiliang University

(5) Nanjing Normal University [NNU]

Download article

Open on arXiv

Submitted on

February 7, 2023

Accepted on

February 12, 2026

Published on

August 29, 2026

Last modified on

August 29, 2026

Volume 28

vol. 28:2

Graph Theory

DOI

10.46298/dmtcs.10921

License

Attribution 4.0 International (CC BY 4.0)

Indicators

Views

Downloads

Constructing edge-disjoint Steiner trees in Cartesian product networks

Rui Li⁽¹⁾, Gregory Gutin

⁽²⁾, He Zhang⁽³⁾, Zhao Wang⁽⁴⁾, Xiaoyan Zhang⁽⁵⁾, Yaping Mao

⁽³⁾

(1) Xidian University

(2) University of London

(3) Qinghai Normal University [QHNU]

(4) China Jiliang University

(5) Nanjing Normal University [NNU]

Abstract

Cartesian product networks are always regarded as a tool for ``combining'' two given networks with established properties to obtain a new one that inherits properties from both. For a graph $F=(V,E)$ and a set $S\subseteq V(F)$ of at least two vertices, \emph{an $S$-Steiner tree} or \emph{a Steiner tree connecting $S$} (or simply, \emph{an $S$-tree}) is a subgraph $T=(V',E')$ of $F$ that is a tree with $S\subseteq V'$. For $S\subseteq V(F)$ and $|S|\geq 2$, the {\it generalized local edge-connectivity} $λ(S)$ is the maximum number of edge-disjoint Steiner trees connecting $S$ in $F$. For an integer $k$ with $2\leq k\leq n$, the {\it generalized $k$-edge-connectivity} $λ_k(F)$ of a graph $F$ is defined as $λ_k(F)=\min\{λ(S)\,|\,S\subseteq V(F) \ and \ |S|=k\}$.In this paper, we give sharp upper and lower bounds for $λ_k(G\Box H)$, where $\Box$ is the Cartesian product operation, and $G,H$ are two graphs. 14 pages; 3 figures

Keywords

Combinatorics

Preview

Loading PDF preview...

References

J. A. Bondy, U. S. R. Murty, Graph Theory, GTM 244, Springer, 2008.
N.J. Calkin, H.S. Wilf, The number of independent sets in a grid graph, SIAM J. Discrete Math., vol. 11, pp. 54-60, 1998.
DOI : 10.1137/s089548019528993x
X. Cheng and D. Du, Steiner Trees in Industry, Kluwer Academic Publisher, Dordrecht, 2001.
K. Day and A.-E. Al-Ayyoub, The cross product of interconnection networks, IEEE Trans. Parallel Distrib. Syst., vol. 8, pp. 109-118, 1997.
DOI : 10.1109/71.577251
D. Du, X. Hu, Steiner tree problems in computer communication networks, World Scientific, 2008.
P. Fragopoulou, S.G. Akl, Edge-disjoint spanning trees on the star network with applications to fault tolerance, IEEE Trans. Comput., vol. 45, pp. 174-185, 1996.
DOI : 10.1109/12.485370
M. Grötschel, The Steiner tree packing problem in VLSI design, Math. Program., vol. 78, pp. 265- 281, 1997.
DOI : 10.1007/bf02614374
M. Grötschel, A. Martin, R. Weismantel, Packing Steiner trees: A cutting plane algorithm and com- putational results, Math. Program., vol. 72, pp. 125-145, 1996.
DOI : 10.1007/bf02592086
M. Hager, Pendant tree-connectivity, J. Combin. Theory, Series B, vol. 38, pp. 179-189, 1985.
DOI : 10.1016/0095-8956(85)90083-8
R. Hammack, W. Imrich, and S. Klavžar, Handbook of product graphs, Second edition, CRC Press, 2011.
S.M. Hedetniemi, S.T. Hedetniemi, A.L. Liestman, A survey of gossiping and broadcasting in com- munication networks, Networks, vol. 18, pp. 1240-1268, 1988.
DOI : 10.1002/net.3230180406
A. Itai, M. Rodeh, The multi-tree approach to reliability in distributed networks, Inform. Comput., vol. 79, 1988, pp. 43-59.
DOI : 10.1016/0890-5401(88)90016-8
P. Jalote, Fault Tolerance in Distributed Systems, Prentice-Hall, Englewood Cliffs, NJ, 1994.
S. Ku, B. Wang, T. Hung, Constructing edge-disjoint spanning trees in product networks, IEEE Trans. Parallel Distrib. Syst., vol. 14, pp. 213-221, 2003.
DOI : 10.1109/TPDS.2003.1189580
S. Li, J. Tu, C. Yu, The generalized 3-connectivity of star graphs and bubble-sort graphs, Appl. Math. Comput., vol. 274, pp. 41-46, 2016.
DOI : 10.1016/j.amc.2015.11.016
H. Li, X. Li, and Y. Sun, The generalized 3-connectivity of Cartesian product graphs, Discrete Math. Theor. Comput. Sci., vol. 14, 2012.
DOI : 10.46298/dmtcs.572
H. Li, J. Wang, The λ 3 -connectivity and κ 3 -connectivity of recursive circulants, Appl. Math. Com- put., vol. 339, pp. 750-757, 2018.
DOI : 10.1016/j.amc.2018.07.065
H. Li, Y. Ma, W. Yang, Y. Wang, The generalized 3-connectivity of graph products, Applied Math. Comput., vol. 295, pp. 77-83, 2017.
DOI : 10.1016/j.amc.2016.10.002
X. Li, Y. Mao, Generalized Connectivity of Graphs, Springer Briefs in Mathematics, Springer, Switzerland, 2016.
X. Li, Y. Mao, On extremal graphs with at most ℓ internally disjoint Steiner trees connecting any n -1 vertices, Graphs & Combin., vol. 31, 2231-2259, 2015.
DOI : 10.1007/s00373-014-1500-7
X. Li, Y. Mao, The generalized 3-connectivity of lexicographic product graphs, Discrete Math. Theor. Comput. Sci., vol. 16, pp. 339-354, 2014.
DOI : 10.46298/dmtcs.1266
X. Li, Y. Mao, Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs, Discrete Appl. Math., vol. 185, pp. 102-112, 2015.
DOI : 10.1016/j.dam.2014.12.009
X. Li, Y. Mao, Y. Sun, On the generalized (edge-)connectivity of graphs, Australasian J. Combin., vol. 58, 304-319, 2014.
S. Lin, Q. Zhang, The generalized 4-connectivity of hypercubes, Discrete Appl. Math., vol. 220, pp. 60-67, 2017.
DOI : 10.1016/j.dam.2016.12.003
X. Qin, R. Hao, J. Chang, The existence of completely independent spanning trees for some com- pound graphs, IEEE Trans. Parallel Distrib. Syst., vol. 31, pp. 201-210, 2020.
DOI : 10.1109/tpds.2019.2931904
P. Ramanathan, D.D. Kandlur, K.G. Shin, Hardware-assisted software clock synchronization for homogeneous distributed systems, IEEE Trans. Comput., vol. 39, 514-524, 1990.
DOI : 10.1109/12.54844
N.A. Sherwani, Algorithms for VLSI Physical Design Automation, 3rd Edition, Kluwer Acad. Pub., London, 1999.
Y. Sun, Generalized 3-edge-connectivity of Cartesian product graphs, Czechoslovak Math. J., vol. 65, pp. 107-117, 2015.
DOI : 10.1007/s10587-015-0162-9
J. Xu, C. Yang, Connectivity of Cartesian product graphs, Discrete Math., vol. 306, pp. 159-165, 2006.
DOI : 10.1016/j.disc.2005.11.010
J.-S. Yang, J.-M. Chang, K.-J. Pai, H.-C. Chan, Parallel construction of independent spanning trees on enhanced hypercubes, IEEE Trans. Parallel Distrib. Syst., vol. 26, pp. 3090-3098, 2015.
DOI : 10.1109/tpds.2014.2367498
J.-S. Yang, J.-M. Chang, S.-M. Tang, and Y.-L. Wang, Reducing the height of independent spanning trees in chordal rings, IEEE Trans. Parallel Distrib. Syst., vol. 18, no. 5, pp. 644-657, 2007.
DOI : 10.1109/tpds.2007.351709
S. Zhao, R. Hao, The generalized connectivity of alternating group graphs and (n, k)-star graphs, Discrete Appl. Math., vol. 251, pp. 310-321, 2018.
DOI : 10.1016/j.dam.2018.05.059
S. Zhao, R. Hao, J. Wu, The generalized 3-connectivity of some regular networks, J. Parallel Distrib. Comput., vol. 133, pp. 18-29, 2019.
DOI : 10.1016/j.jpdc.2019.06.006
S. Zhao, R. Hao, E. Cheng, Two kinds of generalized connectivity of dual cubes, Discrete Appl. Math., vol. 257, pp. 306-316, 2019.
DOI : 10.1016/j.dam.2018.09.025

Constructing edge-disjoint Steiner trees in Cartesian product networks

Rui Li⁽¹⁾, Gregory Gutin

⁽²⁾, He Zhang⁽³⁾, Zhao Wang⁽⁴⁾, Xiaoyan Zhang⁽⁵⁾, Yaping Mao

⁽³⁾

(1) Xidian University

(2) University of London

(3) Qinghai Normal University [QHNU]

(4) China Jiliang University

(5) Nanjing Normal University [NNU]

Download article

Open on arXiv

Submitted on

February 7, 2023

Accepted on

February 12, 2026

Published on

August 29, 2026

Last modified on

August 29, 2026

Volume 28

vol. 28:2

Graph Theory

DOI

10.46298/dmtcs.10921

License

Attribution 4.0 International (CC BY 4.0)

Indicators

Views

Downloads

Constructing edge-disjoint Steiner trees in Cartesian product networks

Rui Li⁽¹⁾, Gregory Gutin

⁽²⁾, He Zhang⁽³⁾, Zhao Wang⁽⁴⁾, Xiaoyan Zhang⁽⁵⁾, Yaping Mao

⁽³⁾

(1) Xidian University

(2) University of London

(3) Qinghai Normal University [QHNU]

(4) China Jiliang University

(5) Nanjing Normal University [NNU]

Abstract

Keywords

Combinatorics

Preview

Loading PDF preview...

References

J. A. Bondy, U. S. R. Murty, Graph Theory, GTM 244, Springer, 2008.
N.J. Calkin, H.S. Wilf, The number of independent sets in a grid graph, SIAM J. Discrete Math., vol. 11, pp. 54-60, 1998.
DOI : 10.1137/s089548019528993x
X. Cheng and D. Du, Steiner Trees in Industry, Kluwer Academic Publisher, Dordrecht, 2001.
K. Day and A.-E. Al-Ayyoub, The cross product of interconnection networks, IEEE Trans. Parallel Distrib. Syst., vol. 8, pp. 109-118, 1997.
DOI : 10.1109/71.577251
D. Du, X. Hu, Steiner tree problems in computer communication networks, World Scientific, 2008.
P. Fragopoulou, S.G. Akl, Edge-disjoint spanning trees on the star network with applications to fault tolerance, IEEE Trans. Comput., vol. 45, pp. 174-185, 1996.
DOI : 10.1109/12.485370
M. Grötschel, The Steiner tree packing problem in VLSI design, Math. Program., vol. 78, pp. 265- 281, 1997.
DOI : 10.1007/bf02614374
M. Grötschel, A. Martin, R. Weismantel, Packing Steiner trees: A cutting plane algorithm and com- putational results, Math. Program., vol. 72, pp. 125-145, 1996.
DOI : 10.1007/bf02592086
M. Hager, Pendant tree-connectivity, J. Combin. Theory, Series B, vol. 38, pp. 179-189, 1985.
DOI : 10.1016/0095-8956(85)90083-8
R. Hammack, W. Imrich, and S. Klavžar, Handbook of product graphs, Second edition, CRC Press, 2011.
S.M. Hedetniemi, S.T. Hedetniemi, A.L. Liestman, A survey of gossiping and broadcasting in com- munication networks, Networks, vol. 18, pp. 1240-1268, 1988.
DOI : 10.1002/net.3230180406
A. Itai, M. Rodeh, The multi-tree approach to reliability in distributed networks, Inform. Comput., vol. 79, 1988, pp. 43-59.
DOI : 10.1016/0890-5401(88)90016-8
P. Jalote, Fault Tolerance in Distributed Systems, Prentice-Hall, Englewood Cliffs, NJ, 1994.
S. Ku, B. Wang, T. Hung, Constructing edge-disjoint spanning trees in product networks, IEEE Trans. Parallel Distrib. Syst., vol. 14, pp. 213-221, 2003.
DOI : 10.1109/TPDS.2003.1189580
S. Li, J. Tu, C. Yu, The generalized 3-connectivity of star graphs and bubble-sort graphs, Appl. Math. Comput., vol. 274, pp. 41-46, 2016.
DOI : 10.1016/j.amc.2015.11.016
H. Li, X. Li, and Y. Sun, The generalized 3-connectivity of Cartesian product graphs, Discrete Math. Theor. Comput. Sci., vol. 14, 2012.
DOI : 10.46298/dmtcs.572
H. Li, J. Wang, The λ 3 -connectivity and κ 3 -connectivity of recursive circulants, Appl. Math. Com- put., vol. 339, pp. 750-757, 2018.
DOI : 10.1016/j.amc.2018.07.065
H. Li, Y. Ma, W. Yang, Y. Wang, The generalized 3-connectivity of graph products, Applied Math. Comput., vol. 295, pp. 77-83, 2017.
DOI : 10.1016/j.amc.2016.10.002
X. Li, Y. Mao, Generalized Connectivity of Graphs, Springer Briefs in Mathematics, Springer, Switzerland, 2016.
X. Li, Y. Mao, On extremal graphs with at most ℓ internally disjoint Steiner trees connecting any n -1 vertices, Graphs & Combin., vol. 31, 2231-2259, 2015.
DOI : 10.1007/s00373-014-1500-7
X. Li, Y. Mao, The generalized 3-connectivity of lexicographic product graphs, Discrete Math. Theor. Comput. Sci., vol. 16, pp. 339-354, 2014.
DOI : 10.46298/dmtcs.1266
X. Li, Y. Mao, Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs, Discrete Appl. Math., vol. 185, pp. 102-112, 2015.
DOI : 10.1016/j.dam.2014.12.009
X. Li, Y. Mao, Y. Sun, On the generalized (edge-)connectivity of graphs, Australasian J. Combin., vol. 58, 304-319, 2014.
S. Lin, Q. Zhang, The generalized 4-connectivity of hypercubes, Discrete Appl. Math., vol. 220, pp. 60-67, 2017.
DOI : 10.1016/j.dam.2016.12.003
X. Qin, R. Hao, J. Chang, The existence of completely independent spanning trees for some com- pound graphs, IEEE Trans. Parallel Distrib. Syst., vol. 31, pp. 201-210, 2020.
DOI : 10.1109/tpds.2019.2931904
P. Ramanathan, D.D. Kandlur, K.G. Shin, Hardware-assisted software clock synchronization for homogeneous distributed systems, IEEE Trans. Comput., vol. 39, 514-524, 1990.
DOI : 10.1109/12.54844
N.A. Sherwani, Algorithms for VLSI Physical Design Automation, 3rd Edition, Kluwer Acad. Pub., London, 1999.
Y. Sun, Generalized 3-edge-connectivity of Cartesian product graphs, Czechoslovak Math. J., vol. 65, pp. 107-117, 2015.
DOI : 10.1007/s10587-015-0162-9
J. Xu, C. Yang, Connectivity of Cartesian product graphs, Discrete Math., vol. 306, pp. 159-165, 2006.
DOI : 10.1016/j.disc.2005.11.010
J.-S. Yang, J.-M. Chang, K.-J. Pai, H.-C. Chan, Parallel construction of independent spanning trees on enhanced hypercubes, IEEE Trans. Parallel Distrib. Syst., vol. 26, pp. 3090-3098, 2015.
DOI : 10.1109/tpds.2014.2367498
J.-S. Yang, J.-M. Chang, S.-M. Tang, and Y.-L. Wang, Reducing the height of independent spanning trees in chordal rings, IEEE Trans. Parallel Distrib. Syst., vol. 18, no. 5, pp. 644-657, 2007.
DOI : 10.1109/tpds.2007.351709
S. Zhao, R. Hao, The generalized connectivity of alternating group graphs and (n, k)-star graphs, Discrete Appl. Math., vol. 251, pp. 310-321, 2018.
DOI : 10.1016/j.dam.2018.05.059
S. Zhao, R. Hao, J. Wu, The generalized 3-connectivity of some regular networks, J. Parallel Distrib. Comput., vol. 133, pp. 18-29, 2019.
DOI : 10.1016/j.jpdc.2019.06.006
S. Zhao, R. Hao, E. Cheng, Two kinds of generalized connectivity of dual cubes, Discrete Appl. Math., vol. 257, pp. 306-316, 2019.
DOI : 10.1016/j.dam.2018.09.025