پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 44 |
| تعداد شمارهها | 1,877 |
| تعداد مقالات | 15,278 |
| تعداد مشاهده مقاله | 43,730,750 |
| تعداد دریافت فایل اصل مقاله | 17,563,091 |
The condition for a sequence to be potentially $A_{L, M}$- graphic | ||
| Transactions on Combinatorics | ||
| مقاله 3، دوره 6، شماره 1، خرداد 2017، صفحه 21-27 اصل مقاله (361.02 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2017.20361 | ||
| نویسندگان | ||
| Shariefuddin Pirzada* ؛ Bilal A. Chat | ||
| University of Kashmir | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Split graph؛ complete product split graph؛ potentially $H$-graphic Sequences | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 1,355 تعداد دریافت فایل اصل مقاله: 1,080 |
||