On Extremal Graphs with at Most \(\ell \) Internally Disjoint Steiner Trees C

详细信息    查看全文

• 作者：Xueliang Li ; Yaping Mao
• 关键词：(Edge ; )connectivity ; Steiner tree ; Internally (edge ; )disjoint trees ; Packing ; generalized local (edge ; )connectivity ; 05C05 ; 05C35 ; 05C40 ; 05C70
• 刊名：Graphs and Combinatorics
• 出版年：2015
• 出版时间：November 2015
• 年：2015
• 卷：31
• 期：6
• 页码：2231-2259
• 全文大小：728 KB
• 参考文献：1.Bártfai P.: Solution of a problem proposed by P. Erd?s (in Hungarian). Mat. Lapok 11, 175-76 (1960)
  2.Beineke, L., Wilson, R.: Topics in Structural Graph Theory. Cambrige University Press, Cambrige (2013)MATH
  3.Beineke, L., Oellermann, O., Pippert, R.: The average connectivity of a graph. Discrete Math. 252, 31-5 (2002)MathSciNet CrossRef MATH
  4.Bollobás, B.: Extremal Graph Theory. Acdemic Press, New York (1978)MATH
  5.Bollobás, B.: On graphs with at most three independent paths connecting any two vertices. Studia Sci. Math. Hungar 1, 137-40 (1966)MathSciNet MATH
  6.Bollobás, B.: Cycles and semi-topological configurations. In: Alavi, Y., Lick, D.R. (eds.) Theory and Applications of Graphs. Lecture Notes in Maths, vol. 642, pp. 66-4. Springer, Berlin (1978)CrossRef
  7.Bondy, J.A., Murty, U.S.R.: Graph Theory, GTM 244. Springer, Berlin (2008)CrossRef
  8.Chartrand, G., Kapoor, S., Lesniak, L., Lick, D.: Generalized connectivity in graphs. Bull. Bombay Math. Colloq. 2, 1- (1984)
  9.Chartrand, G., Okamoto, F., Zhang, P.: Rainbow trees in graphs and generalized connectivity. Networks 55(4), 360-67 (2010)MathSciNet MATH
  10.Day, D., Oellermann, O., Swart, H.: The \(\ell \) -connectivity function of trees and complete multipartite graphs. J. Combin. Math. Combin. Comput. 10, 183-92 (1991)MathSciNet MATH
  11.Gusfield, D.: Connectivity and edge-disjoint spanning trees. Inform. Process. lett. 16, 87-9 (1983)MathSciNet CrossRef MATH
  12.Hager, M.: Pendant tree-connectivity. J. Combin. Theory Ser B 38, 179-89 (1985)MathSciNet CrossRef MATH
  13.Hind, H., Oellermann, O.: Menger-type results for three or more vertices. Congressus Numerantium 113, 179-04 (1996)MathSciNet MATH
  14.Jain, K., Mahdian, M., Salavatipour, M.: Packing Steiner trees. In: Proc. of the 14th \(ACM\) -\(SIAM\) symposium on Discterte Algorithms, Baltimore, pp. 266-74 (2003)
  15.Kriesell, M.: Edge-disjoint trees containing some given vertices in a graph. J. Combin. Theory Ser. B 88, 53-5 (2003)MathSciNet CrossRef MATH
  16.Kriesell, M.: Edge-disjoint Steiner trees in graphs without large bridges. J. Graph Theory 62, 188-98 (2009)MathSciNet CrossRef MATH
  17.Lau, L.: An approximate max-Steiner-tree-packing min-Steiner-cut theorem. Combinatorica 27, 71-0 (2007)MathSciNet CrossRef MATH
  18.Leonard, J.: On a conjecture of Bollobás and Edr?s. Period. Math. Hungar. 3, 281-84 (1973)MathSciNet CrossRef MATH
  19.Leonard, J.: On graphs with at most four edge-disjoint paths connecting any two vertices. J. Combin. Theory Ser. B 13, 242-50 (1972)MathSciNet CrossRef MATH
  20.Leonard, J.: Graphs with 6-ways. Canad. J. Math. 25, 687-92 (1973)MathSciNet CrossRef MATH
  21.Li, H., Li, X., Mao, Y.: On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices. Bull. Malays. Math. Sci. Soc. (2) 37(3), 747-56 (2014)
  22.Li, H., Li, X., Mao, Y., Sun, Y.: Note on the generalized 3-connectivity. Ars Combin. 114, 193-02 (2014)MathSciNet MATH
  23.Li, H., Li, X., Sun, Y.: The generalied 3-connectivity of Cartesian product graphs. Discrete Math. Theor. Comput. Sci. 14(1), 43-4 (2012)MathSciNet CrossRef MATH
  24.Li S., Li W., Li X.: The generalized connectivity of complete equipartition \(3\) -partite graphs. Bull. Malays. Math. Sci. Soc. (2) 37(1), 103-21 (2014)
  25.Li, S., Li, X.: Note on the hardness of generalized connectivity. J. Combin. Optim. 24, 389-96 (2012)CrossRef MATH
  26.Li, S., Li, X., Zhou, W.: Sharp bounds for the generalized connectivity \(\kappa _3(G)\) . Discrete Math. 310, 2147-163 (2010)MathSciNet CrossRef MATH
  27.Li, X., Mao, Y.: The generalized 3-connectivity of lexicographic product graphs. Discrete Math. Theor. Comput. Sci. 16(1), 339-54 (2014)MathSciNet MATH
  28.Li, X., Mao, Y., Sun, Y.: On the generalized (edge-)connectivity. Australas. J. Combin. 58(2), 304-19 (2014)MathSciNet MATH
  29.Mader, W.: Ein Extremalproblem des Zusammenhangs in Graphen. Math. Z. 131, 223-31 (1973)MathSciNet CrossRef MATH
  30.Mader, W.: Grad und lokaler Zusammenhang in endlichen Graphen. Math. Ann. 205, 9-1 (1973)MathSciNet CrossRef MATH
  31.Mader, W.: über die Maximalzahl kantendisjunkter A-Wege. Arch. Math. 30, 325-36 (1978)MathSciNet CrossRef MATH
  32.Mader, W.: über die Maximalzahl kreuzungsfreier H-Wege. Arch. Math. 31, 387-02 (1978)MathSciNet CrossRef
  33.Nash-Williams, CStJA: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 36, 445-50 (1961)MathSciNet CrossRef MATH
  34.Oellermann, O.: Connectivity and edge-connectivity in graphs: a survey. Congressus Numerantium 116, 231-52 (1996)MathSciNet MATH
  35.Oellermann, O.: On the \(\ell \) -connectivity of a graph. Graphs Combin. 3, 285-99 (1987)MathSciNet CrossRef MATH
  36.Oellermann, O.: A note on the \(\ell \) -connectivity function of a graph. Congressus Numerantium 60, 181-88 (1987)MathSciNet
  37.S?rensen B., Thomassen C.: On \(k\) -r
• 作者单位：Xueliang Li (1)
  Yaping Mao (1) (2)
  
  1. Center for Combinatorics and LPMC, Nankai University, Tianjin, 300071, China
  2. Department of Mathematics, Qinghai Normal University, Xining, 810008, Qinghai, China
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914

文摘

The maximum local connectivity was first introduced by Bollobás. The problem of determining the maximum number of edges in a graph with \(\overline{\kappa }\le \ell \) has been studied extensively. We consider a generalization of the above concept and problem. For \(S\subseteq V(G)\) and \(|S|\ge 2\), the generalized local connectivity \(\kappa (S)\) is the maximum number of internally disjoint trees connecting \(S\) in \(G\). The parameter \(\overline{\kappa }_k(G)=\max \{\kappa (S)\,|\,S\subseteq V(G),|S|=k\}\) is called the maximum generalized local connectivity of \(G\). In this paper the problem of determining the largest number \(f(n;\overline{\kappa }_k\le \ell )\) of edges for graphs of order \(n\) that have maximum generalized local connectivity at most \(\ell \) is considered. The exact value of \(f(n;\overline{\kappa }_k\le \ell )\) for \(k=n,n-1\) is determined. For a general \(k\), we construct a graph to obtain a sharp lower bound. Keywords (Edge-)connectivity Steiner tree Internally (edge-)disjoint trees Packing generalized local (edge-)connectivity