Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract) Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

On the Number of Connected Sets in Bounded Degree Graphs

verfasst von : Kustaa Kangas, Petteri Kaski, Mikko Koivisto, Janne H. Korhonen

Erschienen in: Graph-Theoretic Concepts in Computer Science

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

A set of vertices in a graph is connected if the set induces a connected subgraph. Using Shearer’s entropy lemma, we show that the number of connected sets in an \(n\)-vertex graph with maximum vertex degree \(d\) is \(O(1.9351^n)\) for \(d=3\), \(O(1.9812^n)\) for \(d=4\), and \(O(1.9940^n)\) for \(d=5\). Dually, we construct infinite families of generalized ladder graphs whose number of connected sets is bounded from below by \(\varOmega (1.5537^n)\) for \(d=3\), \(\varOmega (1.6180^n)\) for \(d=4\), and \(\varOmega (1.7320^n)\) for \(d=5\).

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel A Characterization of Mixed Unit Interval Graphs
Nächstes Kapitel Parameterized Edge Hamiltonicity
Fußnoten
Literatur
1.
Alon, N.: Independent sets in regular graphs and sum-free subsets of finite groups. Isr. J. Math. 73, 247–256 (1991)CrossRefMATH
2.
Binkele-Raible, D., Fernau, H., Gaspers, S., Liedloff, M.: Exact and parameterized algorithms for max internal spanning tree. Algorithmica 65(1), 95–128 (2013)MathSciNetCrossRefMATH
3.
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Computing the Tutte polynomial in vertex-exponential time. In: FOCS, pp. 677–686. IEEE Computer Society (2008)
4.
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Trimmed Moebius inversion and graphs of bounded degree. Theor. Comput. Syst. 47(3), 637–654 (2010)CrossRefMATH
5.
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: The traveling salesman problem in bounded degree graphs. ACM Trans. Algorithms 8(2), 18:1–18:13 (2012)CrossRef
6.
Bollobás, B.: The Art of Mathematics: Coffee Time in Memphis. Cambridge University Press (2006)
7.
Chung, F., Graham, R., Frankl, P., Shearer, J.: Some intersection theorems for ordered sets and graphs. J. Comb. Theor. Ser. A 43(1), 23–37 (1986)MathSciNetCrossRefMATH
8.
Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: exact and enumeration algorithms. Algorithmica 52(2), 293–307 (2008)MathSciNetCrossRefMATH
9.
Fomin, F.V., Grandoni, F., Pyatkin, A.V., Stepanov, A.A.: Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications. ACM Trans. Algorithms 5(1), 9:1–9:17 (2008)MathSciNetCrossRef
10.
Fomin, F.V., Villanger, Y.: Finding induced subgraphs via minimal triangulations. In: Marion, J.Y., Schwentick, T. (eds.) STACS. Volume 5 of LIPIcs., Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 383–394 (2010)
11.
12.
Galvin, D.: An upper bound for the number of independent sets in regular graphs. Discrete Math. 309(23–24), 6635–6640 (2009)MathSciNetCrossRefMATH
13.
Gaspers, S., Kratsch, D., Liedloff, M.: On independent sets and bicliques in graphs. Algorithmica 62(3–4), 637–658 (2012)MathSciNetCrossRefMATH
14.
15.
Kahn, J.: An entropy approach to the hard-core model on bipartite graphs. Combin. Probab. Comput. 10, 219–237 (2001)MathSciNetMATH
16.
17.
Perrier, E., Imoto, S., Miyano, S.: Finding optimal Bayesian network given a super-structure. J. Mach. Learn. Res. 9, 2251–2286 (2008)MathSciNetMATH
18.
Metadaten
Titel
On the Number of Connected Sets in Bounded Degree Graphs
verfasst von
Kustaa Kangas
Petteri Kaski
Mikko Koivisto
Janne H. Korhonen
Copyright-Jahr
2014
Buch
Graph-Theoretic Concepts in Computer Science

Print ISBN: 978-3-319-12339-4

Electronic ISBN: 978-3-319-12340-0

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-319-12340-0_28