Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graph; degree sequence; potentially $C_r$-graphic sequence
graph; degree sequence; potentially $C_r$-graphic sequence
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.
References:
[1] Berge, C.: Graphs and Hypergraphs. North Holland Amsterdam (1973). MR 0357172 | Zbl 0254.05101
[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 10.4153/CJM-1965-016-2 | MR 0177908 | Zbl 0132.21002
[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
[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
[6] Lai, C.: The smallest degree sum that yields potentially $C_k$-graphical sequences. J. Combin. Math. Combin. Comput. 49 (2004), 57-64. MR 2054962 | Zbl 1054.05027
[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.
Search
Partner of
