On potentially H -graphic sequences

Meng Xiao Yin; Jian Hua Yin

Czechoslovak Mathematical Journal (2007)

  • Volume: 57, Issue: 2, page 705-724
  • ISSN: 0011-4642

Abstract

top
For given a graph H , a graphic sequence π = ( d 1 , d 2 , ... , d n ) is said to be potentially H -graphic if there is a realization of π containing H as a subgraph. In this paper, we characterize the potentially ( K 5 - e ) -positive graphic sequences and give two simple necessary and sufficient conditions for a positive graphic sequence π to be potentially K 5 -graphic, where K r is a complete graph on r vertices and K r - e is a graph obtained from K r by deleting one edge. Moreover, we also give a simple necessary and sufficient condition for a positive graphic sequence π to be potentially K 6 -graphic.

How to cite

top

Yin, Meng Xiao, and Yin, Jian Hua. "On potentially $H$-graphic sequences." Czechoslovak Mathematical Journal 57.2 (2007): 705-724. <http://eudml.org/doc/31157>.

@article{Yin2007,
abstract = {For given a graph $H$, a graphic sequence $\pi =(d_1,d_2,\ldots ,d_n)$ is said to be potentially $H$-graphic if there is a realization of $\pi $ containing $H$ as a subgraph. In this paper, we characterize the potentially $(K_5-e)$-positive graphic sequences and give two simple necessary and sufficient conditions for a positive graphic sequence $\pi $ to be potentially $K_5$-graphic, where $K_r$ is a complete graph on $r$ vertices and $K_r-e$ is a graph obtained from $K_r$ by deleting one edge. Moreover, we also give a simple necessary and sufficient condition for a positive graphic sequence $\pi $ to be potentially $K_6$-graphic.},
author = {Yin, Meng Xiao, Yin, Jian Hua},
journal = {Czechoslovak Mathematical Journal},
keywords = {graph; degree sequence; potentially $H$-graphic sequence; graph; degree sequence; potentially -graphic sequence},
language = {eng},
number = {2},
pages = {705-724},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On potentially $H$-graphic sequences},
url = {http://eudml.org/doc/31157},
volume = {57},
year = {2007},
}

TY - JOUR
AU - Yin, Meng Xiao
AU - Yin, Jian Hua
TI - On potentially $H$-graphic sequences
JO - Czechoslovak Mathematical Journal
PY - 2007
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 57
IS - 2
SP - 705
EP - 724
AB - For given a graph $H$, a graphic sequence $\pi =(d_1,d_2,\ldots ,d_n)$ is said to be potentially $H$-graphic if there is a realization of $\pi $ containing $H$ as a subgraph. In this paper, we characterize the potentially $(K_5-e)$-positive graphic sequences and give two simple necessary and sufficient conditions for a positive graphic sequence $\pi $ to be potentially $K_5$-graphic, where $K_r$ is a complete graph on $r$ vertices and $K_r-e$ is a graph obtained from $K_r$ by deleting one edge. Moreover, we also give a simple necessary and sufficient condition for a positive graphic sequence $\pi $ to be potentially $K_6$-graphic.
LA - eng
KW - graph; degree sequence; potentially $H$-graphic sequence; graph; degree sequence; potentially -graphic sequence
UR - http://eudml.org/doc/31157
ER -

References

top
  1. Graphs realizing the same degree sequences and their respective clique numbers, in: Y. Alavi et al., (Eds.), Graph Theory, Combinatorics and Applications, Vol. 1, John Wiley & Sons, New York, 1991, pp. 439–449. (1991) MR1170797
  2. On potentially K 4 - e -graphic, Australasian J. Combinatorics 29 (2004), 59–65. (2004) MR2037333
  3. Potentially G -graphical degree sequences, in: Y. Alavi et al., (Eds.), Combinatorics, Graph Theory, and Algorithms, Vol. 1, New Issues Press, Kalamazoo Michigan, 1999, pp. 451–460. (1999) MR1985076
  4. Degree sequences of graphs with prescribed clique size, in: Y. Alavi et al., (Eds.), Combinatorics, Graph Theory, and Algorithms, Vol. 2, New Issues Press, Kalamazoo Michigan, 1999, pp. 535–544. (1999) MR1985084
  5. 10.1016/0012-365X(73)90037-X, Discrete Math. 6 (1973), 79–88. (1973) MR0327559DOI10.1016/0012-365X(73)90037-X
  6. 10.1016/S0012-365X(99)00289-7, Discrete Math. 212 (2000), 223–231. (2000) MR1748652DOI10.1016/S0012-365X(99)00289-7
  7. 10.1002/(SICI)1097-0118(199810)29:2<63::AID-JGT2>3.0.CO;2-A, J. Graph Theory 29 (1998), 63–72. (1998) MR1644418DOI10.1002/(SICI)1097-0118(199810)29:2<63::AID-JGT2>3.0.CO;2-A
  8. 10.1007/BF02879940, Science in China, Ser. A 41 (1998), 510–520. (1998) MR1663175DOI10.1007/BF02879940
  9. 10.1007/s100120100006, Southeast Asian Bulletin of Mathematics 25 (2001), 427–434. (2001) MR1933948DOI10.1007/s100120100006
  10. On potentially C k -graphic sequences, Ars Combinatoria 64 (2002), 301–318. (2002) MR1914218
  11. On potentially K k -graphic sequences, Ars Combinatoria 75 (2005), 233–239. (2005) MR2133225
  12. The clique number of a graph with given degree sequence, Proc. Symposium on Graph Theory, A. R. Rao ed., MacMillan and Co. India Ltd., I.S.I. Lecture Notes Series 4 (1979), 251–267. (1979) 
  13. An Erdős-Gallai type result on the clique number of a realization of a degree sequence, unpublished, . 
  14. 10.1016/S0012-365X(02)00765-3, Discrete Math. 260 (2003), 295–305. (2003) MR1948398DOI10.1016/S0012-365X(02)00765-3
  15. 10.1016/j.disc.2005.03.028, Discrete Math. 301 (2005), 218–227. (2005) MR2171314DOI10.1016/j.disc.2005.03.028

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.