JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2022, Vol. 57 ›› Issue (3): 85-88.doi: 10.6040/j.issn.1671-9352.0.2020.102

Previous Articles    

A sufficient condition for (An;Bn) to be identical parity m-graphic

GUO Ji-yun1,2, LI Hai-yan2, GUO Jin2, CAI Bai-guang2*   

  1. 1. Center for Applied Mathematics, Tianjin University, Tianjin 300072, China;
    2. School of Science, Hainan University, Haikou 570228, Hainan, Chian
  • Published:2022-03-15

Abstract: Let An={a1,a2,…,an} and Bn={b1,b1,…,bn} be two sequences of nonnegative integers with ai≤bi for i=1,2,…,n. If An and Bn satisfy a1≥a2≥…≥an and ai=ai+1 implies bi≥bi+1 for i=1,2,…,n-1, then An and Bn are said to be in good order. If ai≡bi(mod 2)for each i and there exists a m-graph G with vertices v1,…,vn such that ai≤dG(vi)≤bi and dG(vi)≡bi(mod 2)for each i, then (An;Bn) is said to be identical parity m-graphic, G is called a realization of the pair. A constructive method is performed to prove a sufficient condition for (An;Bn) to be identical parity m-graphic, where An and Bn are in good order.

Key words: degree sequences, constructive method, identical parity m-graphic

CLC Number: 

  • O157.5
[1] ERDÖS P, GALLAI T. Graphs with prescribed degrees of vertices[J]. Mat Lapok, 1960, 11:24-274.
[2] CAI Maochen, DENG Xiaotie, ZANG Wenan. Solution to a problem on degree sequences of graphs[J]. Discrete Mathematics, 2000, 219(1/2/3):253-257.
[3] GUO Jiyun, YIN Jianhua. A constructive extension of the characterization on potentially Ks, t-bigraphic pairs[J]. Discussiones Mathematicae Graph Theory, 2017, 37(1):251.
[4] LAI Chunhui, HU Lili. Potentially Km-G-graphical sequences: a survey[J]. Czechoslovak Mathematical Journal, 2009, 59(4):1059-1075.
[5] 李炯生, 尹建华. 极值图论与度序列[J]. 数学进展, 2004, 33(3):273-283. LI Jiongsheng, YIN Jianhua. Extremal graph theory and degree sequences[J]. Advances in Mathematics, 2004, 33(3):273-283.
[6] RAO S B. A survey of the theory of potentially P-graphic and forcibly P-graphic degree sequences[M] //Combinatorics and Graph Theory. Berlin: Springer, 1981: 417-440.
[7] GARG A, GOEL A, TRIPATHI A. Constructive extensions of two results on graphic sequences[J]. Discrete Applied Mathematics, 2011, 159(17):2170-2174.
[8] LOVÁSZ L. The factorization of graphs: II[J]. Acta Mathematica Academiae Scientiarum Hungaricae, 1972, 23(1/2):223-246.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!