The Jump Number of a Split Graph

摘要

In 1982, Jamison and Laskar introduced the concept of the jump number of a chordal graph. This parameter is defined as follows. Let φ be a perfect elimination ordering (PEO) of G. Then define j(φ) to be the number of nonadjacent consecutive pairs φ~(-1)(i)φ~(-1)(i + 1) of vertices in φ. The jump number j(G) of a chordal graph is then defined to be min{j(φ) | φ is a PEO of G}. In this paper we determine the jump number of a split graph.