Separation index of a graph

From MaRDI portal





The separation index of a graph \(G\) is defined as the minimum number \(k\) of vertices \(v_1,\dots,v_k\) of \(G\) such that for every pair \(x,y\) of vertices of \(G\), the stabilizer of \(v_i\) in Aut(\(G\)) has \(x\) and \(y\) in distinct orbits, for some \(i\) with \(1\leq i \leq k\). It is proved that the separation index of any 3-connected planar graph is at most 3. A generalization of this result to 3-connected graphs that are uniquely embeddable in a surface of negative Euler characteristic is given. The author mentions that the separation index of every complete \(r\)-partite graph of order \(n\) is equal to \(n-r\). However, this is true only when at most one of the partite classes of the graph consists of a single vertex.











This page was built for publication: Separation index of a graph

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