Pirzada, S., A. Chat, B. (2017). The condition for a sequence to be potentially $A_{L, M}$- graphic. Transactions on Combinatorics, 6(1), 21-27. doi: 10.22108/toc.2017.20361

Shariefuddin Pirzada; Bilal A. Chat. "The condition for a sequence to be potentially $A_{L, M}$- graphic". Transactions on Combinatorics, 6, 1, 2017, 21-27. doi: 10.22108/toc.2017.20361

Pirzada, S., A. Chat, B. (2017). 'The condition for a sequence to be potentially $A_{L, M}$- graphic', Transactions on Combinatorics, 6(1), pp. 21-27. doi: 10.22108/toc.2017.20361

Pirzada, S., A. Chat, B. The condition for a sequence to be potentially $A_{L, M}$- graphic. Transactions on Combinatorics, 2017; 6(1): 21-27. doi: 10.22108/toc.2017.20361

The condition for a sequence to be potentially $A_{L, M}$- graphic

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.

[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.