Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Using Synthetic Networks for Parameter Tuning in Community Detection Read chapter Read first chapter

2019 | OriginalPaper | Chapter

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

Authors : Christopher Duffy, Jeannette Janssen

Published in: Algorithms and Models for the Web Graph

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Almost Exact Recovery in Label Spreading
next chapter The Robot Crawler Model on Complete k-Partite and Erdős-Rényi Random Graphs
Literature
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.
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
Metadata
Title
Strongly n-e.c. Graphs and Independent Distinguishing Labellings
Authors
Christopher Duffy
Jeannette Janssen
Copyright Year
2019
Book
Algorithms and Models for the Web Graph

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

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

Copyright Year: 2019

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

Premium Partner

    Image Credits