Document Type : Research Paper

**Authors**

University of Kashmir

**Abstract**

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 simple 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}$. The complete product split graph on $L + M$ vertices is denoted by $\overline{S}_{L, M}=K_{L} \vee \overline{K}_{M}$, where $K_{L}$ and $K_{M}$ are complete graphs respectively on $L = \sum\limits_{i = 1}^{p}r_{i}$ and $M = \sum\limits_{i = 1}^{p}s_{i}$ vertices with $r_{i}$ and $s_{i}$ being integers. Another split graph is denoted by $S_{L, M} = \overline{S}_{r_{1}, s_{1}} \vee\overline{S}_{r_{2}, s_{2}} \vee \cdots \vee \overline{S}_{r_{p}, s_{p}}= (K_{r_{1}} \vee \overline{K}_{s_{1}})\vee (K_{r_{2}} \vee \overline{K}_{s_{2}})\vee \cdots \vee (K_{r_{p}} \vee \overline{K}_{s_{p}})$. A sequence $\pi=(d_{1}, d_{2},\ldots,d_{n})$ is said to be potentially $S_{L, M}$-graphic (respectively $\overline{S}_{L, M}$)-graphic if there is a realization $G$ of $\pi$ containing $S_{L, M}$ (respectively $\overline{S}_{L, M}$) as a subgraph. If $\pi$ has a realization $G$ containing $S_{L, M}$ on those vertices having degrees $d_{1}, d_{2},\ldots,d_{L+M}$, then $\pi$ is potentially $A_{L, M}$-graphic. A non-increasing sequence of non-negative integers $\pi = (d_{1}, d_{2},\ldots,d_{n})$ is potentially $A_{L, M}$-graphic if and only if it is potentially $S_{L, M}$-graphic. In this paper, we obtain the sufficient condition for a graphic sequence to be potentially $A_{L, M}$-graphic and this result is a generalization of that given by J. H. Yin on split graphs.

**Keywords**

**Main Subjects**

[1] P. Erdos and T. Gallai, Graphs with prescrib ed degrees (in Hungarian), *Matemoutiki Lapor*, **11** (1960) 264-274.

[2] R. J. Gould, M. S. Jacobson and J. Lehel, *Potentially G-graphical degree sequences*, in Combinatorics, Graph Theory, and Algorithms (Y. Alavi et al., eds.), **1,2**, Kalamazo o, MI, 1999 451-460.

[3] S. L. Hakimi, On realizability of a set of integers as degrees of the vertices of a linear graph, *I. J. Soc. Indust. Appl. Math.*, **10** (1962) 496-506.

[4] V. Havel, A Remark on the existance of nite graphs (Czech), *Casopis Pest. Mat.*, **80** (1955) 477-480.

[5] S. Pirzada, *An Introduction to Graph Theory*, Universities Press, Orient Blackswan, India, 2012.

[6] S. Pirzada and J. H. Yin, Degree sequences in graphs, *J. Math. Study*,** 39** (2006) 25-31

[7] S. Pirzada and Bilal A. Chat, Potentially graphic sequences of split graphs,* Kragujevac J. Math.*, **38** (2014) 73-81.

[8] S. Pirzada, Bilal A. Chat and Faro o q A. Dar, Graphical sequences of some family of induced subgraphs, *J. Algebra Comb. Discrete Struct. Appl.*, **2** (2015) 95-109.

[9] A. R. Rao, *An Erdos-Gallai type result on the clique numb er of a realization of a degree sequence*, Unpublished.

[10] A. R. Rao, *The clique number of a graph with given degree sequence*, Graph Theory, Proc. Symp. Calcutta 1976, ISI Lecture Notes,** 4** (A. R. Rao, ed.), 1979 251-267.

[11] J. H. Yin, A Havel-Hakimi typ e pro cedure and a suﬃcient condition for a sequence to be potentially S_{r,s}-graphic, *Czechoslovak Math. J.*, **62** (2012) 863-867.

March 2017

Pages 21-27

**Receive Date:**08 May 2014**Revise Date:**18 March 2016**Accept Date:**06 August 2016**Published Online:**01 March 2017