On extremal k-outconnected graphs

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


Let G be a minimally k-connected graph with n nodes and m edges. Mader proved that if n ≥ 3 k - 2 then m ≤ k (n - k), and for n ≥ 3 k - 1 an equality is possible if, and only if, G is the complete bipartite graph Kk, n - k. Cai proved that if n ≤ 3 k - 2 then m ≤ ⌊ (n + k)2 / 8 ⌋, and listed the cases when this bound is tight. In this paper we prove a more general theorem, which implies similar results for minimally k-outconnected graphs; a graph is called k-outconnected from r if it contains k internally disjoint paths from r to every other node.

שפה מקוריתאנגלית
עמודים (מ-עד)2533-2543
מספר עמודים11
כתב עתDiscrete Mathematics
מספר גיליון12
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 28 יוני 2008

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On extremal k-outconnected graphs'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי