A sufficient condition for r - graphic sequences to be potentially

Abstract

An r-graph is a multigraph in which two vertices are joined by at most r edges. An r-complete graph on n vertices, denoted by , is an r-graph on n vertices in which each pair of vertices is joined by exactly r-edges. The r-split graph on l+m vertices is denoted by . A non increasing sequence p = (d, d, … , d) of non negative integers is said to be r-graphic if it is realizable by an r-graph on n vertices. An r-graphic sequence π is said to be potentially -graphic if it has a realization containing as a subgraph. In this paper, we obtain conditions for r-graphic sequences to be potentially and give a Rao-type characterizations for π to be potentially -graphic.

Subject Classification:

• 05C07
• 05C35

Keywords:

• r-graph
• r-split graph
• r-graphic sequence