完全多部图的广义连通度
|
摘要
连通度是图论的基本概念之一，它常被用来衡量一个通讯网络的性能。一个通讯网络可以自然地表示成图的形式，而连通度就是为使这个图不连通所需移除的元素（顶点或边）的最小数目，因此连通度越高也就意味着这个通讯网络的性能越好。连通度被众多的数学家进行研究。近年来，数学家们又提出了一些新的连通度概念，如彩虹连通度，广义连通度等，从不同的侧重点研究图的连通性质。这篇论文的主要结果就是关于广义连通度的一些进展。
令G为一个具有n个顶点的非平凡连通图， k为一个整数，满足2≤k≤n。对G的一个k-元子集S，用κ(S)表示G中边不交树T1,T2,...,T的数目，这些树要满足V(Ti)∩V (Tj)=S，对每对不同的整数i, j，其中1≤i, j≤(注意到这些树在G\S中是顶点不交的)。G中满足这一性质的一族树{T1,T2,...,T}称为连接S的内部不交树集。图G的k-连通度，记为κk(G)，定义为κk(G)=min{κ(S)}，其中最小是取遍V (G)的所有k-元子集S。因此，κ2(G)=κ(G)，而κn(G)是G的边不交生成树的数目.
本文的第一章主要介绍一些记号和定义，以及相关的结果等。
在第二章中，我们设计了一种方法——列表方法，利用这种方法我们可以方便而快捷的找到任意完全二部图的所有边不交生成树。我们还计算了完全二部图的所有广义k-连通度并得到下面的结果：令a，b为满足a≤b的任意两个正整数，如果k> b a+2，且a b+k是奇数，那么
在第三章中，我们将列表方法进一步用于完全三部图，可以找到任意完全三部图的所有边不交生成树。应用数学分析和近似算法等中的一些技巧，我们计算出了等部完全三部图的所有广义k-连通度。对满足b≥2且3≤k≤3b的任意两个整数b，k，等部完全三部图K3
在第四章中，我们用图的分解以及匹配的一些方法，找到了完全多部图G的所有m(G)n(G)1棵边不交生成树，其中m(G)表示G的边数，n(G)表示G的顶点数。我们还根据完全二部图和等部完全三部图的广义k-连通度的结果，提出了关于完全多部图的广义k-连通度的一些猜想。
Connectivity is one of the basic concepts of graph theory, it is often used to mea-sure the performance of a communication network. A communication network can berepresented as a graph naturally, while the connectivity of the graph is the minimumnumber of elements (vertices or edges) which need to be removed to disconnect thegraph. Therefore the higher the connectivity of the graph means the better the perfor-mance of the communication network. Connectivity is studied by many mathemati-cians. In recent years, mathematicians have also proposed some new concepts aboutconnectivity, such as rainbow connection, generalized connectivity and so on. Theystudy the connectivity property of graphs from different emphases. The main results ofthis thesis are about some development of generalized connectivity.
Let G be a nontrivial connected graph of order n, and k an integer with2≤k≤n.For a set S of k vertices of G, let κ(S) denote the number of edge-disjoint treesT1,T2,...,T in G such that V(Ti)∩V (Tj)=S for every pair i, j of distinct integers with1≤i, j≤(Note that the trees are vertex-disjoint in G\S). A collection {T1,T2,...,T}of trees in G with this property is called an internally disjoint set of trees connectingS. The k-connectivity, denoted by κk(G), of G is then defined as κk(G)=min{κ(S)},where the minimum is taken over all k-subsets S of V (G). Thus, κ2(G)=κ(G) andκn(G) is the number of edge-disjoint spanning trees of G.
In Chapter1, we introduce some notation, definitions and related results.
In Chapter2, we design a method—list method. Using this method we can find alledge-disjoint spanning trees of any complete bipartite graph conveniently and rapidly.Then we compute k-connectivity of all complete bipartite graphs for2≤k≤n andget the following results: Let a, b be any two positive integers such that a≤b. Ifk> b a+2and a b+k is odd, then
In Chapter3, we apply list method to complete3-partite graphs. With this methodwe can find all edge-disjoint spanning trees of any complete3-partite graph. Then weuse some techniques in mathematical analysis and approximation algorithms to com-pute k-connectivity of all complete equipartition3-partite graphs for3≤k≤n. Forany two integers b, k such that b≥2and3≤k≤3b, the k-connectivity of completeequipartition3-partite graph K3
In Chapter4, we use some techniques in decomposition of graphs and matchingto find allm(G)n(G)1edge-disjoint spanning trees of complete equipartition multipartitegraph G, where m(G) denotes the number of edges of G and n(G) denotes the numberof vertices of G. We also propose some conjectures about k-connectivity of completeequipartition multipartite graphs according to the results of k-connectivity of completebipartite graphs and complete equipartition3-partite graphs.
令G为一个具有n个顶点的非平凡连通图， k为一个整数，满足2≤k≤n。对G的一个k-元子集S，用κ(S)表示G中边不交树T1,T2,...,T的数目，这些树要满足V(Ti)∩V (Tj)=S，对每对不同的整数i, j，其中1≤i, j≤(注意到这些树在G\S中是顶点不交的)。G中满足这一性质的一族树{T1,T2,...,T}称为连接S的内部不交树集。图G的k-连通度，记为κk(G)，定义为κk(G)=min{κ(S)}，其中最小是取遍V (G)的所有k-元子集S。因此，κ2(G)=κ(G)，而κn(G)是G的边不交生成树的数目.
本文的第一章主要介绍一些记号和定义，以及相关的结果等。
在第二章中，我们设计了一种方法——列表方法，利用这种方法我们可以方便而快捷的找到任意完全二部图的所有边不交生成树。我们还计算了完全二部图的所有广义k-连通度并得到下面的结果：令a，b为满足a≤b的任意两个正整数，如果k> b a+2，且a b+k是奇数，那么
在第三章中，我们将列表方法进一步用于完全三部图，可以找到任意完全三部图的所有边不交生成树。应用数学分析和近似算法等中的一些技巧，我们计算出了等部完全三部图的所有广义k-连通度。对满足b≥2且3≤k≤3b的任意两个整数b，k，等部完全三部图K3
在第四章中，我们用图的分解以及匹配的一些方法，找到了完全多部图G的所有m(G)n(G)1棵边不交生成树，其中m(G)表示G的边数，n(G)表示G的顶点数。我们还根据完全二部图和等部完全三部图的广义k-连通度的结果，提出了关于完全多部图的广义k-连通度的一些猜想。
Connectivity is one of the basic concepts of graph theory, it is often used to mea-sure the performance of a communication network. A communication network can berepresented as a graph naturally, while the connectivity of the graph is the minimumnumber of elements (vertices or edges) which need to be removed to disconnect thegraph. Therefore the higher the connectivity of the graph means the better the perfor-mance of the communication network. Connectivity is studied by many mathemati-cians. In recent years, mathematicians have also proposed some new concepts aboutconnectivity, such as rainbow connection, generalized connectivity and so on. Theystudy the connectivity property of graphs from different emphases. The main results ofthis thesis are about some development of generalized connectivity.
Let G be a nontrivial connected graph of order n, and k an integer with2≤k≤n.For a set S of k vertices of G, let κ(S) denote the number of edge-disjoint treesT1,T2,...,T in G such that V(Ti)∩V (Tj)=S for every pair i, j of distinct integers with1≤i, j≤(Note that the trees are vertex-disjoint in G\S). A collection {T1,T2,...,T}of trees in G with this property is called an internally disjoint set of trees connectingS. The k-connectivity, denoted by κk(G), of G is then defined as κk(G)=min{κ(S)},where the minimum is taken over all k-subsets S of V (G). Thus, κ2(G)=κ(G) andκn(G) is the number of edge-disjoint spanning trees of G.
In Chapter1, we introduce some notation, definitions and related results.
In Chapter2, we design a method—list method. Using this method we can find alledge-disjoint spanning trees of any complete bipartite graph conveniently and rapidly.Then we compute k-connectivity of all complete bipartite graphs for2≤k≤n andget the following results: Let a, b be any two positive integers such that a≤b. Ifk> b a+2and a b+k is odd, then
In Chapter3, we apply list method to complete3-partite graphs. With this methodwe can find all edge-disjoint spanning trees of any complete3-partite graph. Then weuse some techniques in mathematical analysis and approximation algorithms to com-pute k-connectivity of all complete equipartition3-partite graphs for3≤k≤n. Forany two integers b, k such that b≥2and3≤k≤3b, the k-connectivity of completeequipartition3-partite graph K3
In Chapter4, we use some techniques in decomposition of graphs and matchingto find allm(G)n(G)1edge-disjoint spanning trees of complete equipartition multipartitegraph G, where m(G) denotes the number of edges of G and n(G) denotes the numberof vertices of G. We also propose some conjectures about k-connectivity of completeequipartition multipartite graphs according to the results of k-connectivity of completebipartite graphs and complete equipartition3-partite graphs.
引文
[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmllan PressLtd. London,1976.
[2] J.A. Bondy and U.S.R. Murty, Graph Theory, GTM244, Springer,2008.
[3] Reinhard Diestel, Graph Theory,3rd ed, GTM173, Springer,2008.
[4] D.Z Du, K.Y. Ge and X.D. Hu, Design and Analysis of Approximation Algo-rithms, HIGHER EDUCATION PRESS,2011.
[5] A. Schrijver, Combinatorial optimization, Springer,2003.
[6] B. Bolloba′s, Extremal Graph Theory, Academic Press,1978.
[7] R. Halin, Graphentheorie, Wissenschaftliche Buchgesellschaft,1980.
[8] R.L. Graham, M. Gr o¨tschel and L. Lov a′sz, Handbook of Combinatorics, North-Holland,1995.
[9] G. Chartrand, S.F. Kapoor, L. Lesniak, D.R. Lick, Generalized connectivity ingraphs, Bull. Bombay Math. Colloq.2(1984),1-6.
[10] G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, Rainbow connection ingraphs, Math. Bohem.133(2008),85-98.
[11] G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, The rainbow connectivity ofa graph, Networks54(2)(2009),75-81.
[12] S. Chakraborty, E. Fischer, A. Matsliah, R. Yuster, Hardness and algorithms forrainbow connectivity, J. Combin. Optim.21(2011),330-347.
[13] Y. Caro, A. Lev, Y. Roditty, Z. Tuza, R. Yuster, On rainbow connection, Electron.J. Combin.15(2008), R57.
[14] E. Uchoa and M. Poggi de Arag a o, Vertex-disjoint packing of two Steiner trees:polyhedra and branch-and-cut, Mathematical Programming90(2001),537-557.
[15] M. Gro¨tschel, A. Martin, R. Weismantel, The Steiner tree packing problem inVLSI-design, Mathematical Programming78(1997),265-281.
[16] A. Martin, R. Weismantel, Packing paths and Steiner trees: routing of electroniccircuits, CWI Quarterly6(1993),185-204.
[17] B. Korte, H.J. Pro¨mel, A. Steger, Steiner trees in VLSI-layout. Paths, Flows, andVLSI-layout, Springer-Verlag,1990,185-214.
[18] D. Bienstock, A. Bley, Capacitated network design with multicast commodities,Proceedings in the8th International Conference on Telecommunication Systems,2000.
[19] M. Hosseini, N.D. Georganas, Design of a multi-sender3D videoconferencingapplication over an end system multicast protocol, Proceedings of the eleventhACM international conference on Multimedia,2003,480-489.
[20] P. Sanders, S. Egner, L. Tolhuizen, Polynomial time algorithms for network in-formation flow, Proceedings of the fifteenth annual ACM symposium on Parallelalgorithms and architectures,2003,286-294.
[21] K. Menger, Zur allgemeinen Kurventheorie, Fund. Math.10(1927),95-115.
[22] C.St.J.A.Nash-Williams, Edge disjoint spanning trees of finite graphs. J. Lond.Math. Soc.36(1961),445-450.
[23] W.T. Tutte, On the problem of decomposing a graph into n connected factors, J.Lond. Math. Soc.36(1961),221-230.
[24] Matthias Kriesell, Edge-disjoint trees containing some given vertices in a graph,Journal of Combinatorial Theory, Series B88(2003),53–65.
[25] D.B. West, H.H. Wu, Packing of Steiner trees and S-connectors in graphs, Journalof Combinatorial Theory, Series B102(2012),186-205.
[26] Matthias Kriesell, Packing Steiner trees on four terminals, Journal of Combinato-rial Theory, Series B100(2010),546-553.
[27] K. Jain, M. Mahdian, M.R. Salavatipour, Packing Steiner trees, Proceeding SODA’03Proceedings of the fourteenth annual ACM-SIAM symposium on Discretealgorithms.
[28] L.C. Lau, An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem,Foundations of Computer Science, Proceedings.45th Annual IEEE Symposium2004,61-70.
[29] G. Chartrand, F. Okamoto, P. Zhang, Rainbow trees in graphs and generalizedconnectivity, Networks55(4)(2010),360-367.
[30] R.E. Tarjan, Edge-disjoint spanning trees and depth-first search, Acta Informatica6(2),171-185.
[31] M. Farber, B. Richter and H. Shank, Edge-disjoint spanning trees: A connected-ness theorem, Journal of Graph Theory9(1985),319–324.
[32] P.A. Catlin, H.J. Lai and Y.H. Shao, Edge-connectivity and edge-disjointspanningtrees, Discrete Mathematics309(2009),1033–1040.
[33] S. Li, X. Li, W. Zhou, Sharp bounds for the generalized connectivity κ3(G), Dis-crete Math.310(2010),2147–2163.
[34] H. Whitney, Congruent graphs and the connectivity of graphs and the connectivityof graphs, Amer. J. Math.54(1932),150-168.
[35] F. Okamoto and P. Zhang, The tree connectivity of regular complete bipartitegraphs, Journal of Combinatorial Mathematics and Combinatorial Computing,74(2010),279-293.
[36] S. Li, X. Li, Note on the hardness of generalized connectivity, J. Combin. Opti-mization. in press.
[37] H. Li, X. Li, Y. Sun, The generalized3-connectivity of Cartesian product graphs,Discrete Math. Theor. Comput. Sci.14(1)(2012).
[38] S. Li, X. Li, Y. Shi,The minimal size of a graph with generalized connectivityκ3=2, Australasian J. Combin.51(2011).
[2] J.A. Bondy and U.S.R. Murty, Graph Theory, GTM244, Springer,2008.
[3] Reinhard Diestel, Graph Theory,3rd ed, GTM173, Springer,2008.
[4] D.Z Du, K.Y. Ge and X.D. Hu, Design and Analysis of Approximation Algo-rithms, HIGHER EDUCATION PRESS,2011.
[5] A. Schrijver, Combinatorial optimization, Springer,2003.
[6] B. Bolloba′s, Extremal Graph Theory, Academic Press,1978.
[7] R. Halin, Graphentheorie, Wissenschaftliche Buchgesellschaft,1980.
[8] R.L. Graham, M. Gr o¨tschel and L. Lov a′sz, Handbook of Combinatorics, North-Holland,1995.
[9] G. Chartrand, S.F. Kapoor, L. Lesniak, D.R. Lick, Generalized connectivity ingraphs, Bull. Bombay Math. Colloq.2(1984),1-6.
[10] G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, Rainbow connection ingraphs, Math. Bohem.133(2008),85-98.
[11] G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, The rainbow connectivity ofa graph, Networks54(2)(2009),75-81.
[12] S. Chakraborty, E. Fischer, A. Matsliah, R. Yuster, Hardness and algorithms forrainbow connectivity, J. Combin. Optim.21(2011),330-347.
[13] Y. Caro, A. Lev, Y. Roditty, Z. Tuza, R. Yuster, On rainbow connection, Electron.J. Combin.15(2008), R57.
[14] E. Uchoa and M. Poggi de Arag a o, Vertex-disjoint packing of two Steiner trees:polyhedra and branch-and-cut, Mathematical Programming90(2001),537-557.
[15] M. Gro¨tschel, A. Martin, R. Weismantel, The Steiner tree packing problem inVLSI-design, Mathematical Programming78(1997),265-281.
[16] A. Martin, R. Weismantel, Packing paths and Steiner trees: routing of electroniccircuits, CWI Quarterly6(1993),185-204.
[17] B. Korte, H.J. Pro¨mel, A. Steger, Steiner trees in VLSI-layout. Paths, Flows, andVLSI-layout, Springer-Verlag,1990,185-214.
[18] D. Bienstock, A. Bley, Capacitated network design with multicast commodities,Proceedings in the8th International Conference on Telecommunication Systems,2000.
[19] M. Hosseini, N.D. Georganas, Design of a multi-sender3D videoconferencingapplication over an end system multicast protocol, Proceedings of the eleventhACM international conference on Multimedia,2003,480-489.
[20] P. Sanders, S. Egner, L. Tolhuizen, Polynomial time algorithms for network in-formation flow, Proceedings of the fifteenth annual ACM symposium on Parallelalgorithms and architectures,2003,286-294.
[21] K. Menger, Zur allgemeinen Kurventheorie, Fund. Math.10(1927),95-115.
[22] C.St.J.A.Nash-Williams, Edge disjoint spanning trees of finite graphs. J. Lond.Math. Soc.36(1961),445-450.
[23] W.T. Tutte, On the problem of decomposing a graph into n connected factors, J.Lond. Math. Soc.36(1961),221-230.
[24] Matthias Kriesell, Edge-disjoint trees containing some given vertices in a graph,Journal of Combinatorial Theory, Series B88(2003),53–65.
[25] D.B. West, H.H. Wu, Packing of Steiner trees and S-connectors in graphs, Journalof Combinatorial Theory, Series B102(2012),186-205.
[26] Matthias Kriesell, Packing Steiner trees on four terminals, Journal of Combinato-rial Theory, Series B100(2010),546-553.
[27] K. Jain, M. Mahdian, M.R. Salavatipour, Packing Steiner trees, Proceeding SODA’03Proceedings of the fourteenth annual ACM-SIAM symposium on Discretealgorithms.
[28] L.C. Lau, An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem,Foundations of Computer Science, Proceedings.45th Annual IEEE Symposium2004,61-70.
[29] G. Chartrand, F. Okamoto, P. Zhang, Rainbow trees in graphs and generalizedconnectivity, Networks55(4)(2010),360-367.
[30] R.E. Tarjan, Edge-disjoint spanning trees and depth-first search, Acta Informatica6(2),171-185.
[31] M. Farber, B. Richter and H. Shank, Edge-disjoint spanning trees: A connected-ness theorem, Journal of Graph Theory9(1985),319–324.
[32] P.A. Catlin, H.J. Lai and Y.H. Shao, Edge-connectivity and edge-disjointspanningtrees, Discrete Mathematics309(2009),1033–1040.
[33] S. Li, X. Li, W. Zhou, Sharp bounds for the generalized connectivity κ3(G), Dis-crete Math.310(2010),2147–2163.
[34] H. Whitney, Congruent graphs and the connectivity of graphs and the connectivityof graphs, Amer. J. Math.54(1932),150-168.
[35] F. Okamoto and P. Zhang, The tree connectivity of regular complete bipartitegraphs, Journal of Combinatorial Mathematics and Combinatorial Computing,74(2010),279-293.
[36] S. Li, X. Li, Note on the hardness of generalized connectivity, J. Combin. Opti-mization. in press.
[37] H. Li, X. Li, Y. Sun, The generalized3-connectivity of Cartesian product graphs,Discrete Math. Theor. Comput. Sci.14(1)(2012).
[38] S. Li, X. Li, Y. Shi,The minimal size of a graph with generalized connectivityκ3=2, Australasian J. Combin.51(2011).