Geodesic
Degree sequences of graphs containing a cycle with prescribed length
Czechoslovak Mathematical Journal, Tome 59 (2009) no. 2, pp. 481-487 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $r\ge 3$, $n\ge r$ and $\pi =(d_1,d_2,\ldots ,d_n)$ be a non-increasing sequence of nonnegative integers. If $\pi $ has a realization $G$ with vertex set $V(G)=\{v_1,v_2,\ldots ,v_n\}$ such that $d_G(v_i)=d_i$ for $i=1,2,\ldots , n$ and $v_1v_2\cdots v_rv_1$ is a cycle of length $r$ in $G$, then $\pi $ is said to be potentially $C_r''$-graphic. In this paper, we give a characterization for $\pi $ to be potentially $C_r''$-graphic.
Let $r\ge 3$, $n\ge r$ and $\pi =(d_1,d_2,\ldots ,d_n)$ be a non-increasing sequence of nonnegative integers. If $\pi $ has a realization $G$ with vertex set $V(G)=\{v_1,v_2,\ldots ,v_n\}$ such that $d_G(v_i)=d_i$ for $i=1,2,\ldots , n$ and $v_1v_2\cdots v_rv_1$ is a cycle of length $r$ in $G$, then $\pi $ is said to be potentially $C_r''$-graphic. In this paper, we give a characterization for $\pi $ to be potentially $C_r''$-graphic.
Classification : 05C07, 05C38
Keywords: graph; degree sequence; potentially $C_r$-graphic sequence 
@article{CMJ_2009_59_2_a12,
     author = {Yin, Jian-Hua},
     title = {Degree sequences of graphs containing a cycle with prescribed length},
     journal = {Czechoslovak Mathematical Journal},
     pages = {481--487},
     year = {2009},
     volume = {59},
     number = {2},
     mrnumber = {2532385},
     zbl = {1224.05107},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2009_59_2_a12/}
}
TY  - JOUR
AU  - Yin, Jian-Hua
TI  - Degree sequences of graphs containing a cycle with prescribed length
JO  - Czechoslovak Mathematical Journal
PY  - 2009
SP  - 481
EP  - 487
VL  - 59
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2009_59_2_a12/
LA  - en
ID  - CMJ_2009_59_2_a12
ER  - 
%0 Journal Article
%A Yin, Jian-Hua
%T Degree sequences of graphs containing a cycle with prescribed length
%J Czechoslovak Mathematical Journal
%D 2009
%P 481-487
%V 59
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2009_59_2_a12/
%G en
%F CMJ_2009_59_2_a12
Yin, Jian-Hua. Degree sequences of graphs containing a cycle with prescribed length. Czechoslovak Mathematical Journal, Tome 59 (2009) no. 2, pp. 481-487. http://geodesic.mathdoc.fr/item/CMJ_2009_59_2_a12/

[1] Berge, C.: Graphs and Hypergraphs. North Holland Amsterdam (1973). | MR | Zbl

[2] Erdős, P., Gallai, T.: Graphs with given degrees of vertices. Math. Lapok 11 (1960), 264-274.

[3] Fulkerson, D. R., Hoffman, A. J., Mcandrew, M. H.: Some properties of graphs with multiple edges. Canad. J. Math. 17 (1965), 166-177. | DOI | MR | Zbl

[4] Gould, R. J., Jacobson, M. S., Lehel, J.: Potentially $G$-graphical degree sequences. In: Combinatorics, Graph Theory, and Algorithms, Vol. 1 Y. Alavi et al. New Issues Press Kalamazoo Michigan (1999), 451-460. | MR

[5] Kézdy, A. E., Lehel, J.: Degree sequences of graphs with prescribed clique size. In: Combinatorics, Graph Theory, and Algorithms, Vol. 2 Y. Alavi New Issues Press Kalamazoo Michigan (1999), 535-544. | MR

[6] Lai, C.: The smallest degree sum that yields potentially $C_k$-graphical sequences. J. Combin. Math. Combin. Comput. 49 (2004), 57-64. | MR | Zbl

[7] Rao, A. R.: The clique number of a graph with given degree sequence. Graph Theory, Proc. Symp. Calcutta 1976, ISI Lecture Notes 4 A. R. Rao (1979), 251-267.

[8] Rao, A. R.: An Erdős-Gallai type result on the clique number of a realization of a degree sequence. Unpublished.