Glossary of graph theory: Difference between revisions

{{defn|The [[achromatic number]] of a graph is the maximum number of colors in a complete coloring.<ref>{{citation|last1=Farber|first1=M.|last2=Hahn|first2=G.|last3=Hell|first3=P.|author3-link=Pavol Hell|last4=Miller|first4=D. J.|title=Concerning the achromatic number of graphs|journal=[[Journal of Combinatorial Theory]], Series B|volume=40|issue=1|year=1986|pages=21–39|doi=10.1016/0095-8956(86)90062-6|doi-access=free}}.</ref>}}

{{defn|no=2|The relation between two distinct edges that share an end vertex.<ref name="diestel">{{citation|title=Graph Theory|year=2017|publisher=Springer-Verlag|location=Berlin, New York|first=Reinhard|last=Diestel|chapter=1.1 Graphs|series=Graduate Texts in Mathematics|volume=173|pages=3|edition=5th|doi=10.1007/978-3-662-53622-3|isbn=978-3-662-53621-6}}.</ref>}}

{{defn|A cherry is a path on three vertices.<ref>{{citation|last1=Sudakov|first1=Benny|last2=Volec|first2=Jan|title=Properly colored and rainbow copies of graphs with few cherries|journal=[[Journal of Combinatorial Theory]], Series B|volume=122|issue=1|year=2017|pages=391–416|doi=10.1016/j.jctb.2016.07.001|doi-access=free|arxiv=1504.06176}}.</ref>}}

{{defn|A [[small-world network]] is a graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other node by a small number of hops or steps. Specifically, a small-world network is defined to be a graph where the typical distance ''L'' between two randomly chosen nodes (the number of steps required) grows proportionally to the logarithm of the number of nodes ''N'' in the network <ref>{{cite journal|title=Collective dynamics of 'small-world' networks|first1=Duncan J.|last1=Watts|first2=Steven H.|last2=Strogatz|date=June 1998|journal=Nature|volume=393|issue=6684|pages=440–442|doi=10.1038/30918|bibcode=1998Natur.393..440W|pmid=9623998|s2cid=4429113}}</ref>}}