| Title:
|
Degree sequences of graphs containing a cycle with prescribed length (English) |
| Author:
|
Yin, Jian-Hua |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
59 |
| Issue:
|
2 |
| Year:
|
2009 |
| Pages:
|
481-487 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
graph |
| Keyword:
|
degree sequence |
| Keyword:
|
potentially $C_r$-graphic sequence |
| MSC:
|
05C07 |
| MSC:
|
05C38 |
| idZBL:
|
Zbl 1224.05107 |
| idMR:
|
MR2532385 |
| . |
| Date available:
|
2010-07-20T15:19:50Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140492 |
| . |
| Reference:
|
[1] Berge, C.: Graphs and Hypergraphs.North Holland Amsterdam (1973). Zbl 0254.05101, MR 0357172 |
| Reference:
|
[2] Erdős, P., Gallai, T.: Graphs with given degrees of vertices.Math. Lapok 11 (1960), 264-274. |
| Reference:
|
[3] Fulkerson, D. R., Hoffman, A. J., Mcandrew, M. H.: Some properties of graphs with multiple edges.Canad. J. Math. 17 (1965), 166-177. Zbl 0132.21002, MR 0177908, 10.4153/CJM-1965-016-2 |
| Reference:
|
[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 1985076 |
| Reference:
|
[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 1985084 |
| Reference:
|
[6] Lai, C.: The smallest degree sum that yields potentially $C_k$-graphical sequences.J. Combin. Math. Combin. Comput. 49 (2004), 57-64. Zbl 1054.05027, MR 2054962 |
| Reference:
|
[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. |
| Reference:
|
[8] Rao, A. R.: An Erdős-Gallai type result on the clique number of a realization of a degree sequence.Unpublished. |
| . |
