The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(K_r,r,n) such that every n-term graphic sequence π = (d₁,d₂,...,d_n) with term sum σ(π) = d₁ + d₂ + ... + d_n ≥ σ(K_r,r,n) is potentially K_r,r-graphic, where K_r,r is an r × r complete bipartite graph, i.e. π has a realization G containing K_r,r as its subgraph. In this paper, the values σ(K_r,r,n) for even r and n ≥ 4r² - r - 6 and for odd r and n ≥ 4r² + 3r - 8 are determined.     

On potentially <Emphasis Type="Italic">H</Emphasis>-graphic sequences

For given a graph H, a graphic sequence π = (d ₁, d ₂,..., d _n) is said to be potentially H-graphic if there is a realization of π containing H as a subgraph. In this paper, we characterize the potentially (K ₅ − e)-positive graphic sequences and give two simple necessary and sufficient conditions for a positive graphic sequence π to be potentially K ₅-graphic, where K _r is a complete graph on r vertices and K _r-e is a graph obtained from K _r by deleting one edge. Moreover, we also give a simple necessary and sufficient condition for a positive graphic sequence π to be potentially K ₆-graphic. Project supported by National Natural Science Foundation of China (No. 10401010).     

On potentially K 5-H-graphic sequences

Let K _m -H be the graph obtained from K _m by removing the edges set E(H) of H where H is a subgraph of K _m . In this paper, we characterize the potentially K ₅-P ₄ and K ₅-Y ₄-graphic sequences where Y ₄ is a tree on 5 vertices and 3 leaves. Research was supported by NNSF of China (10271105) and by NSF of Fujian (Z0511034), Fujian Provincial Training Foundation for “Bai-Quan-Wan Talents Engineering”, Project of Fujian Education Department, Project of Zhangzhou Teachers College and by NSERC.     

A Variation of an Extremal Theorem Due to Woodall

We consider a variation of an extremal theorem due to Woodall [12, or 1, Chapter 3] as follows: Determine the smallest even integer (₃C₁,n), such that every n-term graphic sequence = (d₁, d₂,..., d_n) with term sum () = d₁ + d₂ + ... + d_n (₃C₁,n) has a realization G containing a cycle of length r for each r = 3,4,...,l. In this paper, the values of (₃C_l,n) are determined for l = 2m – 1,n 3m – 4 and for l = 2m,n 5m – 7, where m 4.AMS Mathematics subject classification (1991) 05C35Project supported by the National Natural Science Foundation of China (Grant No. 19971086) and the Doctoral Program Foundation of National Education Department of China     

Conditions for -graphic sequences to be potentially -graphic

An r-graph is a loopless undirected graph in which no two vertices are joined by more than r edges. An r-complete graph on m+1 vertices, denoted by , is an r-graph on m+1 vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π=(d₁,d₂,…,d_n) of nonnegative integers is said to be r-graphic if it is realizable by an r-graph on n vertices. An r-graphic sequence π is said to be potentially -graphic if it has a realization containing as a subgraph. In this paper, some conditions for r-graphic sequences to be potentially -graphic are given. These are generalizations from 1-graphs to r-graphs of four theorems due to Rao [A.R. Rao, The clique number of a graph with given degree sequence, in: A.R. Rao (Ed.), Proc. Symposium on Graph Theory, in: I.S.I. Lecture Notes Series, vol. 4, MacMillan and Co. India Ltd., (1979), 251–267; A.R. Rao, An Erdös-Gallai type result on the clique number of a realization of a degree sequence (unpublished)] and Kézdy and Lehel [A.E. Kézdy, J. Lehel, Degree sequences of graphs with prescribed clique size, in: Y. Alavi et al., (Eds.), in: Combinatorics, Graph Theory, and Algorithms, vol. 2, New Issues Press, Kalamazoo Michigan, 1999, 535–544].     

The Smallest Degree Sum That Yields Potentially Kr＋1 - K3-Graphic Sequences

Let a（Kr,＋1 - K3,n） be the smallest even integer such that each n-term graphic sequence п= （d1,d2,…dn） with term sum σ（п） = d1 ＋ d2 ＋…＋ dn 〉 σ（Kr＋1 -K3,n） has a realization containing Kr＋1 - K3 as a subgraph, where Kr＋1 -K3 is a graph obtained from a complete graph Kr＋1 by deleting three edges which form a triangle. In this paper, we determine the value σ（Kr＋1 - K3,n） for r ≥ 3 and n ≥ 3r＋ 5.     

关于蕴含Ar,s—可图序列的注记

设G＝（V（G）,E（G）是n阶简单图,其顶点集V（G）＝{v1,…,vr,vr 1,…,vr s,…,vn},n={d1,…,dr 1,…,dr s,…,dn}是G的度序列,且vi的度为dio称G具有性质Ar,s,如果{v1,…,vr,vr 1,…,vr x}的导出子图是完全二部图Kr,s,且{v1,…,vr}和{vr 1,…,vr s}是Kr,s顶点集的二部划分,序列π={d1,…,dr,dr 1,…,dr s,…,dn}称为是蕴含Ar,s－可图的序列判别准则。     

Graphic sequences with a realization containing intersecting cliques

Let r≥ 1, k≥ 2 and Fm1 ,...,mki;r denote the most general definition of a friendship graph, that is, the graph of Kr+m1 , . . . , Kr+mk meeting in a common r set, where Kr+mi is the complete graph on r + mi vertices. Clearly, | Fm1 ,...,mki;r | = m1+ ··· + mk + r. Let σ(Fm1 ,...,mki;r , n) be the smallest even integer such that every n-term graphic sequence π = (d1, d2, . . . , dn) with term sum σ(π) = d1 + d2 + ··· + dn ≥σ(Fm1 ,...,mki;r,n) has a realization G containing Fm1 ,...,mki;r as a subgraph. In this paper, we determine σ(Fm1 ,...,mki;r,n) for n sufficiently large.     

蕴含K4＋P2-可图序列的刻划

对于给定的图H,若存在可图序列π的一个实现包含H作为子图,则称π为蕴含H-可图的．Gould等人考虑了下述极值问题的变形：确定最小的偶整数σ（H,n）,使得每个满足σ（π）≥σ（H,n）的n项可图序列π=（d1,d2,…,dn）是蕴含H-可图的,其中σ（π）=∑di．本文刻划了蕴含K4＋P2-可图序列,其中K4＋P2是向致的一个顶点添加两条悬挂边后构成的简单图．这一刻划导出σ（K4＋P2,n）的值．     

图的度序列

图的度序列是图论研究中一个重要的课题．至今已发表了４００余篇文章．本文概述这一课题的某些进展，其中包括了可图序列的判准、蕴含Ｐ可图序列和强迫Ｐ可图序列的一些主要结论，同时列出了一些有待进一步研究的问题．     

A Rao-type characterization for a sequence to have a realization containing an arbitrary subgraph H

Let G be an arbitrary spanning subgraph of the complete graph Kr+1 on r+1 vertices and Kr+1-E(G) be the graph obtained from Kr+1 by deleting all edges of G.A non-increasing sequence π=(d1,d2,...,dn) of nonnegative integers is said to be potentially Kr+1-E(G)-graphic if there is a graph on n vertices that has π as its degree sequence and contains Kr+1-E(G) as a subgraph.In this paper,a characterization of π that is potentially Kr+1-E(G)-graphic is given,which is analogous to the Erdo s–Gallai characterization of graphic sequences using a system of inequalities.This is a solution to an open problem due to Lai and Hu.As a corollary,a characterization of π that is potentially Ks,tgraphic can also be obtained,where Ks,t is the complete bipartite graph with partite sets of size s and t.This is a solution to an open problem due to Li and Yin.     

Quasi‐random graphs with given degree sequences

It is now known that many properties of the objects in certain combinatorial structures are equivalent, in the sense that any object possessing any of the properties must of necessity possess them all. These properties, termed quasirandom, have been described for a variety of structures such as graphs, hypergraphs, tournaments, Boolean functions, and subsets of Z _n, and most recently, sparse graphs. In this article, we extend these ideas to the more complex case of graphs which have a given degree sequence. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(Kr,r, n) such that every n-term graphic sequence π = (d1, d2,..., dn) with term sum σ(π) = d1 + d2 +…+ dn ≥σ(Kr,r, n) is potentially Kr,r-graphic, where Kr,r is an r × r complete bipartite graph, i.e. πr has a realization G containing Kr,r as its subgraph. In this paper, the values σ(Kr,r,n) for even r and n ≥ 4r2 - r - 6 and for odd r and n ≥ 4r2 + 3r - 8 are determined.     

Degree sequence conditions for maximally edge-connected graphs and digraphs

In this paper we give simple degree sequence conditions for the equality of edge-connectivity and minimum degree of a (di-)graph. One of the conditions implies results by Bollobás, Goldsmith and White, and Xu. Moreover, we give analogue conditions for bipartite (di-)graphs. © 1997 John Wiley & Sons, Inc. J Graph Theory 26:27–34, 1997     

The Erdös-Jacobson-Lehel conjecture on potentiallyP k-graphic sequence is true

A variation in the classical Turan extrernal problem is studied. A simple graphG of ordern is said to have propertyPk if it contains a clique of sizek+1 as its subgraph. Ann-term nonincreasing nonnegative integer sequence π=(d₁, d₂,⋯, d₂) is said to be graphic if it is the degree sequence of a simple graphG of ordern and such a graphG is referred to as a realization of π. A graphic sequence π is said to be potentiallyP _k-graphic if it has a realizationG having propertyP _k . The problem: determine the smallest positive even number σ(k, n) such that everyn-term graphic sequence π=(d₁, d₂,…, d₂) without zero terms and with degree sum σ(π)=(d ₁+d ₂+ …+d ₂) at least σ(k,n) is potentially P_k-graphic has been proved positive. Project supported by the National Natural Science Foundation of China (Grant No. 19671077) and the Doctoral Program Foundation of National Education Department of China.     

The signless Laplacian spectral radius of bicyclic graphs with prescribed degree sequences

In this paper, we characterize all extremal connected bicyclic graphs with the largest signless Laplacian spectral radius in the set of all connected bicyclic graphs with prescribed degree sequences. Moreover, the signless Laplacian majorization theorem is proved to be true for connected bicyclic graphs. As corollaries, all extremal connected bicyclic graphs having the largest signless Laplacian spectral radius are obtained in the set of all connected bicyclic graphs of order n (resp. all connected bicyclic graphs with a specified number of pendant vertices, and all connected bicyclic graphs with given maximum degree).     

Graphic Sequences with a Realization Containing a Union of Cliques

An integer sequence π is said to be graphic if it is the degree sequence of some simple graph G. In this case we say that G is a realization of π. Given a graph H, and a graphic sequence π we say that π is potentially H-graphic if there is some realization of π that contains H as a subgraph. We define σ(H,n) to be the minimum even integer such that every graphic sequence with sum at least σ(H,n) is potentially H-graphic. In this paper, we determine σ(H,n) for the graph H = K_m1∪ K_m2∪...∪ K_mk when n is a sufficiently large integer. This is accomplished by determining σ(K_j + kK₂,n) where j and k are arbitrary positive integers, and considering the case where j = m − 2k and m = ∑ m_i.     

Degree sums for edges and cycle lengths in graphs

Let G be a graph of order n satisfying d(u) + d(v) ≥ n for every edge uv of G. We show that the circumference—the length of a longest cycle—of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length between 3 and the circumference, unless G is complete bipartite. If G is 1-tough then it is pancyclic or G = K_r,r with r = n/2. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 253–256, 1997     

On a conjecture concerningk-Hamilton-nice sequences

In this paper, we prove that a non-negative rational number sequence (a ₁,a ₂, ...,a _k+1) isk-Hamilton-nice, if (1)a _k+12, and (2) _j ^=1/h (i _j –1)k–1 implies for arbitraryi ₁,i ₂,...i _h {1,2,... ,k}. This result was conjectured by Guantao Chen and R.H. Schelp, and it generalizes several well-known sufficient conditions for graphs to be Hamiltonian.This project is supported by the National Natural Science Foundation of China.