On multigraphic and potentially multigraphic sequences

Abstract

An r-graph(or a multigraph) is a loopless graph in which no two vertices are joined by more than r edges. An r-complete graph on n vertices, denoted by Kn(r) , is an r-graph on n vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π = (d1, d2, ..., dn) 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 SL;M(r) -graphic if it has a realization containing SL;M(r) as a subgraph. We obtain conditions for an r-graphic sequence to be potentially S(r) L;M-graphic. These are generalizations from split graphs to p-tuple r-split graph.

Keywords

• 05c07
• multigraph
• multigraphic sequence
• potentially multigraphic sequences
• split graph