Potentially Graphic Sequences Of Split Graphs

S. Pirzada ; Bilal A. Chat

Kragujevac Journal of Mathematics, Tome 38 (2014) no. 1, p. 73

Résumé

A sequence $\pi=({d_1,d_2,\ldots,d_n})$ of non-negative integers is said to be graphic if it is the degree sequence of a simple $G$ on $n$ vertices, and such a graph $G$ is referred to as a realization of $\pi$. The set of all non-increasing non-negative integer sequences $\pi=(d_1,d_2,\ldots,d_n)$ is denoted by $NS_n$. A sequence $\pi\in NS_{n}$ is said to be graphic if it is the degree sequence of a graph $G$ on $n$ vertices, and such a graph G is called a realization of $\pi$. The set of all graphic sequences in $NS_{n}$ is denoted by $GS_{n}$. A split graph $K_{r}+\overline{K_{s}}$ on $r+s$ vertices is denoted by $S_{r,s}$. A graphic sequence $\pi$ is potentially $H$-graphic if there is a realizaton of $\pi$ containing $H$ as a subgraph. In this paper, we determine the graphic sequences of subgraphs $H$, where $H$ is $S_{r_{1},s_{1}} + S_{r_{2}, s_{2}} + S_{r_{3},s_{3}} + \ldots + S_{r_{m},s_{m}}$, $S_{r_{1},s_{1}}\vee S_{r_{2},s_{2}}\vee \ldots \vee S_{r_{m}, s_{m}}$ and $S_{r_{1},s_{1}} \times S_{r_{2},s_{2}}\times \ldots \times S_{r_{m},s_{m}}$ and $+$, $V$ and $\times$ denotes the standard join operation, the normal join operation and the cartesian product in these graphs respectively. @filename: kjom3801-05.pdf

Détail

Classification : 05C07
Keywords: Graph, Split graph, Potentially H-graphical sequences