Abstrakt. Denna artikel studerar märkningsscheman för vertex konnektivitet funktion på allmänna grafer. Vi anser att problemet med att tilldela korta etiketter till noderna i någon n-node graf är ett sådant sätt att med tanke på etiketter på två noder u och v, man kan bestämma om u och v är k-vertex ansluten i G, det vill säga, om det finns k vertex disjoint banor som ansluter u och v. Denna artikel fastställer en övre gräns för k 2 log n på antalet bitar som används i en etikett. Den bästa tidigare övre gränsen för etikettstorleken för ett sådant märkningsschema är 2 k log n.
Det vertex-anslutningsmärkningssystem som beskrivs i REF är det mest relaterade till vårt sammanhang.
Labeling schemes for vertex connectivity
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}