TOPICS
Search

Graphic Sequence


A graphic sequence is a sequence of numbers which can be the degree sequence of some graph. A sequence can be checked to determine if it is graphic using GraphicQ[g] in the Wolfram Language package Combinatorica` .

Erdős and Gallai (1960) proved that a degree sequence {d_1,...,d_n} is graphic iff the sum of vertex degrees is even and the sequence obeys the property

 sum_(i=1)^rd_i<=r(r-1)+sum_(i=r+1)^nmin(r,d_i)

for each integer r<=n-1 (Skiena 1990, p. 157), and this condition also generalizes to directed graphs. Tripathi and Vijay (2003) showed that this inequality need be checked only for as many r as there are distinct terms in the sequence, not for all 1<=r<=n-1.

Havel (1955) and Hakimi (1962) proved another characterization of graphic sequences, namely that a degree sequence with n>=3 and d_1>=1 is graphical iff the sequence {d_2-1,d_3-1,...,d_(d_1+1)-1,d_(d_1+2),...,d_p} is graphical. In addition, Havel (1955) and Hakimi (1962) showed that if a degree sequence is graphic, then there exists a graph G such that the node of highest degree is adjacent to the Delta(G) next highest degree vertices of G, where Delta(G) is the maximum vertex degree of G.

No degree sequence can be graphic if all the degrees occur with multiplicity 1 (Behzad and Chartrand 1967, p. 158; Skiena 1990, p. 158). Any degree sequence whose sum is even can be realized by a multigraph having loops (Hakimi 1962; Skiena 1990, p. 158).


See also

Degree Sequence, Graphical Partition, Unigraphic Graph, Vertex Degree

Explore with Wolfram|Alpha

References

Behzad, M. and Chartrand, G. "No Graph is Perfect." Amer. Math. Monthly 74, 962-963, 1967.Eggleton, R. B. "Graphic Sequences and Graphic Polynomials." In Infinite and Finite Sets (Ed. A. Hajnal). Amsterdam, Netherlands: North-Holland, pp. 385-293, 1975.Erdős, P. and Gallai, T. "Graphs with Prescribed Degrees of Vertices" [Hungarian]. Mat. Lapok. 11, 264-274, 1960.Fulkerson, D. R. "Upsets in Round Robin Tournaments." Canad. J. Math. 17, 957-969, 1965.Fulkerson, D. R.; Hoffman, A. J.; and McAndrew, M. H. "Some Properties of Graphs with Multiple Edges." Canad. J. Math. 17, 166-177, 1965.Hakimi, S. "On the Realizability of a Set of Integers as Degrees of the Vertices of a Graph." SIAM J. Appl. Math. 10, 496-506, 1962.Havel, V. "A Remark on the Existence of Finite Graphs" [Czech]. Časopis Pest. Mat. 80, 477-480, 1955.Ryser, H. J. "Combinatorial Properties of Matrices of Zeros and Ones." Canad. J. Math. 9, 371-377, 1957.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 157, 1990.Tripathi, A. and Vijay, S. "A Note on a Theorem of Erdős & Gallai." Discr. Math. 265, 417-420, 2003.

Referenced on Wolfram|Alpha

Graphic Sequence

Cite this as:

Weisstein, Eric W. "Graphic Sequence." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphicSequence.html

Subject classifications