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:
Using Synthetic Networks for Parameter Tuning in Community Detection Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

Strongly n-e.c. Graphs and Independent Distinguishing Labellings

verfasst von : Christopher Duffy, Jeannette Janssen

Erschienen in: Algorithms and Models for the Web Graph

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

A countable graph G is n-ordered if its vertices can be enumerated so each vertex has no more than n neighbours appearing earlier in the enumeration. Here we consider both deterministic and probabilistic methods to produce n-ordered countable graphs with universal adjacency properties. In the countably infinite case, we show that such universal adjacency properties imply the existence an independent 2-distinguishing labelling.

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 Almost Exact Recovery in Label Spreading
Nächstes Kapitel The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs
Literatur
1.
Abbasi, A., Hossain, L., Leydesdorff, L.: Betweenness centrality as a driver of preferential attachment in the evolution of research collaboration networks. J. Inf. 6(3), 403–412 (2012)
2.
3.
Albertson, M.O., Collins, K.L.: Symmetry breaking in graphs. Electron. J. Comb. 3(1), 18 (1996)MathSciNetMATH
4.
Balachandran, N., Padinhatteeri, S.: Distinguishing chromatic number of random Cayley graphs. Discrete Math. 340(10), 2447–2455 (2017)MathSciNetMATHCrossRef
5.
6.
Barabási, A.L., Bonabeau, E.: Scale-free networks. Sci. Am. 288(5), 60–69 (2003)CrossRef
7.
Benzi, M., Klymko, C.: On the limiting behavior of parameter-dependent network centrality measures. SIAM J. Matrix Anal. Appl. 36(2), 686–706 (2015)MathSciNetMATHCrossRef
8.
Bonato, A.: The search for n-e.c. graphs. Contrib. Discret. Math. 4(1), 40–53 (2009)MATH
9.
10.
11.
Cameron, P.J.: The random graph revisited. Eur. Congr. Math. 1, 267–274 (2000)MATH
12.
Cheng, C.T.: On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results. Discrete Math. 309(16), 5169–5182 (2009)MathSciNetMATHCrossRef
13.
Choi, J.O., Hartke, S.G., Kaul, H.: Distinguishing chromatic number of Cartesian products of graphs. SIAM J. Discret. Math. 24(1), 82–100 (2010)MathSciNetMATHCrossRef
14.
Collins, K.L., Trenk, A.N.: The distinguishing chromatic number. Electron. J. Comb. 13(1), 16 (2006)MathSciNetMATH
15.
Deijfen, M., Van Den Esker, H., Van Der Hofstad, R., Hooghiemstra, G.: A preferential attachment model with random initial degrees. Arkiv för Matematik 47(1), 41–72 (2009)MathSciNetMATHCrossRef
16.
17.
Eschen, E.M., Hoàng, C.T., Sritharan, R., Stewart, L.: On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two. Discrete Math. 311(6), 431–434 (2011)MathSciNetMATHCrossRef
18.
Flaxman, A.D., Frieze, A.M., Vera, J.: A geometric preferential attachment model of networks. Internet Math. 3(2), 187–205 (2006)MathSciNetMATHCrossRef
19.
Imrich, W., Klavžar, S., Trofimov, V.: Distinguishing infinite graphs. Electron. J. Comb. 14(1), R36 (2007)MathSciNetMATH
20.
Laflamme, C., Sauer, N., et al.: Distinguishing number of countable homogeneous relational structures. Electron. J. Comb. 17(1), R20 (2010)MathSciNetMATH
21.
De Solla Price, D.: A general theory of bibliometric and other cumulative advantage processes. J. Am. Soc. Inf. Sci. 27(5), 292–306 (1976)CrossRef
22.
Ravasz, E., Barabási, A.L.: Hierarchical organization in complex networks. Phys. Rev. E 67(2), 026112 (2003)MATHCrossRef
23.
Russell, A., Sundaram, R.: A note on the asymptotics and computational complexity of graph distinguishability. Electron. J. Comb. 5(1), 23 (1998)MathSciNetMATH
24.
Telesford, Q.K., Joyce, K.E., Hayasaka, S., Burdette, J.H., Laurienti, P.J.: The ubiquity of small-world networks. Brain Connect. 1(5), 367–375 (2011)CrossRef
25.
Wang, Z., Scaglione, A., Thomas, R.J.: Generating statistically correct random topologies for testing smart grid communication and control networks. IEEE Trans. Smart Grid 1(1), 28–39 (2010)CrossRef
26.
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440 (1998)MATHCrossRef
Metadaten
Titel
Strongly n-e.c. Graphs and Independent Distinguishing Labellings
verfasst von
Christopher Duffy
Jeannette Janssen
Copyright-Jahr
2019
Buch
Algorithms and Models for the Web Graph

Print ISBN: 978-3-030-25069-0

Electronic ISBN: 978-3-030-25070-6

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-030-25070-6_4