Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graphic sequence; potentially $H$-graphic sequence; potential-Ramsey number
graphic sequence; potentially $H$-graphic sequence; potential-Ramsey number
Summary:
A nonincreasing sequence $\pi =(d_1,\ldots ,d_n)$ of nonnegative integers is a graphic sequence if it is realizable by a simple graph $G$ on $n$ vertices. In this case, $G$ is referred to as a realization of $\pi $. Given two graphs $G_1$ and $G_2$, A. Busch et al. (2014) introduced the potential-Ramsey number of $G_1$ and $G_2$, denoted by $r_{\rm pot}(G_1,G_2)$, as the smallest nonnegative integer $m$ such that for every $m$-term graphic sequence $\pi $, there is a realization $G$ of $\pi $ with $G_1\subseteq G$ or with $G_2\subseteq \bar {G}$, where $\bar {G}$ is the complement of $G$. For $t\ge 2$ and $0\le k\le \lfloor \frac {t}{2}\rfloor $, let $K_t^{-k}$ be the graph obtained from $K_t$ by deleting $k$ independent edges. We determine $r_{\rm pot}(K_n,K_t^{-k})$ for $t\ge 3$, $1\le k\le \lfloor \frac {t}{2}\rfloor $ and $n\ge \lceil \sqrt {2k}\rceil +2$, which gives the complete solution to a result in J. Z. Du, J. H. Yin (2021).
References:
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. American Elsevier, New York (1976). MR 0411988 | Zbl 1226.05083
[2] Busch, A., Ferrara, M. J., Hartke, S. G., Jacobson, M. S.: A degree sequence variant of graph Ramsey numbers. Graphs Comb. 30 (2014), 847-859. DOI 10.1007/s00373-013-1307-y | MR 3223948 | Zbl 1298.05078
[3] Busch, A., Ferrara, M. J., Hartke, S. G., Jacobson, M. S., Kaul, H., West, D. B.: Packing of graphic $n$-tuples. J. Graph Theory 70 (2012), 29-39. DOI 10.1002/jgt.20598 | MR 2916065 | Zbl 1243.05191
[4] Du, J., Yin, J.: A further result on the potential-Ramsey number of $G_1$ and $G_2$. Filomat 36 (2019), 1605-1617. DOI 10.2298/FIL1906605D | MR 4034026
[5] Du, J.-Z., Yin, J.-H.: A new lower bound on the potential-Ramsey number of two graphs. Acta Math. Appl. Sin., Engl. Ser. 37 (2021), 176-182. DOI 10.1007/s10255-021-0999-7 | MR 4196622 | Zbl 1464.05043
[6] Dvořák, Z., Mohar, B.: Chromatic number and complete graph substructures for degree sequences. Combinatorica 33 (2013), 513-529. DOI 10.1007/s00493-013-2649-z | MR 3132924 | Zbl 1313.05117
[7] Erdős, P., Gallai, T.: Graphs with prescribed degrees of vertices. Mat. Lapok 11 (1960), 264-274 Hungarian. MR 1964326 | Zbl 0103.39701
[8] Erdős, P., Jacobson, M. S., Lehel, J.: Graphs realizing the same degree sequences and their respective clique numbers. Graph Theory, Combinatorics and Applications. Vol. 1 John Wiley & Sons, New York (1991), 439-449. MR 1170797 | Zbl 0840.05093
[9] Ferrara, M. J., Lesaulnier, T. D., Moffatt, C. K., Wenger, P. S.: On the sum necessary to ensure a degree sequence is potentially $H$-graphic. Combinatorica 36 (2016), 687-702. DOI 10.1007/s00493-015-2986-1 | MR 3597587 | Zbl 1399.05038
[10] Ferrara, M. J., Schmitt, J.: A general lower bound for potentially $H$-graphic sequences. SIAM J. Discrete Math. 23 (2009), 517-526. DOI 10.1137/080715275 | MR 2476846 | Zbl 1215.05036
[11] Gould, R. J., Jacobson, M. S., Lehel, J.: Potentially $G$-graphical degree sequences. Combinatorics, Graph Theory and Algorithms. Vol. I New Issues Press, Kalamazoo (1999), 451-460. MR 1985076
[12] Hakimi, S. L.: On realizability of a set of integers as degrees of vertices of a linear graph. I. J. Soc. Ind. Appl. Math. 10 (1962), 496-506. DOI 10.1137/0110037 | MR 0148049 | Zbl 0109.16501
[13] Havel, V.: A remark on the existence of finite graphs. Čas. Pěstován{'ı Mat. 80 (1955), 477-480 Czech. DOI 10.21136/CPM.1955.108220 | MR 0089165 | Zbl 0068.37202
[14] Rao, A. R.: The clique number of a graph with a given degree sequence. Proceedings of the Symposium on Graph Theory ISI Lecture Notes 4. Macmillan, New Delhi (1979), 251-267. MR 0553948 | Zbl 0483.05038
[15] Robertson, N., Song, Z.-X.: Hadwiger number and chromatic number for near regular degree sequences. J. Graph Theory 64 (2010), 175-183. DOI 10.1002/jgt.20447 | MR 2674490 | Zbl 1209.05098
[16] Yin, J., Li, J.: A variation of a conjecture due to Erdős and Sós. Acta Math. Sin., Engl. Ser. 25 (2009), 795-802. DOI 10.1007/s10114-009-7260-2 | MR 2505310 | Zbl 1229.05161
[17] Yin, J.-H., Li, J.-S.: Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size. Discrete Math. 301 (2005), 218-227. DOI 10.1016/j.disc.2005.03.028 | MR 2171314 | Zbl 1119.05025
[18] Yin, J.-H., Meng, L., Yin, M.-X.: Graphic sequences and split graphs. Acta Math. Appl. Sin., Engl. Ser. 32 (2016), 1005-1014. DOI 10.1007/s10255-016-0622-5 | MR 3552867 | Zbl 1410.05027
Search
Partner of
