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

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 sufficient condition for a sequence to be potentially Sr,s-graphic, Czechoslovak Math. J., 62 (2012) 863-867.