Skip to main content
Erschienen in: Journal of Combinatorial Optimization 1/2017

10.09.2015

On the difference of two generalized connectivities of a graph

verfasst von: Yuefang Sun, Xueliang Li

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2017

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The concept of k-connectivity \(\kappa '_{k}(G)\) of a graph G, introduced by Chartrand in 1984, is a generalization of the cut-version of the classical connectivity. Another generalized connectivity of a graph G, named the generalized k-connectivity \(\kappa _{k}(G)\), mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. In this paper, we get the lower and upper bounds for the difference of these two parameters by showing that for a connected graph G of order n, if \(\kappa '_k(G)\ne n-k+1\) where \(k\ge 3\), then \(0\le \kappa '_k(G)-\kappa _k(G)\le n-k-1\); otherwise, \(-\lfloor \frac{k}{2}\rfloor +1\le \kappa '_k(G)-\kappa _k(G)\le n-k\). Moreover, all of these bounds are sharp. Some specific study is focused for the case \(k=3\). As results, we characterize the graphs with \(\kappa '_3(G)=\kappa _3(G)=t\) for \(t\in \{1, n-3, n-2\}\), and give a necessary condition for \(\kappa '_3(G)=\kappa _3(G)\) by showing that for a connected graph G of order n and size m, if \(\kappa '_3(G)=\kappa _3(G)=t\) where \(1\le t\le n-3\), then \(m\le {n-2\atopwithdelims ()2}+2t\). Moreover, the unique extremal graph is given for the equality to hold.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Chartrand G, Kappor SF, Lesniak L, Lick DR (1984) Generalized connectivity in graphs. Bull Bombay Math Colloq 2:1–6 Chartrand G, Kappor SF, Lesniak L, Lick DR (1984) Generalized connectivity in graphs. Bull Bombay Math Colloq 2:1–6
Zurück zum Zitat Chartrand G, Okamoto F, Zhang P (2010) Rainbow trees in graphs and generalized connectivity. Networks 55(4):360–367MathSciNetMATH Chartrand G, Okamoto F, Zhang P (2010) Rainbow trees in graphs and generalized connectivity. Networks 55(4):360–367MathSciNetMATH
Zurück zum Zitat Day DP, Oellermann OR, Swart HC (1991) The \(\ell \)-connectivity function of trees and complete multipartite graphs. J Combin Math Combin Comput 10:183–192MathSciNetMATH Day DP, Oellermann OR, Swart HC (1991) The \(\ell \)-connectivity function of trees and complete multipartite graphs. J Combin Math Combin Comput 10:183–192MathSciNetMATH
Zurück zum Zitat Gu R, Li X, Shi Y (2014) The generalized 3-connectivity of random graphs. Acta Math Sinica 57(2):321–330 (in Chinese)MATH Gu R, Li X, Shi Y (2014) The generalized 3-connectivity of random graphs. Acta Math Sinica 57(2):321–330 (in Chinese)MATH
Zurück zum Zitat 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 (in press) 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 (in press)
Zurück zum Zitat Li H, Li X, Mao Y, Sun Y (2014) Note on the generalized connectivity. Ars Combin 114:193–202MathSciNetMATH Li H, Li X, Mao Y, Sun Y (2014) Note on the generalized connectivity. Ars Combin 114:193–202MathSciNetMATH
Zurück zum Zitat Li H, Li X, Sun Y (2012) The generalized 3-connectivity of Cartesian product graphs. Discrete Math Theor Comput Sci 14(1):43–54MathSciNetCrossRefMATH Li H, Li X, Sun Y (2012) The generalized 3-connectivity of Cartesian product graphs. Discrete Math Theor Comput Sci 14(1):43–54MathSciNetCrossRefMATH
Zurück zum Zitat Li X, Mao Y (in press) On extremal graphs with at most \(\ell \) vertices. Graphs Combin Li X, Mao Y (in press) On extremal graphs with at most \(\ell \) vertices. Graphs Combin
Zurück zum Zitat Li X, Mao Y (2014) The generalized 3-connectivity of lexicographic product graphs. Discrete Math Theor Comput Sci 16(1):339–354MathSciNetMATH Li X, Mao Y (2014) The generalized 3-connectivity of lexicographic product graphs. Discrete Math Theor Comput Sci 16(1):339–354MathSciNetMATH
Zurück zum Zitat Li X, Mao Y, Sun Y (2014) On the generalized (edge-)connectivity of graphs. Australasian J Combin 58:304–319MathSciNetMATH Li X, Mao Y, Sun Y (2014) On the generalized (edge-)connectivity of graphs. Australasian J Combin 58:304–319MathSciNetMATH
Zurück zum Zitat Oellermann OR (1987) A note on the \(\ell \)-connectivity function of a graph. Congessus Numerantium 60:181–188MathSciNet Oellermann OR (1987) A note on the \(\ell \)-connectivity function of a graph. Congessus Numerantium 60:181–188MathSciNet
Zurück zum Zitat Sun Y (2014) Generalized 3-(edge)-connectivity for undirected double-loop networks. J Discrete Math Sci Cryptogr 17(1):19–28MathSciNetCrossRefMATH Sun Y (2014) Generalized 3-(edge)-connectivity for undirected double-loop networks. J Discrete Math Sci Cryptogr 17(1):19–28MathSciNetCrossRefMATH
Zurück zum Zitat Sun Y (2015a) Generalized 3-edge-connectivity of Cartesian product graphs. Czechoslovak Math J 65(1):107–117 Sun Y (2015a) Generalized 3-edge-connectivity of Cartesian product graphs. Czechoslovak Math J 65(1):107–117
Zurück zum Zitat Sun Y (2015b) Generalized 3-connectivity and 3-edge-connectivity for the Cartesian products of some graph classes. J Combin Math Combin Comput 94:215–225 Sun Y (2015b) Generalized 3-connectivity and 3-edge-connectivity for the Cartesian products of some graph classes. J Combin Math Combin Comput 94:215–225
Zurück zum Zitat Sun Y (2015c) Maximum generalized local connectivities of cubic Cayley graphs on Abelian groups. J Combin Math Combin Comput 94:227–236 Sun Y (2015c) Maximum generalized local connectivities of cubic Cayley graphs on Abelian groups. J Combin Math Combin Comput 94:227–236
Metadaten
Titel
On the difference of two generalized connectivities of a graph
verfasst von
Yuefang Sun
Xueliang Li
Publikationsdatum
10.09.2015
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 1/2017
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-015-9956-9

Weitere Artikel der Ausgabe 1/2017

Journal of Combinatorial Optimization 1/2017 Zur Ausgabe