The splitting number of complete bipartite graphs (Q793047)

From MaRDI portal
Revision as of 11:05, 30 January 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
The splitting number of complete bipartite graphs
scientific article

    Statements

    The splitting number of complete bipartite graphs (English)
    0 references
    0 references
    0 references
    1984
    0 references
    A new and interesting topological invariant of graphs, called splitting number, is introduced to measure, in a way, the ''closeness to embeddability on a surface''. The splitting number \(sp_ S(G)\) of a graph G (with respect to a closed surface S) is defined as the smallest number of vertex splittings (i.e., replacing a vertex v by two non-adjacent vertices \(v_ 1\), \(v_ 2\) in such a way that every vertex formerly adjacent to v is joined to at least one of \(v_ 1\), \(v_ 2)\) needed to transform G into a graph embeddable on S. It is proved that for any surface S (orientable or not) of Euler characteristic E(S), \[ sp_ S(K_{m,n})=\max(\lceil(m-2)(n-2)/2\rceil -2+E(S),0). \] This yields a new way of obtaining the well known orientable and non-orientable genus formulas for complete bipartite graphs.
    0 references
    complete bipartite graph
    0 references
    embedding of graphs on surfaces
    0 references
    splitting number
    0 references

    Identifiers