完全图的笛卡尔积的广义3-连通度
The Generalized 3-Connectivity of Cartesian Product of Complete Graphs
DOI: 10.12677/AAM.2019.82036, PDF,    国家自然科学基金支持
作者: 李恒哲, 芦园园, 王佳佳：河南师范大学数学和信息科学学院，河南 新乡
关键词: 完全图；K3-连通度；笛卡尔积；Complete Graphs； K3-Connectivity； Cartesian Product
摘要: 设S是图G中至少有2个顶点的集合，T是G的一棵子树。如果S⊆V(T)，则称T是G的一棵S-斯坦纳树。设T1与T2是S-斯坦纳树，如果E(T1)∩E(T2)=∅且V(T1)∩V(T2)=S，则称T1与T2是内部不交的S-斯坦纳树。KG(S)表示图G中内部不交的S-斯坦纳树的最大数目，KK(G)是当S遍及V(G)的所有k元子集时的最小的KG(S)。在本文中，我们研究完全图的笛卡尔积的K3-连通度。对于任意两个完全图Kn1与Kn2，确定K3(Kn1,Kn2)=n1+n2-3；对于任意K(K≥2)个完全图，确定K3(Kn1,Kn2,...,KnK)=∑i=1kni-K-1。
Abstract: Let S be a set of at least two vertices in a graph G. A subtree T of G is an S-Steiner tree if S⊆V(T). Two S-Steiner trees T1 and T2 are internally disjoint if E(T1)∩E(T2)=∅ and V(T1)∩V(T2)=S. Let KG(S) be the maximum number of internally disjoint S-Steiner trees in G, and let KK(G) be the minimum KG(S) for S ranges over all k-subsets of V(G). In this paper, we study the K3-connectivity of Cartesian product of complete graphs, determine K3(Kn1,Kn2)=n1+n2-3 for any two complete graphs; K3(Kn1,Kn2,...,KnK)=∑i=1kni-K-1 for any k complete graphs, where K≥2.
文章引用：李恒哲, 芦园园, 王佳佳. 完全图的笛卡尔积的广义3-连通度[J]. 应用数学进展, 2019, 8(2): 320-326. https://doi.org/10.12677/AAM.2019.82036

参考文献

[1] Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory, GTM 244. Springer, Berlin.
[2] Chartrand, G., Kapoor, S.F., Lesniak, L. and Lick, D.R. (1984) Generalized Connectivity in Graphs. Bulletin of the Bombay Mathematical Colloquium, 2, 1-6.
[3] Chiue, W.-S. and Shieh, B.-S. (1999) On Connectivity of Cartesian Product of Two Graphs. Applied Mathematics and Computation, 102, 129-137. [Google Scholar] [CrossRef] 
[4] Imrich, W. and Klavžar, S. (2000) Product Graphs. Structure and Recognition. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, New York.
[5] Imrich, W., Klavžar, S. and Rall, D.F. (2008) Topics in Graph Theory. Graphs and Their Cartesian Product. AK Peters, Wellesley.
[6] Klavžar, S. and Spacapan, S. (2008) On the Edge-Connectivity of Cartesian Product Graphs. Asian-European Journal of Mathematics, 1, 93-98.
[7] Sabidussi, G. (1957) Graphs with Given Group and Given Graph-Theoretic Properties. Canadian Journal of Mathematics, 9, 515-525. [Google Scholar] [CrossRef] 
[8] Špacapan, S. (2008) Connectivity of Cartesian Products of Graphs. Applied Mathematics Letters, 21, 682-685. [Google Scholar] [CrossRef] 
[9] Xu, J. and Yang, C. (2006) Connectivity of Cartesian Product Graphs. Discrete Mathematics, 306, 159-165. [Google Scholar] [CrossRef] 
[10] Chartrand, G., Okamoto, F. and Zhang, P. (2010) Rainbow Trees in Graphs and Generalized Connectivity. Networks, 55, 360-367.
[11] Li, H. and Wang, J. (2018) The λ3-Connectivity and κ3-Connectivity of Recursive Circulants. Applied Mathematics and Computation, 339, 750-757. [Google Scholar] [CrossRef] 
[12] Li, H., Li, X. and Sun, Y. (2012) The Generalied 3-Connectivity of Cartesian Product Graphs. Discrete Mathematics and Theoretical Computer Science, 14, 43-54.
[13] Li, S., Li, X. and Zhou, W. (2010) Sharp Bounds for the Generalized Connectivity κ3(G). Discrete Mathematics, 310, 2147-2163. [Google Scholar] [CrossRef] 
[14] Li, X. and Mao, Y. (2014) The Generalized 3-Connectivity of Lexicographic Product Graphs. Discrete Mathematics and Theoretical Computer Science, 16, 339-354.
[15] Li, X., Mao, Y. and Sun, Y. (2014) On the Generalized (Edge-)Connectivity of Graphs. Australasian Journal of Combinatorics, 58, 304-319.
[16] Li, H., Wu, B., Meng, J. and Ma, Y. (2018) Steiner Tree Packing Number and Tree Connectivity. Discrete Mathematics, 341, 1945-1951. [Google Scholar] [CrossRef] 
[17] Li, H., Ma, Y., Yang, W. and Wang, Y. (2017) The Generalized 3-Connectivity of Graph Products. Applied Mathematics and Computation, 295, 77-83. [Google Scholar] [CrossRef] 
[18] Li, X. and Mao, Y. (2016) Generalized Connectivity of Graphs. In: Springer Briefs in Math, Springer, New York. [Google Scholar] [CrossRef] 
[19] Dirac, G.A. (1960) In abstrakten graphen vorhandene voll-standige 4-graphen und ihre unterteilungen. Mathematische Nachrichten, 22, 61-85. [Google Scholar] [CrossRef] 
[20] Lin, S. and Zhang, Q. (2017) The Generalized 4-Connectivity of Hypercubes. Discrete Applied Mathematics, 220, 60-67. [Google Scholar] [CrossRef] 

为你推荐