scientific article; zbMATH DE number 3871399

From MaRDI portal
Publication:3338280





[For the entire collection see Zbl 0534.00004.] Let \(G^ x(p,q)\) be a class of all graphs G with p vertices, q edges and edge connectivity \(\lambda (G)=\lfloor 2q/p\rfloor\). For each vertex v of G let w(v) be such a weight of v that w(v)\(\leq w(u)\) if deg \(v\leq\deg u\). If \(G\in G^ x(p,q)\) and D is a \(\lambda\) -cutset of G (cutset with \(\lambda =\lfloor 2q/p\rfloor\) edges) which separates G into two disjoint graphs \(G_ 1\) and \(G_ 2\) then define \(f(D)=\max\{w(v);\quad v\in V(G_ 1)\}+\max\{w(u);\quad u\in V(G_ 2)\}\) and \(F(G)=\max\{f(D);\) D is a \(\lambda\) -cutset of \(G\}\). The author studies graphs which minimize F(G) among all graphs in \(G^ x(p,q)\) and gives examples of such graphs for each \(p\leq q<3/2 p,\) i.e. \(\lambda =2\).











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3338280)