I denna not bekräftar vi ett antagande som tagits upp av Benjamini et al. [BST13] på bekant tid av grafer, visar att för alla grafer G med n hörn det håller att AC(G) = O(n 3/2 ), som är tight upp till en multiplikativ konstant. Detta görs genom att bevisa att för alla grafer G med n hörn och maximal grad  och det håller att AC(G) ≤ 20 skan. Genom att kombinera detta med den bundna AC(G) ≤ O(n 2 / ska) från [BST13] ges ovanstående enhetliga övre gräns för alla n-vertexdiagram. Vi bevisar också att för n-vertex sökväg P n det håller att AC(P n ) = n − 2. Dessutom visar vi att skivstångsgrafen B n som består av två klichéer av storlekar n/2 och n/2 som är anslutna med en enda kant också har AC(B n ) = n − 2. Detta visar att det är möjligt att lägga till (n 2 ) kanter till P n utan att ändra AC-värdet på grafen.
I REF, författarna visar en övre gräns för O( skan) om bekantskapstiden för en graf, där  till är den maximala graden och n är antalet noder av grafen.
A Tight Upper Bound on Acquaintance Time of Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}